How to design an algorithm which turns an undirected graph into directed with all nodes of indegree higher than 0? [closed]

Question

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).

Answer 1

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, 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). 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.

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). 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.