En la optimización combinatoria , el problema de la 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 de matroides . [1] [2] También se conoce como emparejamiento polimatroide , o el problema matchoide . [3]
La paridad matroide se puede resolver en tiempo polinomial para matroides lineales . Sin embargo, es NP-difícil para ciertas matroides representadas de forma compacta, y requiere más de un número polinomial de pasos en el modelo del oráculo matroide . [1] [4]
Las aplicaciones de los algoritmos de paridad matroide incluyen la búsqueda de grandes subgráficos planos [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 máximo grado tres. [7]
Formulación
Una matroide se puede definir a partir de un conjunto finito de elementos y de una noción de lo que significa que los subconjuntos de elementos sean independientes, sujeto a las siguientes restricciones:
- Cada subconjunto de un conjunto independiente debería ser independiente.
- Si y son conjuntos independientes, con , entonces existe un elemento tal que es independiente. [1]
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 ciclo ) y la partición. matroides (en los 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 matroide, la entrada consiste en una matroide junto con un emparejamiento en sus elementos, de modo que cada elemento pertenece a un par. El objetivo es encontrar un subconjunto de los 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 de matroides para matroides lineales se puede resolver mediante un algoritmo aleatorio en el tiempo, dónde es el número de elementos de la matroide, es su rango (el tamaño del conjunto independiente más grande), yes el exponente en los límites de tiempo para la multiplicación rápida de matrices . [1] En particular, utilizando un algoritmo de multiplicación de matrices de Le Gall, [9] se puede resolver a tiempo. Sin utilizar la multiplicación rápida de matrices, el problema de paridad de matriz lineal se puede resolver a tiempo. [1]
Estos algoritmos se basan en una formulación de álgebra lineal del problema de Geelen & Iwata (2005) . Suponga que una entrada al problema consiste en 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
dónde es una matriz diagonal de bloques cuyos bloques son submatrices de la forma
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 probar si la matriz resultante tiene un determinante cero. Al aplicar un algoritmo codicioso que elimina los pares uno a la vez al establecer sus indeterminados en cero siempre que la matriz permanezca en el rango completo (manteniendo la matriz inversa utilizando 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 muestre que existe. Los métodos adicionales extienden este algoritmo al caso de que la solución óptima al problema de paridad matroide tenga menos depares. [1]
Para las matroides gráficas, se conocen algoritmos más eficientes, con tiempo de ejecución en gráficos con vértices y bordes. [11] Para gráficos simples , es , pero para multigraphs , puede ser más grande, por lo que también es interesante tener algoritmos con menor o sin dependencia de y peor dependencia de . 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]
Aunque el problema de la paridad matroide es NP-difícil para las matroides arbitrarias, todavía se puede aproximar de manera eficiente. Los algoritmos de búsqueda local simples proporcionan un esquema de aproximación de tiempo polinomial para este problema y encuentran soluciones cuyo tamaño, como una fracción del tamaño de la solución óptima, es arbitrariamente cercano a uno. El algoritmo comienza con el conjunto vacío como su solución y repetidamente intenta aumentar el tamaño de la solución en uno eliminando como máximo un número constantede pares de la solución y reemplazarlos por un conjunto diferente con un par más. Cuando 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 ser aproximadamente . [8]
Aplicaciones
Muchos otros problemas de optimización pueden formularse como problemas de paridad de matriz 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 bordes, no hay dos que compartan un punto final, que sea lo más grande posible. Se puede formular como un problema de paridad matroide en una matriz de partición que tiene un elemento para cada incidencia de vértice-borde en el gráfico. En este matroide, dos elementos se emparejan si son las dos incidencias para el mismo borde que el otro. Un subconjunto de elementos es independiente si tiene como máximo una incidencia para 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 los bordes en una coincidencia máxima y sus puntos finales. [2]
- Intersección matroide
- Un ejemplo del problema de intersección de matroides consiste en 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 del nuevo matroide para que cada elemento esté emparejado con su copia. Los pares de elementos en una solución al problema de paridad matroide para este matroide son las dos copias de cada elemento en una solución al problema de intersección matroide. [2]
- Subgrafos planos grandes
En un gráfico arbitrario, el problema de encontrar el mayor conjunto de triángulos en un gráfico dado, sin ciclos distintos a los triángulos elegidos, se puede formular como un problema de paridad matroide en una matriz gráfica cuyos elementos son los bordes del gráfico, con uno par de aristas por triángulo (duplicar 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 las dos aristas de cada triángulo de un conjunto óptimo de triángulos. El mismo problema también puede ser descrito como una de la búsqueda de la mayor Berge-acíclico sub-hypergraph de un 3-uniforme hypergraph . En la versión hipergráfica del problema, los hiperbordes 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 bordes adicionales de un árbol de expansión , sin crear ningún ciclo nuevo, de modo que el subgráfico 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 subgráfico plano más grande de un gráfico dado, 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 mediante el uso de un árbol de expansión arbitrario. [5]
- Rigidez combinatoria
- Una estructura de barras rígidas en el plano euclidiano , conectadas en sus extremos en juntas flexibles, se puede fijar en una sola posición en el plano fijando algunas de sus juntas a puntos del plano. El número mínimo de juntas que se deben fijar para fijar la estructura se denomina número de fijación. Puede calcularse a partir de una solución a un problema de paridad matroide asociado. [3]
- Incrustaciones de género máximo
Se puede obtener una incrustación celular de un gráfico dado en una superficie del máximo género 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 bordes que no están en el árbol, el número de componentes conectados con un número impar de bordes 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 otros bordes incidentes a . 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 los bordes emparejados del gráfico subdividido, utilizando su matroide cográfico (un matroide lineal en el que un subconjunto de bordes 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]
- Dominación conectada
- Un conjunto dominante conectado en un gráfico es un subconjunto de vértices cuyo subgráfico 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áficas arbitrarias, pero se puede encontrar en tiempo polinómico para gráficas de máximo grado 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 extremos y formular un problema de paridad matroide en los pares de aristas generados 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 conectado mínimo. En una gráfica de máximo grado tres, 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] 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 máximo grado tres. [7]
Dureza
El problema de la camarilla , de encontrar un-vertex completo subgrafo en un dado-Gráfico de vértice , se puede transformar en una instancia de paridad matroide de la siguiente manera. Construya una matroide de pavimentación enelementos, emparejados para que haya un par de elementos por par de vértices. Definir un subconjunto de estos elementos para ser independiente si satisface cualquiera de las siguientes tres condiciones:
- tiene menos de elementos.
- tiene exactamente elementos, pero no es la unión de pares de elementos.
- es la unión de pares de elementos que forman una camarilla en .
Entonces hay una solución al problema de paridad matroide para esta matroide, de tamaño , si y solo si tiene una camarilla de tamaño . Dado que encontrar camarillas de un tamaño dado es NP-completo, se deduce que determinar si este tipo de problema de paridad matricial tiene una solución de tamañotambién es NP-completo. [13]
Esta transformación del problema no depende de la estructura del problema de la camarilla de ninguna manera profunda, y funcionaría para cualquier otro problema de encontrar tamaño.subconjuntos de un conjunto más grande que satisfacen una prueba computable. Aplicándolo a un gráfico permutado aleatoriamente que contiene exactamente un grupo de tamaño, se puede demostrar que cualquier algoritmo determinista o aleatorio para la paridad matroide que acceda a su matroide solo mediante pruebas de independencia necesita realizar un número exponencial de pruebas. [4]
Referencias
- ^ a b c d e f g h i j Cheung, Ho Yee; Lau, Lap Chi; Leung, Kai Man (2014), "Algoritmos algebraicos para problemas de paridad matroide lineal" (PDF) , ACM Transactions on Algorithms , 10 (3): 10: 1–10: 26, CiteSeerX 10.1.1.194.604 , doi : 10.1145 / 2601066 , MR 3233690 , S2CID 894004
- ^ a b c d Lawler, Eugene L. (1976), "Capítulo 9: El problema de la paridad matroide" , Optimización combinatoria: redes y matroides , Nueva York: Holt, Rinehart y Winston, págs. 356–367, MR 0439106
- ^ a b c 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 , MR 0572475
- ^ a b Jensen, Per M .; Korte, Bernhard (1982), "Complejidad de los algoritmos de propiedad matroide", SIAM Journal on Computing , 11 (1): 184-190, doi : 10.1137 / 0211014 , MR 0646772
- ^ a b Călinescu, Gruia; Fernandes, Cristina G .; Finkler, Ulrich; Karloff, Howard (1998), "Un mejor algoritmo de aproximación para encontrar subgráficos planos", Journal of Algorithms , 27 (2): 269–302, CiteSeerX 10.1.1.47.4731 , doi : 10.1006 / jagm.1997.0920 , MR 1622397 , S2CID 8329680.
- ^ a b Furst, Merrick L .; Gross, Jonathan L .; McGeoch, Lyle A. (1988), "Finding a maximum-genus graph imbedding", Journal of the ACM , 35 (3): 523–534, doi : 10.1145 / 44483.44485 , MR 0963159 , S2CID 17991210
- ^ a b c Ueno, Shuichi; Kajitani, Yoji; Gotoh, Shin'ya (1988), "Sobre el problema de conjuntos independientes sin separación y el problema de conjuntos de retroalimentación para gráficos sin 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 , MR 0975556
- ^ a b Lee, Jon; Sviridenko, Maxim; Vondrák, Jan (2013), "Matroid matching: the power of local search", SIAM Journal on Computing , 42 (1): 357–379, CiteSeerX 10.1.1.600.4878 , doi : 10.1137 / 11083232X , MR 3033132
- ^ 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, doi : 10.1145 / 2608628.2608664 , ISBN 9781450325011, MR 3239939 , S2CID 2597483
- ^ Geelen, James ; Iwata, Satoru (2005), "Emparejamiento de matrices mediante matrices mixtas simétricas sesgadas", Combinatorica , 25 (2): 187–215, CiteSeerX 10.1.1.702.5431 , doi : 10.1007 / s00493-005-0013-7 , MR 2127610 , S2CID 18576135
- ^ Gabow, Harold N .; Stallmann, Matthias (1985), "Algoritmos eficientes para la intersección y paridad de matroides gráficas (resumen extendido)", en Brauer, Wilfried (ed.), XII Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP), Nafplion, Grecia, julio 15-19, 1985 , Lecture Notes in Computer Science, 194 , Berlín: Springer, págs. 210-220, doi : 10.1007 / BFb0015746 , ISBN 978-3-540-15650-5, MR 0819256
- ^ 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 Ciencias de la Computación, vol. I, II (Győr, 1983) , Colloquia Mathematica Societatis János Bolyai, 42 , Amsterdam: North-Holland, págs. 719–729, MR 0875903
- ^ Soto, José A. (2014), "Un simple PTAS para el emparejamiento de matroides ponderados 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 , MR 3159127