Vertex-disjoint path covers in graphs

• Renzo Gómez USP

DOI: https://doi.org/10.5753/etc.2017.3205

Abstract

Let G be a connected graph and P be a set of pairwise vertex-disjoint paths in G. We say that P is a path cover if every vertex of G belongs to a path in P. The minimum path cover problem asks for a path cover of minimum cardinality. In this problem, known to be NP-hard, the set P may contain trivial (single-vertex) paths. We study a variant of this problem in which the objective is to find a path cover without trivial paths. Using the well-known Edmonds-Gallai decomposition, we show that deciding whether a graph contains such kind of path cover can be reduced to a matching problem on a bipartite graph. We also show hardness and inapproximability results for both problems.

References

Anstee, R. (1985). An algorithmic proof of Tutte’s f-factor theorem. J. Algorithms, 6(1):112–131.

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.