# Has this generalization of the vertex cover problem been researched?

I have the following problem, let's call it the $n$ vertex cover:

Given a directed graph $G,$ find a minimum subset of vertices $S$ such that each trail of length $n$ has at least one vertex in $S$.

Has this problem been researched before? Is there a good way to approximate $S$?

A trail is a walk in which no edge appears twice, but vertices are allowed to repeat. I am also interested in variants where we consider paths or walks instead of trails. Here $n$ is a small constant that is not part of the input; in my application, $n$ is probably something like 5.

• Is the problem "given a graph, determine whether it has an n-trail" in P? If so, there is a poly-time n-approximation alg for your problem: Find any n-trail in your graph, delete all vertices on it, and repeat until no n-trail remains. Finally return the deleted vertices. – Neal Young Jan 9 '17 at 19:30
• For constant n the n-approximation is in poly time, FWIW. For non-constant n, even determining whether there is any n-trail to be covered (i.e., determining whether zero vertices suffice) is NP-complete (at least, in directed graphs, by reduction from the Hamiltonian path problem). – Neal Young Jan 9 '17 at 23:18
• @NealYoung For constant n, can we do better than an n-approximation? – FUZxxl Jan 9 '17 at 23:44
• See the original copy on CS.SE for another relevant comment from Neal Young. – D.W. Jan 25 '17 at 22:03
• Sorry for being a bit pedantic here, but did you mean to say minimum instead of minimal? You can find a minimal set in polynomial time by starting with the whole graph and removing vertices until you can't anymore (without violating the desired property). – Mikhail Rudoy Jan 25 '17 at 22:43

This problem has been studied at least for paths. The problem is NP-complete for any $n \geq 2$ (see for example this).

It is know that the problem is hard even for very special graph classes. For example, in the case $n = 3$, it is NP-hard for cubic planar graphs of girth 3.

On the positive side, there are constant-factor approximations algorithms, at least for some special cases.

Every variant of your problem is NP-complete.

First some definitions in order to make the ideas in my proofs more concise:

I'm going to use the term length for a trail/path/walk to mean the number of edges in it. This is just to resolve ambiguity (i.e. I'm not talking about the length of the list of vertices comprising the trail/path/walk).

Define an $n$-trail, $n$-path, and an $n$-walk to be a trail, path, or walk respectively, of length $n$.

Define a vertex cover of $X$s in some directed graph $G$ to be a set of vertices such that every $X$ in $G$ contains at least one vertex in the set. For example, a vertex cover of 1-trails in $G$ is just a vertex cover of the undirected version of $G$.

The decision version of your problem, which I will refer to as the vertex cover of $X$s problem (for various $X$) takes as input a directed graph $G$ and a value $k$ and asks whether there exists a vertex cover of $X$s in $G$ of size at most $k$.

## vertex cover of $n$-walks is NP-complete for any constant $n \ge 1$

We reduce from vertex cover. The vertex cover instance is an undirected graph $G$ with a value $k$ such that the answer is "yes" if and only if there exists a vertex cover of size $\le k$. We construct directed graph $G'$ by including each edge from $G$ twice: once in each direction. Then the output instance of vertex cover of $n$-walks is $(G', k)$

First suppose that $G'$ contains some vertex cover of $n$-walks $S'$ with $|S'| \le k$. For every edge $(u,v)$ in $G$, there exists an $n$-walk in $G'$ that just goes back and forth between $u$ and $v$. $S'$ must contain a vertex from this $n$-walk, so $S'$ must contain a vertex in $(u,v)$. We have shown that $S'$ contains at least one endpoint of every edge of $G$ and has size $\le k$. Thus $G$ contains a vertex cover of size at most $k$ ($S'$ in particular).

Next suppose that $G$ contains some vertex cover $S$ with $|S| \le k$. Consider any $n$-walk in $G'$. Since $n \ge 1$, this walk includes both endpoints of some edge. Therefore this $n$-walk includes at least one vertex in $S$. Thus $G'$ contains a vertex cover of $n$-walks of size at most $k$ ($S$ in particular).

## vertex cover of $n$-trails and vertex cover of $n$-paths are NP-complete for any constant $n \ge 1$

We still reduce from vertex cover. Take as input the vertex cover instance $(G, k)$ and output $(G_n, k)$ where directed graph $G_n$ is defined as follows:

If $G = (V,E)$ then

• the vertices of $G_n$ are $V \times \{1, \ldots, n\}$
• for $v \in V$ and $i \in \{1, ..., n-1\}$, there is an edge in $G_n$ from $(v, i)$ to $(v, i+1)$
• if $(u, v)$ is an edge in $E$ then there is an edge in $G_n$ from $(u,1)$ to $(v,1)$ and another edge from $(v, 1)$ to $(u, 1)$

First suppose that $G$ has a vertex cover $S$ of size at most $k$. Construct $S' = \{(x, 1)~|~x \in S\}$. We claim that $S'$ is both a vertex cover of $n$-trails and a vertex cover of $n$-paths in $G_n$. Consider any $n$-trail or $n$-path in $G_n$. This $n$-trail or $n$-path must include some edge of the form $((u, 1), (v, 1))$ (this is because all of the other edges together form a set of disjoint $(n-1)$-paths, and it is therefore impossible to select an $n$-trail or $n$-path using just the other edges). Note that the existence of this edge in $G_n$ implies that $(u,v)$ is an edge in $G$. Therefore either $u$ or $v$ must be in $S$. Thus, either $(u,1)$ or $(v,1)$ must be in $S'$ and as a result at least one vertex of the $n$-trail or $n$-path is in $S'$. As desired, $S'$ is both a vertex cover of $n$-trails and a vertex cover of $n$-paths. Since $|S'| = |S| \le k$, this proves one direction of our proof.

Next suppose that $G_n$ has a vertex cover of $n$-trails or a vertex cover of $n$-paths $S'$ of size at most $k$. Let $S = \{x~|~(x, i) \in S'\text{ for some }i\}$. Consider any edge $(u,v)$ of $G$. The path $(u, 1), (v, 1), (v, 2), ..., (v, n)$ is both an $n$-trail and an $n$-path. Thus some vertex in this path is in $S'$. We can conclude that either $u$ or $v$ is in $S$. Thus we see that $S$ is a vertex cover in $G$. Furthermore, $|S| \le |S'| \le k$, so this concludes the proof.