Emparejamiento inducido

En teoría de grafos , un emparejamiento inducido o emparejamiento fuerte es un subconjunto de las aristas de un grafo no dirigido que no comparten ningún vértice (es un emparejamiento ) y estas son las únicas aristas que conectan cualesquiera dos vértices que son puntos finales de las aristas de emparejamiento (es un subgrafo inducido ).

Un emparejamiento inducido también puede describirse como un conjunto independiente en el cuadrado del gráfico de líneas del gráfico dado. ^{[ 1 ]}

El número mínimo de emparejamientos inducidos en los que se pueden formar las aristas de un grafo.${\displaystyle G}$puede ser particionado se llama su índice cromático fuerte , denotado${\displaystyle \chi _{s}'(G)}$, por analogía con el índice cromático${\displaystyle \chi '(G)}$del grafo, el número mínimo de emparejamientos en los que se pueden particionar sus aristas. ^{[ 2 ]} Es igual al número cromático del cuadrado del grafo de líneas . El teorema de Brooks , aplicado al cuadrado del grafo de líneas, muestra que el índice cromático fuerte es como máximo cuadrático en el grado máximo del grafo dado, pero se pueden obtener mejores factores constantes en el límite cuadrático mediante otros métodos. ^{[ 3 ]}

El problema de Ruzsa-Szemerédi se refiere a la densidad de aristas de grafos bipartitos balanceados con índice cromático fuerte lineal. De forma equivalente, se refiere a la densidad de una clase diferente de grafos, los grafos localmente lineales en los que la vecindad de cada vértice es un emparejamiento inducido. ^{[ 4 ]} Ninguno de estos tipos de grafos puede tener un número cuadrático de aristas, pero se conocen construcciones para grafos de este tipo con números de aristas casi cuadráticos. ^{[ 5 ]}

Encontrar una coincidencia inducida de tamaño al menos${\displaystyle k}$es NP-completo (y, por lo tanto, encontrar un emparejamiento inducido de tamaño máximo es NP-difícil ). Se puede resolver en tiempo polinomial en grafos cordales , porque los cuadrados de los grafos de líneas de los grafos cordales son grafos perfectos . ^{[ 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 , el emparejamiento inducido más grande no se puede aproximar dentro de ningún${\displaystyle n^{1-\varepsilon }}$relación de aproximación en tiempo polinomial. ^{[ 8 ]}

El problema también es W[1]-difícil , lo que significa que incluso encontrar un emparejamiento inducido pequeño de un tamaño dado${\displaystyle k}$Es poco probable que exista un algoritmo significativamente más rápido que el enfoque de búsqueda por fuerza bruta de probar todos los métodos.${\displaystyle k}$-tuplas de aristas. ^{[ 9 ]} Sin embargo, el problema de encontrar${\displaystyle k}$vértices cuya eliminación deja un emparejamiento inducido es tratable con parámetros fijos . ^{[ 10 ]} El problema también se puede resolver exactamente en${\displaystyle n}$-grafos de vértices en el tiempo${\displaystyle O(1.3752^{n})}$con espacio exponencial o en tiempo${\displaystyle O(1.4231^{n})}$con espacio polinomial . ^{[ 11 ]}

• Trayectoria inducida