En la optimización combinatoria , el problema de la intersección de matroides es encontrar un conjunto independiente común más grande en dos matroides sobre el mismo conjunto de bases. Si a los elementos de la matroide se les asignan pesos reales, el problema de la intersección ponderada de la matroide es encontrar un conjunto independiente común con el máximo peso posible. Estos problemas generalizan muchos problemas en la optimización combinatoria, incluida la búsqueda de coincidencias máximas y las coincidencias de peso máximo en gráficos bipartitos y la búsqueda de arborescencias en gráficos dirigidos .
El teorema de la intersección de matroides , debido a Jack Edmonds , dice que siempre hay un certificado de límite superior simple, que consiste en una partición del conjunto de suelo entre las dos matroides, cuyo valor (suma de rangos respectivos ) es igual al tamaño de un máximo común independiente independiente colocar. Con base en este teorema, el problema de intersección de matroides para dos matroides se puede resolver en tiempo polinomial usando algoritmos de partición de matroides .
Ejemplo
Sea G = ( U , V , E ) un gráfico bipartito . Uno puede definir una partición matroid M U en el conjunto de suelo E , en el que un conjunto de aristas es independiente si no dos de los bordes tienen el mismo punto final en U . Del mismo modo se puede definir una matroid M V en el que un conjunto de aristas es independiente si no dos de los bordes tienen 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 dos de sus aristas no comparten un punto final; es decir, es una coincidencia . Por lo tanto, el mayor conjunto independiente común de M U y M V es un juego máximo en G .
Extensión
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 sy termina en t . Se puede suponer sin pérdida de generalidad que s no tiene bordes entrantes y t no tiene bordes salientes. 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 el grado de salida del borde seleccionado conjunto son ambos a lo sumo uno, y el matroid gráfico del grafo no dirigido formado por olvidar las orientaciones de borde en G , asegurando que el borde conjunto seleccionado no tiene ciclos ( Welsh 2010 ).
Otro problema computacional en matroides, el problema de paridad matroide , fue formulado por Lawler (1976) como una generalización común de intersección matroide y coincidencia de grafos 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 ( Jensen y Korte 1982 ).
Referencias
- 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.
- 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.
- 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. 69–87. Reimpreso en M. Jünger et al. (Eds.): Optimización combinatoria (Edmonds Festschrift), LNCS 2570, págs. 1126, Springer-Verlag, 2003.
- 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.
- Frederickson, Greg N .; Srinivas, Mandayam A. (1989), "Algoritmos y estructuras de datos para una familia ampliada de problemas de intersección matroide" , SIAM Journal on Computing , 18 (1): 112-138, doi : 10.1137 / 0218008.
- 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.
- 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.
- Lawler, Eugene L. (1975), "Algoritmos de intersección matroide", Programación matemática , 9 (1): 31–56, doi : 10.1007 / BF01681329 , S2CID 206801650.
- 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.
- Galés, DJA (2010) [1976], Matroid Theory , Publicaciones de Courier Dover, p. 131, ISBN 9780486474397.