# Two formulations of path cover

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.

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.

• 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. Mar 9 at 20:58
• 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. Mar 9 at 21:00