Vertex-disjoint path covers in graphs
Resumo
Seja G um grafo conexo e P um conjunto de caminhos disjuntos nos vértices em G. Dizemos que P é uma cobertura por caminhos se cada vértice de G pertence a algum caminho em P. No problema da cobertura mínima por caminhos, o objetivo é encontrar uma cobertura com o menor número de caminhos. Nesse problema, que é sabido ser NP-difícil, o conjunto P pode conter caminhos triviais. Estudamos uma variante desse problema onde o objetivo é encontrar uma cobertura sem caminhos triviais. Usando a decomposição de Edmonds-Gallai, mostramos que o problema de decidir se um grafo tem tal cobertura pode ser reduzido a um problema de emparelhamento em um grafo bipartido. Além disso, mostramos resultados de inaproximabilidade para ambos os problemas de cobertura: com e sem caminhos triviais.
Referências
Arikati, S. R. and Pandu Rangan, C. (1990). Linear algorithm for optimal path cover problem on interval graphs. Inform. Process. Lett., 35(3):149–153.
Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedy, M. (1998). Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555.
Corneil, D. G., Dalton, B., and Habib, M. (2013). LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs. SIAM J. Comput., 42(3):792–807.
Damaschke, P. (1989). The Hamiltonian circuit problem for circle graphs is NP-complete. Inform. Process. Lett., 32(1):1–2.
Franzblau, D. S. and Raychaudhuri, A. (2002). Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow. ANZIAM J., 44(2):193–204.
Garey, M., Johnson, D., and Tarjan, R. (1976). The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput., 5(4):704–714.
Heinrich, K., Hell, P., Kirkpatrick, D., and Liu, G. (1990). A simple existence criterion for (g < f)-factors. Discrete Math., 85(3):313–317.
Las Vergnas, M. (1978). An extension of Tutte’s 1-factor theorem. Discrete Math., 23(3):241–255.
Lovász, L. (1970). Subgraphs with prescribed valencies. J. Combin. Theory, 8:391–416.
Lovász, L. and Plummer, M. D. (1986). Matching theory, volume 121 of North-Holland Mathematics Studies. North-Holland Publishing Co., Amsterdam; North-Holland Publishing Co., Amsterdam. Annals of Discrete Mathematics, 29.
Moran, S. and Wolfstahl, Y. (1991). Optimal covering of cacti by vertex-disjoint paths. Theoret. Comput. Sci., 84(2, Algorithms Automat. Complexity Games):179–197.
Müller, H. (1996). Hamiltonian circuits in chordal bipartite graphs. Discrete Math., 156(1-3):291–298.
Papadimitriou, C. H. and Yannakakis, M. (1993). The traveling salesman problem with distances one and two. Math. Oper. Res., 18(1):1–11.
