0
$\begingroup$

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

$\endgroup$

closed as off-topic by Marzio De Biasi, Emil Jeřábek supports Monica, Sasho Nikolov, David Eppstein, Kaveh Nov 1 '17 at 20:57

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Marzio De Biasi, Emil Jeřábek supports Monica, Sasho Nikolov, David Eppstein, Kaveh
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ In the future, this kind of question will be a better fit on cs.stackexchange.com $\endgroup$ – usul Nov 1 '17 at 18:39
3
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Nov 1 '17 at 7:57
  • $\begingroup$ @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. $\endgroup$ – Yos Nov 1 '17 at 9:40
  • 1
    $\begingroup$ 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$"). $\endgroup$ – Yonatan N Nov 1 '17 at 16:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.