intersección matroide

Conjunto independiente compartido de dos matroides.

En optimización combinatoria , el problema de intersección de matroides consiste en encontrar el conjunto independiente común más grande en dos matroides sobre el mismo conjunto de terreno. Si a los elementos de la matroide se les asignan pesos reales, el problema de intersección de matroides ponderadas es encontrar un conjunto independiente común con el máximo peso posible. Estos problemas generalizan muchos problemas de optimización combinatoria, incluida la búsqueda de coincidencias máximas y coincidencias de peso máximo en gráficos bipartitos y la búsqueda de arborescencias en gráficos dirigidos .

El teorema de intersección de matroides , debido a Jack Edmonds , ^[1] dice que siempre hay un certificado de límite superior simple, que consiste en una partición del terreno establecido entre las dos matroides, cuyo valor (suma de rangos respectivos ) es igual al tamaño de una 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 polinómico utilizando algoritmos de partición de matroides .

Ejemplos

Sea G  = ( U , V , E ) un gráfico bipartito . Se puede definir una matroide de partición _MU en el conjunto básico E , en el que un conjunto de aristas es independiente si no hay dos aristas que tengan el mismo punto final en U. De manera similar , se puede definir una matroide M _V en la que un conjunto de aristas es independiente si no hay dos 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 una coincidencia . Por lo tanto, el conjunto independiente común más grande de M U _y M V _es una coincidencia máxima 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 un peso máximo coincidente en G .

Algoritmos

Existen varios algoritmos de tiempo polinomial para la intersección de matroides ponderadas, 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 las 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 ). ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle T}$ ${\displaystyle k}$ ${\displaystyle 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. ${\displaystyle O(n^{3}T)}$
• Algoritmo de Orlin y Vande-Vate. ^[5]
• El algoritmo de Cunningham ^[6] requiere operaciones en matroides generales y operaciones en matroides lineales , para dos matrices r -by- n . ${\displaystyle O(r^{1.5}nT)}$ ${\displaystyle O(nr^{2}\log {r})}$
• Brezovec, Cornuejos y Glover ^[7] presentan dos algoritmos para la intersección matroide ponderada.
  • El primer algoritmo requiere que todos los pesos sean números enteros y encuentra una intersección de cardinalidad en el tiempo . ${\displaystyle 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 ponderadas se puede resolver resolviendo W instancias del problema de intersección de matroides no ponderadas, donde W es el mayor peso dado, 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 e -solución aproximada resolviendo instancias del problema de intersección de matroides no ponderadas, donde r es el rango más pequeño de las 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 matroide 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.

Extensiones

Maximizar el peso sujeto a cardinalidad

En una variante de intersección matroide ponderada, llamada "(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 dicho conjunto existe. Esta variante también se puede resolver en tiempo polinomial. ^[7]

tres matroides

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 gráficos dirigidos . Dado un gráfico dirigido G con n vértices y nodos s y t especificados , el problema de la ruta hamiltoniana es el problema de determinar si existe una ruta 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 de entrada yt no tiene aristas de salida. Entonces, existe una ruta hamiltoniana si y solo si hay un conjunto de n  − 1 elementos en la intersección de tres matroides en el conjunto de bordes del gráfico: dos matroides de partición que garantizan que el grado de entrada y salida del borde seleccionado ambos son como máximo uno, y la matroide gráfica del gráfico no dirigido se forma al olvidar las orientaciones de los bordes en G , asegurando que el conjunto de bordes seleccionado no tenga ciclos. ^[11]

paridad matroide

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 coincidencia de gráficos no bipartitos. Sin embargo, aunque se puede resolver en tiempo polinomial para matroides lineales , es NP-difícil para otras matroides y requiere tiempo exponencial en el modelo de oráculo matroide . ^[13]

matroides valoradas

Una matroide valorada es una matroide equipada con una función de valor v en el conjunto de sus bases, con la siguiente propiedad de intercambio : para dos bases distintas cualesquiera y , si , entonces existe un elemento tal que ambas y son bases, y :. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle a\in A\setminus B}$ ${\displaystyle b\in B\setminus A}$ ${\displaystyle (A\setminus \{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 gráfico bipartito ponderado G = ( X + Y , E ) y dos matroides valoradas, una en X con bases establecidas B _X y valoración v _X , y otra en Y con bases B _Y y valoración v _Y , el problema de asignación independiente valorada es el problema de encontrar una M coincidente en G , tal que M _X (el subconjunto de X coincidente con M ) sea 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 matroide ponderada es un caso especial en el que las valoraciones 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)}$

Ver también

• Partición matroide : un problema relacionado.

Referencias

1. Edmonds, Jack (1970), "Funciones submodulares, matroides y ciertos poliedros", en R. Guy; H. Hanam; N. Sauer; J. Schonheim (eds.), Estructuras combinatorias y sus aplicaciones (Proc. Conferencia de Calgary de 1969) , Gordon y Breach, Nueva York, págs.. Reimpreso en M. Jünger et al. (Eds.): Optimización combinatoria (Edmonds Festschrift), LNCS 2570, págs. 1126, Springer-Verlag, 2003.
2. Lawler, Eugene L. (1975), "Algoritmos de intersección matroide", Programación matemática , 9 (1): 31–56, doi :10.1007/BF01681329, S2CID  206801650
3. Iri, Masao; Tomizawa, Nobuaki (1976). "Un algoritmo para encontrar una" asignación independiente óptima"".日本オペレーションズ・リサーチ学会論文誌. 19 (1): 32–57. doi : 10.15807/jorsj.19.32 .
4. Frank, András (1981), "Un algoritmo de intersección matroide ponderado", Journal of Algorithms , 2 (4): 328–336, doi :10.1016/0196-6774(81)90032-8
5. Orlin, James B.; VandeVate, John (1983). Sobre un algoritmo de intersección matroide "primario" (Documento de trabajo n.° 1446-83 de la Sloan School of Management). hdl :1721.1/2050.
6. Cunningham, William H. (1 de noviembre de 1986). "Límites mejorados para algoritmos de intersección y partición matroide". Revista SIAM de Computación . 15 (4): 948–957. doi :10.1137/0215066. ISSN  0097-5397.
7. Brezovec, Carl; Cornuéjols, Gérard ; Glover, Fred (1986), "Dos algoritmos para la intersección matroide ponderada", Programación matemática , 36 (1): 39–53, doi :10.1007/BF02591988, S2CID  34567631
8. Huang, Chien-Chung; Kakimura, Naonori; Kamiyama, Naoyuki (1 de septiembre de 2019). "Algoritmos exactos y de aproximación para la intersección matroide ponderada". Programación Matemática . 177 (1): 85-112. doi :10.1007/s10107-018-1260-x. hdl : 2324/1474903 . ISSN  1436-4646. S2CID  254138118.
9. Ghosh, Sumanta; Gurjar, Rohit; Raj, Roshan (1 de enero de 2022), "Una reducción paralela determinista desde la búsqueda de intersección matroide ponderada hasta la decisión", Actas del Simposio anual ACM-SIAM de 2022 sobre algoritmos discretos (SODA) , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 1013–1035, doi :10.1137/1.9781611977073.44, ISBN 978-1-61197-707-3, S2CID  245799113 , consultado el 28 de noviembre de 2022
10. Bérczi, Kristóf; Király, Tamás; Yamaguchi, Yutaro; Yokoi, Yu (28 de septiembre de 2022). "Intersección matroide bajo oráculos restringidos". arXiv : 2209.14516 [cs.DS].
11. Welsh, DJA (2010) [1976], Teoría matroide , Publicaciones Courier Dover, pág. 131, ISBN 9780486474397.
12. 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.
13. 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.
14. Murota, Kazuo (1 de noviembre de 1996). "Intersección matroide valorada I: criterios de optimización". Revista SIAM de Matemática Discreta . 9 (4): 545–561. doi :10.1137/S0895480195279994. ISSN  0895-4801.
15. Murota, Kazuo (noviembre de 1996). "Intersección matroide valorada II: algoritmos". Revista SIAM de Matemática Discreta . 9 (4): 562–576. doi :10.1137/S0895480195280009. ISSN  0895-4801.

Otras lecturas

• Aigner, Martín; Dowling, Thomas (1971), "Teoría de correspondencias 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 ampliada de problemas de intersección de matroides" (PDF) , SIAM Journal on Computing , 18 (1): 112–138, doi :10.1137/0218008, archivado desde 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..