2
$\begingroup$

Undirected graph is given which has M edges and N vertices we have to convert every edge from $u-v$ to $u\to v$ or $v\to u$ such that the total indegree of every vertex is even.

For example, consider a graph which has the edges 1-2, 1-3, 2-4, 3-4. We can direct it as 1→2, 1→3, 2←4, 3←4, so indegrees of 1,2,3,4 are respectively 0,2,2,0, which are all even.

Which method or algorithm is suited for least time complexity? M and N are between 1 and 100,000.

$\endgroup$
  • 3
    $\begingroup$ There is no such algorithm as this is not always possible. In a $K_2$, regardless of how you orient $uv$, the in-degree of $u$ or $v$ is 1, which is not even. $\endgroup$ – Juho Dec 9 '18 at 13:14
  • 1
    $\begingroup$ Please credit the original source of the problem in the question. $\endgroup$ – John L. Dec 10 '18 at 1:37
  • 2
    $\begingroup$ @Juho More generally, it's impossible if the number of edges is odd. $\endgroup$ – David Richerby Dec 11 '18 at 10:54
  • $\begingroup$ Please block this question, this is a question from a competition codechef.com/DEC18B/problems/EDGEDIR $\endgroup$ – Sahil Kumar Dec 12 '18 at 13:40
  • $\begingroup$ It might be too late now, unfortunately. It’s only fair to let anyone use the solution. $\endgroup$ – Yuval Filmus Dec 12 '18 at 17:24
3
$\begingroup$

Orient all edges in an arbitrary fashion, and add a $0/1$ variable $x_{u,v}$ for each edge $(u,v)$, with the following meaning: $x_{u,v} = 0$ means that we use the orientation $u \to v$, and $x_{u,v} = 1$ means that we use the orientation $u \gets v$. The parity of the indegree of $u$ is equal to $$ \sum_{(u,v) \in E} x_{u,v} + \sum_{(w,u) \in E} (1 + x_{w,u}) \pmod{2}. $$ Let $p_u$ be the parity of the number of edges of the form $(w,u)$. Then we can formulate the task as follows:

Assign $0/1$ values to the edges so that the sum of weights of edges adjacent to $u$ is $p_u$ (mod 2).

As an example, consider your sample graph, with edges $$ (1,2), (1,3), (2,4), (3,4). $$ We have $p_1 = 0$, $p_2 = 1$, $p_3 = 1$, $p_4 = 0$. We are looking for a solution (mod 2) of the following system: $$ \begin{align*} &x_{12} + x_{13} = 0 \\ &x_{12} + x_{24} = 1 \\ &x_{13} + x_{34} = 1 \\ &x_{24} + x_{34} = 0 \end{align*} $$

One such solution is $x_{12} = x_{13} = 0$, $x_{24} = x_{34} = 1$. This is exactly the solution that you describe.

If you sum all equations, then all the edges cancel, and you get $\sum_u p_u = 0 \pmod{2}$. This gives a necessary condition for the existence of a solution. It turns out that this condition is also sufficient, assuming the graph is connected (otherwise, you need a similar condition for each connected component). A solution can be found using linear algebra modulo 2.

This is related to the so-called Tseitin contradictions in proof complexity, which correspond to assignments of the weights $p_u$ for which no solution exists.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Please block this question, this is a question from a competition codechef.com/DEC18B/problems/EDGEDIR $\endgroup$ – Sahil Kumar Dec 12 '18 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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