Intersección de matroides

En la optimización combinatoria , el problema de intersección de matroides consiste en encontrar el mayor conjunto común independiente en dos matroides sobre el mismo conjunto base. Si a los elementos del matroide se les asignan pesos reales, el problema de intersección de matroides ponderados consiste en encontrar un conjunto común independiente con el máximo peso posible. Estos problemas generalizan muchos problemas de la optimización combinatoria, entre ellos, la búsqueda de correspondencias máximas y correspondencias de peso máximo en grafos bipartitos y la búsqueda de arborescencias en grafos dirigidos .

El teorema de intersección de matroides , creado por Jack Edmonds ^[1], dice que siempre existe un límite superior simple, que consiste en una partición del conjunto base entre las dos matroides, cuyo valor (suma de los rangos respectivos ) es igual al tamaño de un conjunto independiente común máximo. Con base en este teorema, el problema de intersección de matroides para dos matroides se puede resolver en tiempo polinomial utilizando algoritmos de partición de matroides .

Sea G  = ( U , V , E ) un grafo bipartito . Se puede definir un matroide de partición M _U sobre el conjunto base E , en el que un conjunto de aristas es independiente si no hay dos de las aristas que tengan el mismo punto final en U . De manera similar, se puede definir un matroide M _V en el que un conjunto de aristas es independiente si no hay dos de las aristas que tengan el mismo punto final en V . Cualquier conjunto de aristas que sea independiente tanto en M _U como en M _V tiene la propiedad de que no hay dos de sus aristas que compartan un punto final; es decir, es un coincidente . Por lo tanto, el mayor conjunto independiente común de M _U y M _V es un coincidente máximo en G .

De manera similar, si cada borde tiene un peso, entonces el conjunto independiente de peso máximo de M _U y M _V es una coincidencia de peso máximo en G .

Existen varios algoritmos de tiempo polinomial para la intersección de matroides ponderados, con diferentes tiempos de ejecución. Los tiempos de ejecución se dan en términos de: - el número de elementos en el conjunto base común, - el máximo entre los rangos de los dos matroides, - el número de operaciones requeridas para un oráculo de búsqueda de circuitos , y - el número de elementos en la intersección (en caso de que queramos encontrar una intersección de un tamaño específico ). ${\estilo de visualización n}$${\estilo de visualización r}$${\estilo de visualización T}$${\estilo de visualización k}$${\estilo de visualización k}$

• El algoritmo de Edmonds utiliza programación lineal y poliedros. ^[1]
• Algoritmo de Lawler . ^[2]
• Algoritmo de Iri y Tomizawa ^[3]
• El algoritmo de Andras Frank ^[4] utiliza operaciones aritméticas.$Estilo de visualización O(n^{3}T)}$
• Algoritmo de Orlin y Vande-Vate. ^[5]
• El algoritmo de Cunningham ^[6] requiere operaciones sobre matroides generales y operaciones sobre matroides lineales , para dos matrices de r por n .$Estilo de visualización O(r^{1.5}nT)}$${\displaystyle O(nr^{2}\log {r})}$
• Brezovec, Cornuejos y Glover ^[7] presentan dos algoritmos para la intersección de matroides ponderadas.
  • El primer algoritmo requiere que todos los pesos sean números enteros y encuentra una intersección de cardinalidad en el tiempo .${\estilo de visualización k}$${\displaystyle O((n^{3}k^{2}+nkT)\cdot (1+\log {W}))}$
  • El segundo algoritmo se ejecuta en el tiempo .${\displaystyle O(nr\cdot (\log {n}+r+T))}$
• Huang, Kakimura y Kamiyama ^[8] muestran que el problema de intersección de matroides ponderados se puede resolver resolviendo W instancias del problema de intersección de matroides no ponderados, donde W es el peso dado más grande, asumiendo que todos los pesos dados son integrales. Este algoritmo es más rápido que los algoritmos anteriores cuando W es pequeño. También presentan un algoritmo de aproximación que encuentra una solución e -aproximada resolviendo instancias del problema de intersección de matroides no ponderados, donde r es el rango más pequeño de los dos matroides de entrada.${\displaystyle O(\epsilon ^{-1}\log {r})}$
• Ghosh, Gurjar y Raj ^[9] estudian la complejidad en tiempo de ejecución de la intersección de matroides en el modelo de computación paralela .
• Bérczi, Király, Yamaguchi y Yokoi ^[10] presentan algoritmos de tiempo fuertemente polinomial para la intersección de matroides ponderadas utilizando oráculos más restringidos.

En una variante de la intersección de matroides ponderada, denominada "(P _k )", el objetivo es encontrar un conjunto independiente común con el máximo peso posible entre todos los conjuntos con cardinalidad k , si tal conjunto existe. Esta variante también se puede resolver en tiempo polinomial. ^[7]

El problema de la intersección de matroides se vuelve NP-difícil cuando están involucradas tres matroides, en lugar de solo dos.

Una prueba de este resultado de dureza utiliza una reducción del problema de la trayectoria hamiltoniana en grafos dirigidos . Dado un grafo dirigido G con n vértices y nodos especificados s y t , el problema de la trayectoria hamiltoniana es el problema de determinar si existe una trayectoria simple de longitud n  − 1 que comienza en s y termina en t . Se puede suponer sin pérdida de generalidad que s no tiene aristas entrantes y t no tiene aristas salientes. Entonces, existe una trayectoria hamiltoniana si y solo si hay un conjunto de n  − 1 elementos en la intersección de tres matroides en el conjunto de aristas del grafo: dos matroides de partición que aseguran que el grado de entrada y el grado de salida del conjunto de aristas seleccionado sean ambos como máximo uno, y la matroide gráfica del grafo no dirigido formada olvidando las orientaciones de las aristas en G , asegurando que el conjunto de aristas seleccionado no tenga ciclos. ^[11]

Otro problema computacional sobre matroides, el problema de paridad de matroides , fue formulado por Lawler ^[12] como una generalización común de la intersección de matroides y la correspondencia de grafos no bipartitos. Sin embargo, aunque se puede resolver en tiempo polinomial para matroides lineales , es NP-hard para otros matroides y requiere tiempo exponencial en el modelo de oráculo de matroides . ^[13]

Un matroide valuado es un matroide equipado con una función de valor v en el conjunto de sus bases, con la siguiente propiedad de intercambio : para cualesquiera dos bases distintas y , si , entonces existe un elemento tal que ambos y son bases, y : . ${\estilo de visualización A}$${\estilo de visualización B}$${\displaystyle a\en A\setmenos B}$${\displaystyle b\en B\setmenos A}$${\displaystyle (A\setmenos \{a\})\cup \{b\}}$${\displaystyle (B\setminus \{b\})\cup \{a\}}$${\displaystyle v(A)+v(B)\leq v(B\setminus \{b\}\cup \{a\})+v(A\setminus \{a\}\cup \{b\} )}$

Dado un grafo bipartito ponderado G = ( X + Y , E ) y dos matroides valuados, uno en X con bases establecidas B _X y valuación v _X , y uno en Y con bases B _Y y valuación v _Y , el problema de asignación independiente valuado es el problema de encontrar un M coincidente en G , tal que M _X (el subconjunto de X coincidente con M ) es una base en B _X , M _Y es una base en B _Y , y sujeto a esto, la suma se maximiza. El problema de intersección de matroides ponderados es un caso especial en el que las valuaciones de los matroides son constantes, por lo que solo buscamos maximizar sujeto a que M _X es una base en B _X y M _Y es una base en B _Y . ^[14] Murota presenta un algoritmo de tiempo polinomial para este problema. ^[15]${\displaystyle w(M)+v_{X}(M_{X})+v_{Y}(M_{Y})}$${\displaystyle w(M)}$

• Particionamiento de matroides : un problema relacionado.

• Aigner, Martin; Dowling, Thomas (1971), "Teoría de emparejamiento para geometrías combinatorias", Transactions of the American Mathematical Society , 158 (1): 231–245, doi : 10.1090/S0002-9947-1971-0286689-5.
• Frederickson, Greg N.; Srinivas, Mandayam A. (1989), "Algoritmos y estructuras de datos para una familia expandida de problemas de intersección de matroides" (PDF) , SIAM Journal on Computing , 18 (1): 112–138, doi :10.1137/0218008, hdl :1802/6137, archivado desde el original el 22 de septiembre de 2017.
• Gabow, Harold N. ; Tarjan, Robert E. (1984), "Algoritmos eficientes para una familia de problemas de intersección de matroides", Journal of Algorithms , 5 (1): 80–131, doi :10.1016/0196-6774(84)90042-7..