Nontrivial path covers of graphs: existence, minimization and maximization

Renzo Gómez () and Yoshiko Wakabayashi ()
Additional contact information
Renzo Gómez: University of São Paulo
Yoshiko Wakabayashi: University of São Paulo

Journal of Combinatorial Optimization, 2020, vol. 39, issue 2, No 9, 437-456

Abstract: Abstract Let G be a graph and $${{{\mathcal {P}}}}$$P be a set of pairwise vertex-disjoint paths in G. We say that $${{\mathcal {P}}}$$P is a path cover if every vertex of G belongs to a path in $${{\mathcal {P}}}$$P. In the minimum path cover problem, one wishes to find a path cover of minimum cardinality. In this problem, known to be $${\textsc {NP}}$$NP-hard, the set $${{\mathcal {P}}}$$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.

Keywords: Covering; Min path cover; Max path cover; [1; 2]-factor; Bounded treewidth (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00488-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:39:y:2020:i:2:d:10.1007_s10878-019-00488-w

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00488-w

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().