Problema de paridad matroide

El mayor conjunto independiente de elementos emparejados.

Un ejemplo del problema de paridad matroide en una matroide gráfica : dado un gráfico con bordes coloreados, que tiene exactamente dos bordes por color, encuentre un bosque lo más grande posible que nuevamente tenga exactamente dos bordes por color.

En optimización combinatoria , el problema de paridad matroide es un problema de encontrar el mayor conjunto independiente de elementos emparejados en una matroide . ^[1] El problema fue formulado por Lawler (1976) como una generalización común de coincidencia de gráficos e intersección matroide . ^{[1] [2]} También se conoce como coincidencia de polimatroides o problema de matchoides . ^[3]

La paridad matroide se puede resolver en tiempo polinómico para matroides lineales . Sin embargo, es NP-difícil para ciertas matroides representadas de forma compacta y requiere más de un número polinómico de pasos en el modelo de oráculo matroide . ^{[1] [4]}

Las aplicaciones de los algoritmos de paridad matroide incluyen la búsqueda de subgrafos planos grandes ^[5] y la búsqueda de incrustaciones de gráficos de género máximo . ^[6] Estos algoritmos también se pueden utilizar para encontrar conjuntos dominantes conectados y conjuntos de vértices de retroalimentación en gráficos de grado tres como máximo. ^[7]

Formulación

Una matroide se puede definir a partir de un conjunto finito de elementos y a partir de una noción de lo que significa que subconjuntos de elementos sean independientes, sujeto a las siguientes restricciones:

• Todo subconjunto de un conjunto independiente debe ser independiente.
• Si y son conjuntos independientes, con , entonces existe un elemento tal que es independiente. ^[1] ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle |T|>|S|}$ ${\displaystyle t\in T}$ ${\displaystyle S\cup \{t\}}$

Ejemplos de matroides incluyen las matroides lineales (en las que los elementos son vectores en un espacio vectorial , con independencia lineal ), las matroides gráficas (en las que los elementos son aristas en un gráfico no dirigido , independientes cuando no contienen ningún ciclo ) y la partición matroides (en las que los elementos pertenecen a una familia de conjuntos disjuntos , y son independientes cuando contienen como máximo un elemento en cada conjunto). Las matroides gráficas y las matroides de partición son casos especiales de matroides lineales. ^[1]

En el problema de paridad de matroides, la entrada consta de una matroide junto con un emparejamiento de sus elementos, de modo que cada elemento pertenece a un par. El objetivo es encontrar un subconjunto de pares, lo más grande posible, de modo que la unión de los pares en el subconjunto elegido sea independiente. ^{[1] [2]} Otra variación aparentemente más general, en la que los pares permitidos forman un gráfico en lugar de tener solo un par por elemento, es equivalente: un elemento que aparece en más de un par podría ser reemplazado por múltiples copias del elemento, uno por par. ^[8]

Algoritmos

El problema de paridad matroide para matroides lineales se puede resolver mediante un algoritmo aleatorio en el tiempo , donde es el número de elementos de la matroide, es su rango (el tamaño del conjunto independiente más grande) y es el exponente en los límites de tiempo para matroides rápidas. multiplicación de matrices . ^[1] En particular, utilizando un algoritmo de multiplicación de matrices de Le Gall, ^[9] se puede resolver en el tiempo . Sin utilizar una multiplicación rápida de matrices, el problema de paridad matroide lineal se puede resolver a tiempo . ^[1] ${\displaystyle O(nr^{\omega -1})}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle \omega }$ ${\displaystyle O(nr^{1.3729})}$ ${\displaystyle O(nr^{2})}$

Estos algoritmos se basan en una formulación de álgebra lineal del problema de Geelen & Iwata (2005). Supongamos que una entrada al problema consta de pares de vectores dimensionales (dispuestos como vectores de columna en una matriz de tamaño ). Entonces el número de pares en la solución óptima es ${\displaystyle m}$ ${\displaystyle r}$ ${\displaystyle M}$ ${\displaystyle r\times 2m}$

${\displaystyle {\frac {1}{2}}\operatorname {rank} {\begin{pmatrix}0&M\\M^{T}&T\end{pmatrix}}-m,}$

donde es una matriz diagonal de bloques cuyos bloques son submatrices de la forma ${\displaystyle T}$ ${\displaystyle 2\times 2}$

${\displaystyle {\begin{pmatrix}0&t_{i}\\-t_{i}&0\end{pmatrix}}}$

para una secuencia de variables . ^[10] El lema de Schwartz-Zippel se puede utilizar para probar si esta matriz tiene rango completo o no (es decir, si la solución tiene tamaño o no), asignando valores aleatorios a las variables y probando si la matriz resultante tiene determinante cero. . Aplicando un algoritmo codicioso que elimina pares uno a la vez estableciendo sus indeterminados en cero siempre que la matriz permanezca de rango completo (manteniendo la matriz inversa usando la fórmula de Sherman-Morrison para verificar el rango después de cada eliminación), se puede encontrar una solución siempre que esta prueba demuestre que existe. Métodos adicionales extienden este algoritmo al caso en que la solución óptima al problema de paridad matroide tenga menos de pares. ^[1] ${\displaystyle t_{1},\dots t_{m}}$ ${\displaystyle r/2}$ ${\displaystyle t_{i}}$ ${\displaystyle r/2}$

Para las matroides gráficas, se conocen algoritmos más eficientes, con tiempo de ejecución en gráficos con vértices y aristas. ^[11] Para gráficos simples , es , pero para multigrafos , puede ser mayor, por lo que también es interesante tener algoritmos con menor o ninguna dependencia y peor dependencia . En estos casos, también es posible resolver el problema de paridad matroide gráfica en un tiempo esperado aleatorio , o en el tiempo cuando cada par de aristas forma un camino. ^[1] ${\displaystyle O(mn\log ^{6}n)}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle O(n^{2})}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle O(n^{4})}$ ${\displaystyle O(n^{3})}$

Aunque el problema de paridad de matroides es NP-difícil para matroides arbitrarias, aún se puede aproximar de manera eficiente. Los algoritmos de búsqueda local simples proporcionan un esquema de aproximación en tiempo polinomial para este problema y encuentran soluciones cuyo tamaño, como fracción del tamaño óptimo de la solución, es arbitrariamente cercano a uno. El algoritmo comienza con el conjunto vacío como solución e intenta repetidamente aumentar el tamaño de la solución en uno eliminando como máximo un número constante de pares de la solución y reemplazándolos por un conjunto diferente con un par más. Cuando ya no son posibles más movimientos de este tipo, la solución resultante se devuelve como la aproximación a la solución óptima. Para lograr una relación de aproximación de , basta con elegir que sea aproximadamente . ^[8] ${\displaystyle C}$ ${\displaystyle 1-\epsilon }$ ${\displaystyle C}$ ${\displaystyle 5^{\lceil 1/2\epsilon \rceil }}$

Aplicaciones

Muchos otros problemas de optimización pueden formularse como problemas de paridad matroide lineal y resolverse en tiempo polinomial utilizando esta formulación.

Coincidencia de gráficos

Una coincidencia máxima en un gráfico es un subconjunto de aristas, sin que dos compartan un punto final, que sea lo más grande posible. Se puede formular como un problema de paridad matroide en una partición matroide que tiene un elemento para cada incidencia de vértice-borde en el gráfico. En esta matroide, dos elementos están emparejados si son las dos incidencias para el mismo borde entre sí. Un subconjunto de elementos es independiente si tiene como máximo una incidencia por cada vértice del gráfico. Los pares de elementos en una solución al problema de paridad matroide para esta matroide son las incidencias entre las aristas en una coincidencia máxima y sus puntos finales. ^[2]

intersección matroide

Una instancia del problema de intersección de matroides consta de dos matroides en el mismo conjunto de elementos; el objetivo es encontrar un subconjunto de elementos que sea lo más grande posible y que sea independiente en ambas matroides. Para formular la intersección de matroides como un problema de paridad de matroides, construya una nueva matroide cuyos elementos sean la unión disjunta de dos copias de los elementos dados, una para cada matroide de entrada. En la nueva matroide, un subconjunto es independiente si su restricción a cada una de las dos copias es independiente en cada una de las dos matroides, respectivamente. Empareje los elementos de la nueva matroide para que cada elemento se empareje con su copia. Los pares de elementos en una solución al problema de paridad de matroides para esta matroide son las dos copias de cada elemento en una solución al problema de intersección de matroides. ^[2]

Grandes subgrafos planos

En un gráfico arbitrario, el problema de encontrar el conjunto más grande de triángulos en un gráfico dado, sin otros ciclos que los triángulos elegidos, se puede formular como un problema de paridad matroide en una matroide gráfica cuyos elementos son bordes del gráfico, con uno par de aristas por triángulo (duplicando aristas si es necesario cuando pertenecen a más de un triángulo). Los pares de elementos en una solución al problema de paridad matroide para esta matroide son los dos bordes en cada triángulo de un conjunto óptimo de triángulos. El mismo problema también se puede describir como el de encontrar el subhipergrafo Berge-acíclico más grande de un hipergrafo de 3 uniformes . En la versión hipergráfica del problema, las hiperaristas son los triángulos del gráfico dado. ^[3]

Un gráfico de cactus es un gráfico en el que cada dos ciclos tienen como máximo un vértice en común. Como caso especial, las gráficas en las que cada ciclo es un triángulo son necesariamente gráficas de cactus. El cactus triangular más grande en el gráfico dado se puede encontrar agregando aristas adicionales de un árbol de expansión , sin crear ningún ciclo nuevo, de modo que el subgrafo resultante tenga los mismos componentes conectados que el gráfico original. Los gráficos de cactus son automáticamente gráficos planos , y el problema de encontrar gráficos de cactus triangulares forma la base del algoritmo de aproximación más conocido al problema de encontrar el subgrafo plano más grande de un gráfico determinado, un paso importante en la planarización . El cactus triangular más grande siempre tiene al menos 4/9 del número de aristas del subgrafo plano más grande, mejorando la relación de aproximación de 1/3 obtenida al usar un árbol de expansión arbitrario. ^[5]

Rigidez combinatoria

Una estructura de barras rígidas en el plano euclidiano , conectadas en sus extremos por uniones flexibles, se puede fijar en una sola posición en el plano fijando algunas de sus uniones a puntos del plano. El número mínimo de juntas que es necesario fijar para fijar la estructura se denomina número de fijación. Se puede calcular a partir de una solución a un problema de paridad matroide asociado. ^[3]

Incrustaciones de género máximo

Un árbol Xuong

Se puede obtener una incrustación celular de un gráfico determinado en una superficie del género máximo posible a partir de un árbol Xuong del gráfico. Este es un árbol de expansión con la propiedad de que, en el subgrafo de aristas que no están en el árbol, el número de componentes conectados con un número impar de aristas es lo más pequeño posible.

Para formular el problema de encontrar un árbol Xuong como un problema de paridad matroide, primero subdivida cada borde del gráfico dado en una ruta, con la longitud de la ruta igual al número de otras aristas incidentes . Luego, empareje los bordes del gráfico subdividido, de modo que cada par de bordes en el gráfico original esté representado por un solo par de bordes en el gráfico subdividido, y cada borde en el gráfico subdividido esté emparejado exactamente una vez. Resuelva un problema de paridad matroide con las aristas emparejadas del gráfico subdividido, utilizando su matroide cográfica (una matroide lineal en la que un subconjunto de aristas es independiente si su eliminación no separa el gráfico). Cualquier árbol de expansión del gráfico original que evite los bordes utilizados en la solución de paridad matroide es necesariamente un árbol Xuong. ^[6] ${\displaystyle e}$ ${\displaystyle e}$

Dominación conectada

Un conjunto dominante conectado en un gráfico es un subconjunto de vértices cuyo subgrafo inducido está conectado, adyacente a todos los demás vértices. Es NP-difícil encontrar el conjunto dominante conectado más pequeño en gráficos arbitrarios, pero se puede encontrar en tiempo polinomial para gráficos de grado máximo tres. En un gráfico cúbico , se puede reemplazar cada vértice por una ruta de dos aristas conectada a los extremos de sus tres puntos finales, y formular un problema de paridad matroide en los pares de aristas generadas de esta manera, utilizando la matroide cográfica del gráfico expandido. Los vértices cuyos caminos no se utilizan en la solución forman un conjunto dominante mínimo conectado. En una gráfica de grado tres como máximo, algunas transformaciones adicionales simples reducen el problema a uno en una gráfica cúbica. ^[7]

Conjunto de vértices de retroalimentación

Un vértice de retroalimentación establecido en un gráfico es un subconjunto de vértices que toca todos los ciclos. En los gráficos cúbicos, hay una ecuación lineal que relaciona el número de vértices, el número ciclomático , el número de componentes conectados, el tamaño de un conjunto dominante mínimo conectado y el tamaño de un conjunto mínimo de vértices de retroalimentación. ^[12] De ello se deduce que el mismo problema de paridad matroide utilizado para encontrar conjuntos dominantes conectados también se puede utilizar para encontrar conjuntos de vértices de retroalimentación en gráficos de grado máximo tres. ^[7]

Dureza

El problema de camarilla , de encontrar un subgrafo completo de vértice en un gráfico de vértice dado , se puede transformar en una instancia de paridad matroide de la siguiente manera. Construya una matroide de pavimento sobre elementos, emparejados de modo que haya un par de elementos por par de vértices. Defina un subconjunto de estos elementos como independiente si satisface cualquiera de las tres condiciones siguientes: ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle 2n}$ ${\displaystyle S}$

• ${\displaystyle S}$tiene menos que elementos. ${\displaystyle 2k}$
• ${\displaystyle S}$tiene exactamente elementos, pero no es la unión de pares de elementos. ${\displaystyle 2k}$ ${\displaystyle k}$
• ${\displaystyle S}$Es la unión de pares de elementos que forman una camarilla en . ${\displaystyle k}$ ${\displaystyle G}$

Entonces hay una solución al problema de paridad de matroide para esta matroide, de tamaño , si y sólo si tiene una camarilla de tamaño . Dado que encontrar camarillas de un tamaño determinado es NP-completo, se deduce que determinar si este tipo de problema de paridad matricial tiene una solución de tamaño también es NP-completo. ^[13] ${\displaystyle 2k}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle 2k}$

Esta transformación del problema no depende en profundidad de la estructura del problema de camarilla y funcionaría para cualquier otro problema de encontrar subconjuntos de tamaño de un conjunto mayor que satisfagan una prueba computable. Al aplicarlo a un gráfico permutado aleatoriamente que contiene exactamente una camarilla de tamaño , se puede demostrar que cualquier algoritmo determinista o aleatorio para la paridad matroide que accede a su matroide sólo mediante pruebas de independencia necesita realizar un número exponencial de pruebas. ^[4] ${\displaystyle k}$ ${\displaystyle k}$

Referencias

1. Cheung, Ho Yee; Lau, Lap Chi; Leung, Kai Man (2014), "Algoritmos algebraicos para problemas de paridad matroide lineal" (PDF) , Transacciones ACM sobre algoritmos , 10 (3): 10:1–10:26, CiteSeerX  10.1.1.194.604 , doi :10.1145/ 2601066, SEÑOR  3233690, S2CID  894004
2. Lawler, Eugene L. (1976), "Capítulo 9: El problema de la paridad de las matroides", Optimización combinatoria: redes y matroides , Nueva York: Holt, Rinehart y Winston, págs. 356–367, MR  0439106
3. Lovász, L. (1980), "Emparejamiento de matroides y algunas aplicaciones", Journal of Combinatorial Theory , Serie B, 28 (2): 208–236, doi : 10.1016/0095-8956(80)90066-0 , SEÑOR  0572475
4. Jensen, por M.; Korte, Bernhard (1982), "Complejidad de los algoritmos de propiedades matroides", SIAM Journal on Computing , 11 (1): 184–190, doi :10.1137/0211014, MR  0646772
5. Călinescu, Gruia; Fernández, Cristina G.; Finkler, Ulrich; Karloff, Howard (1998), "Un mejor algoritmo de aproximación para encontrar subgrafos planos", Journal of Algorithms , 27 (2): 269–302, CiteSeerX 10.1.1.47.4731 , doi :10.1006/jagm.1997.0920, MR  1622397, S2CID  8329680 .
6. Furst, Merrick L.; Bruto, Jonathan L.; McGeoch, Lyle A. (1988), "Encontrar una incrustación de gráfico de género máximo", Journal of the ACM , 35 (3): 523–534, doi : 10.1145/44483.44485 , MR  0963159, S2CID  17991210
7. Ueno, Shûichi; Kajitani, Yoji; Gotoh, Shin'ya (1988), "Sobre el problema de conjuntos independientes no separables y el problema de conjuntos de retroalimentación para gráficos sin un grado de vértice superior a tres", Actas de la Primera Conferencia Japonesa sobre Teoría y Aplicaciones de Grafos (Hakone, 1986), Matemáticas Discretas , 72 (1–3): 355–360, doi : 10.1016/0012-365X(88)90226-9 , SEÑOR  0975556
8. Lee, Jon; Sviridenko, Maxim; Vondrák, Jan (2013), "Coincidencia de matroides: el poder de la búsqueda local", SIAM Journal on Computing , 42 (1): 357–379, CiteSeerX 10.1.1.600.4878 , doi :10.1137/11083232X, MR  3033132 
9. Le Gall, François (2014), "Poderes de tensores y multiplicación rápida de matrices", Actas del 39º Simposio internacional sobre computación simbólica y algebraica (ISSAC 2014) , Nueva York: ACM, págs. 296–303, arXiv : 1401.7714 , doi :10.1145/2608628.2608664, ISBN 9781450325011, SEÑOR  3239939, S2CID  2597483
10. Geelen, James ; Iwata, Satoru (2005), "Emparejamiento de matroides mediante matrices simétricas oblicuas mixtas", Combinatorica , 25 (2): 187–215, CiteSeerX 10.1.1.702.5431 , doi :10.1007/s00493-005-0013-7, MR  2127610 , S2CID  18576135 
11. Gabow, Harold N .; Stallmann, Matthias (1985), "Algoritmos eficientes para la intersección y paridad de matroides gráficas (resumen ampliado)", en Brauer, Wilfried (ed.), Autómatas, lenguajes y programación , Lecture Notes in Computer Science, vol. 194, Berlín: Springer, págs. 210–220, doi :10.1007/BFb0015746, ISBN 978-3-540-15650-5, señor  0819256
12. Speckenmeyer, E. (1986), "Límites en conjuntos de vértices de retroalimentación de gráficos cúbicos no dirigidos", Álgebra, combinatoria y lógica en informática, vol. I, II (Győr, 1983) , Colloquia Mathematica Societatis János Bolyai, vol. 42, Ámsterdam: Holanda Septentrional, págs. 719–729, SEÑOR  0875903
13. Soto, José A. (2014), "Un PTAS simple para la comparación de matroides ponderadas en matroides ordenables de base fuerte", Matemáticas Aplicadas Discretas , 164 (parte 2): 406–412, arXiv : 1102.3491 , doi : 10.1016/j.dam .2012.10.019, SEÑOR  3159127, S2CID  17970404