<p>Edit: modified to emphasize how this approach can be generalized to any arbitrary degree sequence of lower bound in-degrees.</p>

<p>(Apologies if the below is extra verbose -- you said that you're new to graph algorithms, and I want to make sure you can follow the reasoning.)</p>

<p>Your problem is a special case of the <a href="https://dl.acm.org/citation.cfm?id=1132522" rel="nofollow noreferrer" title="Santa Clause Problem">Santa Clause problem</a>, and the (significantly) more general version that requires each vertex $v_i$ to have in-degree $\geq d_i$ can be solved using Max $s-t$ Flow as follows (your problem is the special case where each $d_i$ is exactly $1$, <a href="https://en.wikipedia.org/wiki/Maximum_flow_problem%20click%20here%20to%20see%20more%20about%20maximum%20flow" rel="nofollow noreferrer">read up more on maximum flow here</a>). Given an instance $G = (V,E)$ of your problem, we construct a new graph $G'$ with $|V| + |E| + 2$ vertices as follows:</p>

<ul>
<li>A source node $s$</li>
<li>An edge layer consisting of one node $u_i$ for each $e_i \in E$</li>
<li>A vertex layer consisting of one node $w_i$ for each $v_i \in V$</li>
<li>An sink-node $t$</li>
</ul>

<p>Further, we connect these nodes with (directed) arcs as follows</p>

<ul>
<li>$s$ has an arc to each $u_i$ node, with capacity-$1$</li>
<li>Each $u_i$ node has an arc to both $w_j$ and $w_k$, where $v_j$ and $v_k$ are the endpoints of $e_i$ in $G$, again with capacity-$1$.</li>
<li>Each $w_i$ has an arc to $t$, with capacity $d_i$.</li>
</ul>

<p>Here's an MSPaint diagram of the reduction on a particularly simple example. All drawn edges in $G_2$ are actually downward-oriented arcs.</p>

<p><a href="https://i.sstatic.net/LMRlY.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/LMRlY.png" alt="enter image description here"></a></p>

<p>The claim is that the max $s-t$ flow in this graph is $\sum_i d_i$ iff $G_1$'s edges can be directed so that the min in-degree is $\geq d_i$. Additionally, when the problem is solvable, the optimal solution will be easy to extract*.</p>

<p>The analysis is as follows. The graph has integer weights, so w.l.o.g. we can consider only integer-valued $s-t$ flows (this is called the <a href="https://en.wikipedia.org/wiki/Maximum_flow_problem#Integral_flow_theorem" rel="nofollow noreferrer">Integral Flow Theorem</a>). Additionally, the weights on the edges between the $\{w_i\}$ and $t$ ensure that the only way we can get $\sum_i d_i$ units of flow to $t$ is by first getting at least $d_i$ units of flow to each $w_i$. How does flow get to the $\{w_i\}$ nodes? It must originate at the $\{u_j\}$ nodes, which correspond to edges of $G$. Because each $\{u_j\}$ is only getting (at most) $1$ unit of flow from $s$, each $u_j$ gets to pick at most one of its two out-neighbors to send its flow to.</p>

<p>Thus, the interpretation of this flow problem construction is that each edge-node gets to pick at most one vertex-node that can get its unit of flow, and each vertex node $w_j$ must be chosen at least $d_j$ times. This is <em>just</em> like your problem, where we have an edge $e_i$ direct itself towards a vertex $v_j$ (in $G_1)$ if $u_i$ sends a unit of flow to $w_j$ (in $G_2$). In particular, the set of utilized arcs between $\{u_i\}$ and $\{w_j\}$ will tell you exactly how to orient some subset of the edges so that every vertex $v_j$ has at least $d_j$ in-edges. The rest, of course, can be oriented arbitrarily.</p>

<p>* Actually, this construction solves a more general problem, in which we want to maximize the number of vertices with at least $d_i$ in-edges.</p>

CC BY-SA 3.0
2017-11-01T07:57:04.743Z
This is a nice reduction, but I think it's a bit of an overkill. Unless I am missing something, the required orientation of the graph exists if and only if every one of its connected components has a cycle. It really is an exercise in edge counting and BFS.
Sasho Nikolov
CC BY-SA 3.0
2017-11-01T09:40:42.880Z
@SashoNikolov Is my attempt to solve this with BFS on the right track?Specifically I'm not sure how to prove that if there's cycle in a graph then we can satisfy the conditions.
Yos
CC BY-SA 3.0
2017-11-01T16:05:18.097Z
Orient the edges of the cycle in a cyclic fashion, so that every vertex has in-degree 1. Now starting from each vertex of the cycle, do a BFS outwards, with $a$ pointing to $b$ if $a$ is reached before $b$. This ensures that every "$b$" has in-degree at least one (from its corresponding "$a$").
Yonatan N
CC BY-SA 3.0
2017-10-31T22:01:52.910Z
2017-11-01T16:11:14.093Z
2017-11-01T16:11:14.093Z
Yonatan N
<blockquote>
  <p>Given an undirected graph $G=(V,E)$ devise an algorithm that will check whether its edges can be directed in such a way that the vertices of the resulting directed graph will all have indegree higher than $0$. For any edge $\{u,v\}∈E$ only one direction can be chosen: $(u,v)$ or $(v,u)$.</p>
</blockquote>

<p>I'm quite new to graphs and graph algorithms so I was wondering if I'm on the right track:</p>

<p>I think the key to the solution is to determine whether the graph is acyclic. </p>

<p>In order to do that we can use BFS algorithm on the graph by coloring layer $i$ in red, layer $i+1$ in blue and again $i+2$ in red and so forth. If at the end of the algorithm we have an edge which connects two nodes of same color that the graph is cyclic. </p>

<p>If the graph is acyclic this means that no matter how we choose the directions if we use topological sorting there will always be a node without an incoming edge, which means that such graphs cannot become directed graphs of indegree higher than $0$ as requested.</p>

<p>Intuitively I think if we have a cyclic graph then our algorithm should be able to turn it into directed with all nodes of indegree higher than $0$ but I'm not sure how to prove this. Maybe like this:</p>

<p>Suppose we choose a graph component with one cycle (circle). We then remove an edge from the circle. Now the component becomes acyclic and using topological sorting we'll have one node without an incoming edge. So now put back the previously removed edge to that node and all the requested conditions hold (the graph is directed and all nodes have at least one incoming edge).</p>

CC BY-SA 3.0
2017-11-01T18:39:34.770Z
In the future, this kind of question will be a better fit on cs.stackexchange.com
usul
<graph-algorithms><directed-acyclic-graph><topology>
How to design an algorithm which turns an undirected graph into directed with all nodes of indegree higher than 0?
Yos
# How to design an algorithm which turns an undirected graph into directed with all nodes of indegree higher than 0?

(Asked by: username_0 on 2017-10-31)

> Given an undirected graph $G=(V,E)$ devise an algorithm that will check whether its edges can be directed in such a way that the vertices of the resulting directed graph will all have indegree higher than $0$. For any edge $\{u,v\}∈E$ only one direction can be chosen: $(u,v)$ or $(v,u)$.

I'm quite new to graphs and graph algorithms so I was wondering if I'm on the right track:

I think the key to the solution is to determine whether the graph is acyclic.

In order to do that we can use BFS algorithm on the graph by coloring layer $i$ in red, layer $i+1$ in blue and again $i+2$ in red and so forth. If at the end of the algorithm we have an edge which connects two nodes of same color that the graph is cyclic.

If the graph is acyclic this means that no matter how we choose the directions if we use topological sorting there will always be a node without an incoming edge, which means that such graphs cannot become directed graphs of indegree higher than $0$ as requested.

Intuitively I think if we have a cyclic graph then our algorithm should be able to turn it into directed with all nodes of indegree higher than $0$ but I'm not sure how to prove this. Maybe like this:

Suppose we choose a graph component with one cycle (circle). We then remove an edge from the circle. Now the component becomes acyclic and using topological sorting we'll have one node without an incoming edge. So now put back the previously removed edge to that node and all the requested conditions hold (the graph is directed and all nodes have at least one incoming edge).

**Tags:** graph-algorithms, directed-acyclic-graph, topology
> **Comments:**
> **username_1**: In the future, this kind of question will be a better fit on cs.stackexchange.com  

---

## 1 answers

### Answer by username_2 on 2017-10-31. Score: 3 | Accepted answer

Edit: modified to emphasize how this approach can be generalized to any arbitrary degree sequence of lower bound in-degrees.

(Apologies if the below is extra verbose -- you said that you're new to graph algorithms, and I want to make sure you can follow the reasoning.)

Your problem is a special case of the [Santa Clause problem](https://dl.acm.org/citation.cfm?id=1132522 "Santa Clause Problem"), and the (significantly) more general version that requires each vertex $v\_i$ to have in-degree $\geq d\_i$ can be solved using Max $s-t$ Flow as follows (your problem is the special case where each $d\_i$ is exactly $1$, [read up more on maximum flow here](https://en.wikipedia.org/wiki/Maximum_flow_problem%20click%20here%20to%20see%20more%20about%20maximum%20flow)). Given an instance $G = (V,E)$ of your problem, we construct a new graph $G'$ with $|V| + |E| + 2$ vertices as follows:

* A source node $s$
* An edge layer consisting of one node $u\_i$ for each $e\_i \in E$
* A vertex layer consisting of one node $w\_i$ for each $v\_i \in V$
* An sink-node $t$

Further, we connect these nodes with (directed) arcs as follows

* $s$ has an arc to each $u\_i$ node, with capacity-$1$
* Each $u\_i$ node has an arc to both $w\_j$ and $w\_k$, where $v\_j$ and $v\_k$ are the endpoints of $e\_i$ in $G$, again with capacity-$1$.
* Each $w\_i$ has an arc to $t$, with capacity $d\_i$.

Here's an MSPaint diagram of the reduction on a particularly simple example. All drawn edges in $G\_2$ are actually downward-oriented arcs.

[![enter image description here](https://i.sstatic.net/LMRlY.png)](https://i.sstatic.net/LMRlY.png)

The claim is that the max $s-t$ flow in this graph is $\sum\_i d\_i$ iff $G\_1$'s edges can be directed so that the min in-degree is $\geq d\_i$. Additionally, when the problem is solvable, the optimal solution will be easy to extract\*.

The analysis is as follows. The graph has integer weights, so w.l.o.g. we can consider only integer-valued $s-t$ flows (this is called the [Integral Flow Theorem](https://en.wikipedia.org/wiki/Maximum_flow_problem#Integral_flow_theorem)). Additionally, the weights on the edges between the $\{w\_i\}$ and $t$ ensure that the only way we can get $\sum\_i d\_i$ units of flow to $t$ is by first getting at least $d\_i$ units of flow to each $w\_i$. How does flow get to the $\{w\_i\}$ nodes? It must originate at the $\{u\_j\}$ nodes, which correspond to edges of $G$. Because each $\{u\_j\}$ is only getting (at most) $1$ unit of flow from $s$, each $u\_j$ gets to pick at most one of its two out-neighbors to send its flow to.

Thus, the interpretation of this flow problem construction is that each edge-node gets to pick at most one vertex-node that can get its unit of flow, and each vertex node $w\_j$ must be chosen at least $d\_j$ times. This is *just* like your problem, where we have an edge $e\_i$ direct itself towards a vertex $v\_j$ (in $G\_1)$ if $u\_i$ sends a unit of flow to $w\_j$ (in $G\_2$). In particular, the set of utilized arcs between $\{u\_i\}$ and $\{w\_j\}$ will tell you exactly how to orient some subset of the edges so that every vertex $v\_j$ has at least $d\_j$ in-edges. The rest, of course, can be oriented arbitrarily.

\* Actually, this construction solves a more general problem, in which we want to maximize the number of vertices with at least $d\_i$ in-edges.

> **Comments:**
> **username_3**: This is a nice reduction, but I think it's a bit of an overkill. Unless I am missing something, the required orientation of the graph exists if and only if every one of its connected components has a cycle. It really is an exercise in edge counting and BFS.  
> **username_0**: @SashoNikolov Is my attempt to solve this with BFS on the right track?Specifically I'm not sure how to prove that if there's cycle in a graph then we can satisfy the conditions.  
> **username_2**: Orient the edges of the cycle in a cyclic fashion, so that every vertex has in-degree 1. Now starting from each vertex of the cycle, do a BFS outwards, with $a$ pointing to $b$ if $a$ is reached before $b$. This ensures that every "$b$" has in-degree at least one (from its corresponding "$a$").  

---

