En teoría de grafos , un ciclo impar transversal 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. Eliminar los vértices de un ciclo impar transversal de un gráfico deja un gráfico bipartito como el subgráfico inducido restante . [1]
Relación con la cobertura de vértices
Un dado -Gráfico de vértice tiene un ciclo impar transversal de tamaño , si y solo si el producto cartesiano de las gráficas (un gráfico que consta de dos copias de , con los vértices correspondientes de cada copia conectados por los bordes de una coincidencia perfecta ) tiene una cubierta de vértice de tamaño. La transversal de ciclo impar se puede transformar en una cubierta de vértice incluyendo ambas copias de cada vértice de la transversal y una copia de cada vértice restante, seleccionada de las dos copias según qué lado de la bipartición lo contenga. En la otra dirección, una cubierta de vértice dese puede transformar en un ciclo impar transversal manteniendo solo los vértices para los que ambas copias están en la portada. Los vértices fuera de la transversal resultante se pueden dividir en dos según qué copia del vértice se utilizó en la portada. [1]
Algoritmos y complejidad
El problema de encontrar la transversal de ciclo impar más pequeño, o de manera equivalente, el subgrafo inducido bipartito más grande, también se denomina transversal de ciclo impar y se abrevia como OCT. Es NP-difícil , 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-duros. [2] [3]
La equivalencia entre la transversal de ciclo impar y los problemas de cobertura de vértice se ha utilizado para desarrollar algoritmos manejables de parámetros fijos para la transversal de ciclo impar, lo que significa que existe un algoritmo cuyo tiempo de ejecución puede estar acotado por una función polinomial del tamaño del gráfico multiplicado por una función más grande 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 polinomial del tamaño del gráfico, la dependencia de se puede hacer tan pequeño como . [5] En contraste, el problema análogo para gráficos dirigidos no admite un algoritmo manejable de parámetros fijos bajo supuestos estándar de teoría de la complejidad. [6]
Ver también
- Corte máximo , equivalente a pedir un juego mínimo de aristas cuya eliminación deja un gráfico bipartito
Referencias
- ^ a b c Cygan, Marek; Fomin, Fedor V .; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Dániel; 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, MR 3380745
- ^ Garey, Michael R .; Johnson, David S. (1979), "GT21: Subgrafo inducido con propiedad Π", Computadoras e intratabilidad: Una guía para la teoría de NP-completitud , WH Freeman, p. 195
- ^ Yannakakis, Mihalis (1978), "Problemas NP-completos de eliminación de nodos y bordes", Actas del décimo Simposio ACM sobre Teoría de la Computación (STOC '78) , págs. 253-264, doi : 10.1145 / 800133.804355
- ^ 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, MR 2809682
- ^ Lokshtanov, Daniel; Narayanaswamy, NS; Raman, Venkatesh; Ramanujan, MS; Saurabh, Saket (2014), "Algoritmos parametrizados más rápidos usando programación lineal", Transacciones ACM sobre Algoritmos , 11 (2): Art. 15, 31, arXiv : 1203.0833 , doi : 10.1145 / 2566616 , MR 3283570
- ^ Lokshtanov, Daniel; Ramanujan, MS; Saurabh, Saket; Zehavi, Meirav (2017), Complejidad parametrizada y aproximabilidad de ciclo impar dirigido transversal , arXiv : 1704.04249 , Bibcode : 2017arXiv170404249L