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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top