Vertex cover algorithms for directed graphs?

Question

I've recently been working on a problem that I believe can be expressed as a vertex cover problem over a directed graph.

Formally, I have a graph $G = (V,E)$ where $V$ is a vertex set and $E$ is a set of edges between vertices. The edges are directed so we can have $e_{ij} = 1$ but $e_{ji} = 0$ where $i,j \in V$. Here, $e_{ji} = 0$ would mean that there is no edge from $j$ to $i$.

My problem is as follows. I would like to find the smallest subset of vertices $S \subseteq V$ such that there is a path from every vertex in S to every vertex to V. That is, for every vertex $j \in V$, there is an $i \in S$ such that either:

• $e_{i,j} > 0$ (edge between $i$ and $j$)
• $e_{i,{k_1}}e_{{k_1,k_2}}$...$e_{{k_t,j}} > 0$ (path from $i$ to $j$)

I will assume that $e_{ii} = 1$ to ensure that such a subset exists, as I can set $S = V$. However, this is only optimal when the set of nodes is entirely disconnected.

I'm wondering if this a vertex cover problem? If so, are there algorithms for this problem? I'm slightly confused because most vertex cover algorithms are for problems where the graph is undirected (e.g., $e_{ij} = e_{ji}$). If not, are there algorithms to solve this problem?

Answer 1

Thanks for the edit! This isn't vertex cover; it's something different.

There are simple algorithms for this problem. Decompose the graph into a dag of strongly connected components. (The dag is sometimes called "the metagraph".) Each source vertex in the dag corresponds to a SCC that has no edges coming into it from outside; for each such SCC, pick one vertex and add it to $S$.

The result will be the smallest set $S$ that meets your conditions. This can be done in $O(V+E)$ time.

---

Answer to the original version of your question (now irrelevant):

Your problem, as stated, is trivial: the solution is the empty set $S=\emptyset$.

If, on the other hand, you meant that $e_{ij} > 0$ implies $i \in S$, the problem is also trivial: the set $S$ has to include the source vertex of every edge. So, you just loop over all the edges $(i,j)$ and add $i$ to $S$.

Answer 2

The problem you're describing sounds more like a Dominating Set style problem to me (vertices covering vertices, Vertex Cover is vertices covering edges), but because you allow the dominating vertex to be at any distance from the dominated vertex, the problem becomes much easier.

I believe the problem can in fact be solved in (near) linear time (in the number of vertices).

Firstly, if we take a strongly connected component, then any vertex in that component will dominate every other vertex in the component (because there's a path from any vertex to any other in that component).

We can compute an auxiliary graph $H = (C,F)$ from $G$ (using any of the algorithms listed on the strongly connected component page) in $O(n)$ time where each strongly connected component is represented by a vertex in $C$, and there is an edge from $c_{1} \in C$ to $c_{2} \in C$ if there is an edge from any vertex in the component represented by $c_{1}$ to any vertex in the component represented by $c_{2}$.

Note that $H$ must be a acyclic (i.e. it's a DAG).

Now we solve the original problem on $H$ to get a set $S_{H}$. The key is that $S_{H}$ must be the set of all sources in $H$ (a source being a vertex with only out-edges, or more precisely, $i \in C$ is a source if for every $j \in C$ we have $e_{ji} \notin F$). Why is this true? There is no path to a source from any other vertex, so each source must be in $S_{H}$, but for every non-source vertex, there is (by definition) a path to it from a source, so it must be dominated by at least that source vertex. So the set of all sources is the minimum set that satisfies the requirements.

We can get all the sources by simply looking at each $c_{i} \in C$ and counting it's in-degree, if it's $0$, it's a source (this is the point where the linear time claim may fall down, it depends highly on your data structures).

Then for each source $c_{i}$ in $S_{H}$ from $H$ we can construct the full solution $S$ for $G$ by simply taking a single vertex from each source $c_{i}$ and adding it to $S$ (also implying that $|S_{H}| = |S|$).