0
$\begingroup$

Wikipedia gives the path cover definition as:

Given a directed graph $G = (V, E)$, a path cover is a set of directed paths such that every vertex $v \in V$ belongs to at least one path.

I'm reading the paper "On k-Path Covers and their Application" (Funke, S., Nusser, A., & Storandt, S. (2014)) and they gave the definition where we select a subset of vertices $C \subseteq V$ such that for every simple path $\pi$ in the graph we have that $C \cap \pi \neq \emptyset$. (There's also a $k$ constraint but it's not particularly relevant to my problem).

Are these definitions equivalent? One uses a set of vertices and the other uses a set of paths.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The definitions are not equivalent. Clearly, as you point out, one is a set of paths while the other is a set of vertices, but even their sizes are unrelated. In fact, since a single edge is a path, the second definition would be equivalent to saying that $C$ is a vertex cover.* If you want an explicit counterexample, think of a graph consisting of a path of length $2$.

From what I see at a quick glance, the paper studies $k$-Path covers. The $k$ here is critical, since a path $\pi$ needs to be covered by $C$ (i.e., it must contain at least one vertex in $C$) only if $\pi$ is a simple path containing at least $k-1$ edges (i.e., $k$ vertices).

* I'm actually disregarding paths with 0 edges here, otherwise the only feasibly set $C$ would be $V$ itself.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you. As a followup, the Wikipedia page also has a note that "path cover may also refer to vertex-disjoint path cover" - can we consider this restriction of exactly one to be equivalent to the more general problem of at least one? I think so, since we can just discard paths that would be covering vertices more than once. $\endgroup$
    – a6623
    Mar 9 at 20:58
  • $\begingroup$ No. You can cover a star with $4$ leaves with $2$ paths that intersect on the star center. If you want to use vertex-disjoint paths, then you need to select at least $3$ paths. $\endgroup$
    – Steven
    Mar 9 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.