En la teoría de grafos , una coincidencia inducida o una coincidencia fuerte es un subconjunto de los bordes de un gráfico no dirigido que no comparte ningún vértice (es un emparejamiento ) e incluye cada borde que conecta dos vértices cualesquiera en el subconjunto (es un subgrafo inducido ) .
Una coincidencia inducida también se puede describir como un conjunto independiente en el cuadrado del gráfico lineal del gráfico dado. [1]
Colores fuertes y vecindarios.
El número mínimo de emparejamientos inducidos en los que se pueden dividir los bordes de un gráfico se denomina índice cromático fuerte , por analogía con el índice cromático del gráfico, el número mínimo de emparejamientos en los que se pueden dividir sus bordes. [2] Es igual al número cromático del cuadrado del gráfico lineal. El teorema de Brooks , aplicado al cuadrado del gráfico lineal, muestra que el índice cromático fuerte es a lo sumo cuadrático en el grado máximo del gráfico dado, pero se pueden obtener mejores factores constantes en el límite cuadrático por otros métodos. [3]
El problema de Ruzsa-Szemerédi se refiere a la densidad de los bordes de los gráficos bipartitos equilibrados con un fuerte índice cromático lineal. De manera equivalente, se refiere a la densidad de una clase diferente de gráficos, los gráficos localmente lineales en los que la vecindad de cada vértice es una coincidencia inducida. [4] Ninguno de estos tipos de gráficos puede tener un número cuadrático de aristas, pero se conocen construcciones para gráficos de este tipo con números de aristas casi cuadráticos. [5]
Complejidad computacional
Encontrar una coincidencia inducida de tamaño al menos es NP-completo (y por lo tanto, encontrar una coincidencia inducida de tamaño máximo es NP-difícil ). Se puede resolver en tiempo polinomial en gráficas cordales , porque los cuadrados de las gráficas lineales de las gráficas cordales son gráficas perfectas . [6] Además, se puede resolver en tiempo lineal en grafos cordales [7] . A menos que ocurra un colapso inesperado en la jerarquía polinomial , la mayor coincidencia inducida no se puede aproximar dentro de ningún Relación de aproximación en tiempo polinomial. [8]
El problema también es W [1] -hard , lo que significa que incluso encontrar una pequeña coincidencia inducida de un tamaño dadoEs poco probable que tenga un algoritmo significativamente más rápido que el enfoque de búsqueda de fuerza bruta de probar todos-tuplas de aristas. [9] Sin embargo, el problema de encontrarvértices cuya eliminación deja una coincidencia inducida es manejable con parámetros fijos . [10] El problema también se puede resolver exactamente en-Gráficos de vértice en el tiempo con espacio exponencial, o en el tiempo con espacio polinomial . [11]
Ver también
Referencias
- ^ Cameron, Kathie (2004), "Emparejamientos inducidos en gráficos de intersección", Matemáticas discretas , 278 (1-3): 1-9, doi : 10.1016 / j.disc.2003.05.001 , MR 2035386
- ^ Fouquet, J.-L .; Jolivet, J.-L. (1983), "Fuerte coloración de bordes de gráficos y aplicaciones a múltiples k - gones", Ars Combinatoria , 16 (A): 141-150, MR 0737086
- ^ Molloy, Michael; Reed, Bruce (1997), "Un límite en el fuerte índice cromático de un gráfico", Journal of Combinatorial Theory , Serie B, 69 (2): 103–109, doi : 10.1006 / jctb.1997.1724 , hdl : 1807/9474 , Señor 1438613
- ^ Fronček, Dalibor (1989), "Gráficos localmente lineales", Mathematica Slovaca , 39 (1): 3–6, hdl : 10338.dmlcz / 136481 , MR 1016323
- ^ Ruzsa, IZ ; Szemerédi, E. (1978), "Sistemas triples sin seis puntos que llevan tres triángulos", Combinatoria (Proc. Quinto Coloquio Húngaro, Keszthely, 1976), vol. II , Coloq. Matemáticas. Soc. János Bolyai, 18 , Amsterdam y Nueva York: North-Holland, págs. 939–945, MR 0519318
- ^ Cameron, Kathie (2008), "Máximas coincidencias inducidas para gráficos de cuerdas en tiempo lineal", número especial para la Primera Conferencia de Montreal sobre Combinatoria y Ciencias de la Computación, 1987, Algorithmica , 52 : 440–447, doi : 10.1016 / 0166-218X (92 ) 90275-F , MR 1011265
- ^ Brandstaedt, Andreas; Hoang, Chinh (1989), "Emparejamientos inducidos", Matemáticas aplicadas discretas , 24 (1-3): 97-102, doi : 10.1007 / s00453-007-9045-2
- ^ Chalermsook, Parinya; Laekhanukit, Bundit; Nanongkai, Danupon (2012), "Productos gráficos revisitados: dureza de aproximación ajustada del emparejamiento inducido, dimensión poset y más", Actas del vigésimo cuarto simposio anual ACM-SIAM sobre algoritmos discretos , Filadelfia, Pensilvania: SIAM, págs. 1557– 1576, MR 3202998
- ^ Moser, Hannes; Sikdar, Somnath (2009), "La complejidad parametrizada del problema de emparejamiento inducido", Matemáticas aplicadas discretas , 157 (4): 715–727, doi : 10.1016 / j.dam.2008.07.011 , MR 2499485
- ^ Xiao, Mingyu; Kou, Shaowei (2016), "Coincidencia casi inducida: núcleos lineales y algoritmos parametrizados", en Heggernes, Pinar (ed.), Graph-Theoretic Concepts in Computer Science: 42nd International Workshop, WG 2016, Estambul, Turquía, 22 de junio - 24, 2016, Revised Selected Papers , Lecture Notes in Computer Science, 9941 , Berlín: Springer, págs. 220–232, doi : 10.1007 / 978-3-662-53536-3_19 , MR 3593958
- ^ Xiao, Mingyu; Tan, Huan (2017), "Algoritmos exactos para la máxima coincidencia inducida", Información y cálculo , 256 : 196–211, doi : 10.1016 / j.ic.2017.07.006 , MR 3705425