<p>This problem has been studied at least for paths. The problem is NP-complete for any $n \geq 2$ (see for example <a href="http://www.sciencedirect.com/science/article/pii/S0020019014001446" rel="nofollow noreferrer">this</a>). </p>

<p>It is know that the problem is hard even for very special graph classes. For example, in the case $n = 3$, it is <a href="http://www.sciencedirect.com/science/article/pii/S0020019013001130" rel="nofollow noreferrer">NP-hard for cubic planar graphs of girth 3</a>.</p>

<p>On the positive side, there are constant-factor <a href="http://www.tandfonline.com/doi/abs/10.1080/00207160.2014.881476?journalCode=gcom20" rel="nofollow noreferrer">approximations algorithms</a>, at least for some special cases.</p>

CC BY-SA 3.0
2017-02-22T22:29:03.590Z
2017-02-22T22:29:03.590Z
Vinicius dos Santos
<p>Every variant of your problem is NP-complete.</p>

<p>First some definitions in order to make the ideas in my proofs more concise:</p>

<p>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).</p>

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

<p>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$.</p>

<p>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$.</p>

<hr>

<h2>vertex cover of $n$-walks is NP-complete for any constant $n \ge 1$</h2>

<p>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)$</p>

<p>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).</p>

<p>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).</p>

<hr>

<h2>vertex cover of $n$-trails and vertex cover of $n$-paths are NP-complete for any constant $n \ge 1$</h2>

<p>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:</p>

<p>If $G = (V,E)$ then </p>

<ul>
<li>the vertices of $G_n$ are $V \times \{1, \ldots, n\}$</li>
<li>for $v \in V$ and $i \in \{1, ..., n-1\}$, there is an edge in $G_n$ from $(v, i)$ to $(v, i+1)$</li>
<li>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)$</li>
</ul>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-02-23T18:47:39.167Z
2017-02-23T18:47:39.167Z
Mikhail Rudoy
<p>I have the following problem, let's call it the $n$ vertex cover:</p>

<blockquote>
  <p>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$.</p>
</blockquote>

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

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

CC BY-SA 3.0
2017-01-09T19:30:38.610Z
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
CC BY-SA 3.0
2017-01-09T23:18:40.553Z
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
CC BY-SA 3.0
2017-01-09T23:44:22.770Z
@NealYoung For constant *n*, can we do better than an *n*-approximation?
FUZxxl
CC BY-SA 3.0
2017-01-25T22:03:22.117Z
See the original copy on CS.SE for [another relevant comment from Neal Young](http://cs.stackexchange.com/questions/68466/has-this-generalization-of-the-vertex-cover-problem-been-researched#comment146173_68466).
D.W.
CC BY-SA 3.0
2017-01-25T22:43:53.670Z
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
CC BY-SA 3.0
2017-01-25T23:03:16.160Z
@Mikhail Yeah, I want a minimum set.
FUZxxl
<graph-theory>
Has this generalization of the vertex cover problem been researched?
FUZxxl
# Has this generalization of the vertex cover problem been researched?

(Asked by: username_0 on 2017-01-09)

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.

**Tags:** graph-theory

> **Comments:**
> **username_1**: 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.  
> **username_1**: 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).  
> **username_0**: @NealYoung For constant *n*, can we do better than an *n*-approximation?  
> **username_2**: See the original copy on CS.SE for [another relevant comment from username_1](http://cs.stackexchange.com/questions/68466/has-this-generalization-of-the-vertex-cover-problem-been-researched#comment146173_68466).  
> **username_3**: 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).  
> **username_0**: @Mikhail Yeah, I want a minimum set.  

---

## 2 answers

### Answer by username_4 on 2017-02-22. Score: 4 | Accepted answer

This problem has been studied at least for paths. The problem is NP-complete for any $n \geq 2$ (see for example [this](http://www.sciencedirect.com/science/article/pii/S0020019014001446)).

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](http://www.sciencedirect.com/science/article/pii/S0020019013001130).

On the positive side, there are constant-factor [approximations algorithms](http://www.tandfonline.com/doi/abs/10.1080/00207160.2014.881476?journalCode=gcom20), at least for some special cases.


---

### Answer by username_3 on 2017-02-23. Score: 1

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.


---

