<p>I am posting the following question due to a lacking overview of relevant algorithms.</p>

<p>Given a directed graph $G=(V,E)$, how can you find a (minimal) subset $S$ of $V$ such that there for every vertex $u \in V-S$ is a (directed) edge from some vertex $v \in S$ to $u$?</p>

CC BY-SA 3.0
2013-09-07T13:09:58.073Z
The title has "bipartite" but the question doesn't.
Tyson Williams
CC BY-SA 3.0
2013-09-07T15:25:08.163Z
Perhaps this is a polynomial time solution: scan each vertex of $v_i \in V$ and assume that $v_i \in S$; so you must add to $S$ every node $w$ such that there is not an edge $v_i \rightarrow w$. Repeat the operation for the new nodes added to $S$ until $S =V$ or every node in $S$ has a directed edge to a node in $V \setminus S$. If for every $v_i$ you end with $S = V$  then the only trivial minimal soultion is $S = \emptyset$.
Marzio De Biasi
CC BY-SA 3.0
2013-09-07T15:51:30.767Z
See https://en.wikipedia.org/wiki/Dominating_set for pointers.  Note that the undirected version can be trivially reduced to the directed version, so the directed version is NP-hard.
András Salamon
CC BY-SA 3.0
2013-09-07T22:19:49.870Z
@AndrasSalamon: I interpreted the question as every vertex of $S$ must have a directed edge to every vertex of $V \setminus S$ ... "for *every* vertex u in V\S there is a directed edge from *any* (== "every" or "at least one"? :-) vertex v in S" ?!?
Marzio De Biasi
CC BY-SA 3.0
2013-09-08T14:35:59.643Z
@tychicus: do you mean "from any" or "from every"?
András Salamon
CC BY-SA 3.0
2013-09-09T01:27:03.960Z
tychicus, I recommend avoiding use of the word "any", as it can be ambiguous whether you mean "every" or "some" ("for all" vs "there exists").  Perhaps you might like to edit the question to make your final sentence clearer, i.e., to make it clearer what is the criteria for $S$ to be valid?
D.W.
CC BY-SA 3.0
2013-09-13T14:11:43.107Z
@AndrásSalamon I apologize for the ambiguous question. I meant "from some vertex $v \in S$ to $u$.
GCOverhead
<graph-algorithms>
Subset of a vertex set with directed edge to all other vertices
GCOverhead
# Subset of a vertex set with directed edge to all other vertices

(Asked by: username_0 on 2013-09-07)

I am posting the following question due to a lacking overview of relevant algorithms.

Given a directed graph $G=(V,E)$, how can you find a (minimal) subset $S$ of $V$ such that there for every vertex $u \in V-S$ is a (directed) edge from some vertex $v \in S$ to $u$?

**Tags:** graph-algorithms

> **Comments:**
> **username_1**: The title has "bipartite" but the question doesn't.  
> **username_2**: Perhaps this is a polynomial time solution: scan each vertex of $v_i \in V$ and assume that $v_i \in S$; so you must add to $S$ every node $w$ such that there is not an edge $v_i \rightarrow w$. Repeat the operation for the new nodes added to $S$ until $S =V$ or every node in $S$ has a directed edge to a node in $V \setminus S$. If for every $v_i$ you end with $S = V$  then the only trivial minimal soultion is $S = \emptyset$.  
> **username_3**: See https://en.wikipedia.org/wiki/Dominating_set for pointers.  Note that the undirected version can be trivially reduced to the directed version, so the directed version is NP-hard.  
> **username_2**: @AndrasSalamon: I interpreted the question as every vertex of $S$ must have a directed edge to every vertex of $V \setminus S$ ... "for *every* vertex u in V\S there is a directed edge from *any* (== "every" or "at least one"? :-) vertex v in S" ?!?  
> **username_3**: @tychicus: do you mean "from any" or "from every"?  
> **username_4**: tychicus, I recommend avoiding use of the word "any", as it can be ambiguous whether you mean "every" or "some" ("for all" vs "there exists").  Perhaps you might like to edit the question to make your final sentence clearer, i.e., to make it clearer what is the criteria for $S$ to be valid?  
> **username_0**: @AndrásSalamon I apologize for the ambiguous question. I meant "from some vertex $v \in S$ to $u$.  

---

## 0 answers

