Ciclo impar transversal

Un gráfico con una transversal de ciclo impar de tamaño 2: al eliminar los dos vértices inferiores azules se obtiene un gráfico bipartito.

En teoría de grafos , una transversal de ciclo impar de un grafo no dirigido es un conjunto de vértices del grafo que tiene una intersección no vacía con cada ciclo impar en el grafo. Al eliminar los vértices de una transversal de ciclo impar de un grafo, queda un grafo bipartito como el subgrafo inducido restante . ^[1]

Relación con la cobertura del vértice

Un grafo -vértice dado tiene una transversal de ciclo impar de tamaño , si y solo si el producto cartesiano de grafos (un grafo que consiste en dos copias de , con vértices correspondientes de cada copia conectados por los bordes de un ) tiene una cobertura de vértices de tamaño . La transversal de ciclo impar se puede transformar en una cobertura de vértices al incluir ambas copias de cada vértice de la transversal y una copia de cada vértice restante, seleccionado de las dos copias según qué lado de la bipartición lo contiene. En la otra dirección, una cobertura de vértices de se puede transformar en una transversal de ciclo impar al mantener solo los vértices para los cuales ambas copias están en la cobertura. Los vértices fuera de la transversal resultante se pueden biparticionar según qué copia del vértice se usó en la cobertura. ^[1] ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G\square K_{2}}$ ${\displaystyle G}$ ${\displaystyle n+k}$ ${\displaystyle G\square K_{2}}$

Algoritmos y complejidad

El problema de encontrar el ciclo impar transversal más pequeño, o equivalentemente el subgrafo inducido bipartito más grande, también se llama ciclo impar transversal y se abrevia como OCT. Es NP-hard , como un caso especial del problema de encontrar el subgrafo inducido más grande con una propiedad hereditaria (ya que la propiedad de ser bipartito es hereditaria). Todos estos problemas para propiedades no triviales son NP-hard. ^{[2] [3]}

La equivalencia entre los problemas transversales de ciclo impar y de cobertura de vértices se ha utilizado para desarrollar algoritmos manejables con parámetros fijos para transversales de ciclo impar, lo que significa que hay un algoritmo cuyo tiempo de ejecución puede limitarse mediante una función polinómica del tamaño del grafo multiplicado por una función mayor de . El desarrollo de estos algoritmos condujo al método de compresión iterativa , una herramienta más general para muchos otros algoritmos parametrizados. ^[1] Los algoritmos parametrizados conocidos para estos problemas toman un tiempo casi lineal para cualquier valor fijo de . ^[4] Alternativamente, con dependencia polinómica del tamaño del grafo, la dependencia de puede hacerse tan pequeña como . ^[5] Por el contrario, el problema análogo para grafos dirigidos no admite un algoritmo manejable con parámetros fijos bajo supuestos teóricos de complejidad estándar. ^[6] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 2.3146^{k}}$

Véase también

• Corte máximo , equivalente a pedir un conjunto mínimo de aristas cuya eliminación deja un grafo bipartito

Referencias

1. Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015), Algoritmos parametrizados , Springer, págs. 64–65, doi :10.1007/978-3-319-21275-3, ISBN 978-3-319-21274-6, Sr.  3380745
2. Garey, Michael R .; Johnson, David S. (1979), "GT21: Subgrafo inducido con propiedad Π", Computadoras e intratabilidad: una guía para la teoría de la NP-completitud , WH Freeman, pág. 195
3. Yannakakis, Mihalis (1978), "Problemas NP-completos con eliminación de nodos y aristas", Actas del 10º Simposio ACM sobre teoría de la computación (STOC '78) , págs. 253-264, doi : 10.1145/800133.804355
4. Kawarabayashi, Ken-ichi ; Reed, Bruce (2010), "Un algoritmo de tiempo (casi) lineal para ciclos impares transversales", Actas del vigésimo primer simposio anual ACM-SIAM sobre algoritmos discretos , Filadelfia, PA: SIAM, págs. 365–378, CiteSeerX 10.1.1.215.2581 , doi :10.1137/1.9781611973075.31, ISBN  978-0-89871-701-3, Sr.  2809682
5. Lokshtanov, Daniel; Narayanaswamy, NS; Raman, Venkatesh; Ramanujan, MS; Saurabh, Saket (2014), "Algoritmos parametrizados más rápidos utilizando programación lineal", ACM Transactions on Algorithms , 11 (2): Art. 15, 31, arXiv : 1203.0833 , doi : 10.1145/2566616, MR  3283570
6. Lokshtanov, Daniel; Ramanujan, MS; Saurabh, Saket; Zehavi, Meirav (2017), Complejidad parametrizada y aproximabilidad de la transversal de ciclo impar dirigida , arXiv : 1704.04249 , Bibcode :2017arXiv170404249L