Nontrivial path covers of graphs: existence, minimization and maximization

Author(s)

Gomez, Renzo ^[1] ; Wakabayashi, Yoshiko ^[1]

Affiliation

^[1] Univ Sao Paulo, Inst Math & Stat, Rua Matao 1010, BR-05508090 Sao Paulo, SP - Brazil

• Document type: Journal article
• Source: JOURNAL OF COMBINATORIAL OPTIMIZATION; NOV 2019.
• Web of Science Citations: 0

Abstract

LetG be a graph andP be a set of pairwise vertex-disjoint paths inG. We say thatP is a path cover if every vertex of G belongs to a path inP. In the minimum path cover problem, one wishes to find a path cover ofminimum cardinality. In this problem, known to be NP-hard, the set P may contain trivial (single-vertex) paths. We study the problem of finding a path cover composed only of nontrivial paths. First, we show that the corresponding existence problem can be reduced to a matching problem. This reduction gives, in polynomial time, a certificate for both the yes-answer and the no-answer. When trivial paths are forbidden, for the feasible instances, one may consider either minimizing or maximizing the number of paths in the cover. We show that, the minimization problem on feasible instances is computationally equivalent to the minimum path cover problem: their optimum values coincide and they have the same approximation threshold. We show that the maximization problem can be solved in polynomial time. We also consider a weighted version of the path cover problem, in which we seek a path cover with minimum or maximum total weight (the number of paths do not matter), and we show that while the first is polynomial, the second is NP-hard, but admits a constant-factor approximation algorithm. We also describe a linear-time algorithm on (weighted) trees, and mention results for graphs with bounded treewidth. (AU)

• FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
• Grantee: Flávio Keidi Miyazawa
• Support Opportunities: Research Projects - Thematic Grants