6
$\begingroup$

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.

$\endgroup$

migrated from cs.stackexchange.com Jan 25 '17 at 21:34

This question came from our site for students, researchers and practitioners of computer science.

  • $\begingroup$ 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. $\endgroup$ – Neal Young Jan 9 '17 at 19:30
  • $\begingroup$ 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). $\endgroup$ – Neal Young Jan 9 '17 at 23:18
  • $\begingroup$ @NealYoung For constant n, can we do better than an n-approximation? $\endgroup$ – FUZxxl Jan 9 '17 at 23:44
  • $\begingroup$ See the original copy on CS.SE for another relevant comment from Neal Young. $\endgroup$ – D.W. Jan 25 '17 at 22:03
  • $\begingroup$ 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). $\endgroup$ – Mikhail Rudoy Jan 25 '17 at 22:43
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.