Optimal covering of cacti by vertex-disjoint paths (Q1178689): Difference between revisions

A graph \(G\) is assumed to be undirected, with no loops or parallel edges. A path in \(G\) is a sequence of distinct vertices of \(G\) such that any two consecutive vertices of the sequence are adjacent in \(G\). A path cover of \(G\) is a set of vertex-disjoint paths which cover all the vertices of \(G\). An optimal cover of \(G\) is a path cover of the smallest possible cardinality. The problem of finding an optimal cover is \(NP\)-complete, even for cubic 3-connected planar graph [\textit{M. Garey}, \textit{D. Johnson} and \textit{R. E. Tarjan}, SIAM J. Computing 5, 704-714 (1976; Zbl 0346.05110)]. However, an efficient algorithm for finding an optimal cover of a tree was developed in \textit{F. T. Boesch}, \textit{S. Chen} and \textit{J. A. M. McHugh} [Lect. Notes Math. 406, 201-212 (1974)], and later this result was generalized to graphs in which no two cycles share a vertex [\textit{S. Pinter} and \textit{Y. Wolfstahl}, Int. J. Parallel Program. 16(1), 1-15 (1987; Zbl 0632.68029))]. The paper under review generalizes this result further -- to cacti, which are graphs in which no edge lies on more than one cycle. The algorithm derived here runs in linear time in the number of vertices of the input graph.