0
$\begingroup$

I'm very stuck with this problem. Given $G = (V, E, A)$ a mixed graph where every edge in $E$ is directed and every edge in $A$ is undirected. Thinking as a max-flow problem, decide if it's possible to give a direction to every $a \in A$ in order to make $G$ an $eulerian$ graph.

The model I've thinking so far is to translate the problem as a matching problem. For every non directed edge, I would like to determine to which node this will point. For example, if $e=(u,v)$, from the vertex source there should be an edge connecting to $e$ and this one will be connected to $u$ and $v$. Every edge will have a flow capacity of 1, except for the edges of the target, which will have a capacity of $?$. I don't know if this model it's okay, but any clue (or another model) will help, thanks!

$\endgroup$
0
2
$\begingroup$

You want each node to have the same number of incoming and outgoing edges.

Let $\alpha(v)$ be the number of edges in $A$ outgoing in $v$ minus the number of edges in $A$ outgoing from $v$. Consider the graph $H=(V,E)$ and let $\delta(v)$ be the degree of $v$ in $H$.

We need to find an orientation of the edges in $H$ such that each vertex $v$ has an out-degree that is exactly its in-degree minus $\alpha(v)$. In other words, if $k$ is the number of edges in $E$ that need to be oriented towards $v$, we must have: $$ \delta(v) - k(v) = k(v) - \alpha(v), $$ equivalently: $$ k(v) = \frac{\delta(v) + \alpha(v)}{2}, $$ where we can assume that all $k(v)$s are non-negative integers and that $|E| = \sum_{v \in V} k(v)$ (otherwise there is no feasible orientation).

Create a graph $H' = (\{s,t\} \cup E \cup V, F)$ where $F$ contains the following directed edges:

  • All edges in $\{s\} \times E$ with capacity $1$;
  • An edge $(v,t)$ with capacity $k(v)$ for each in $v \in V$.
  • Two edges $(e, u)$ and $(e, v)$, both of capacity $1$, for each $e \in E$.

Now compute a max flow $f$ from $s$ to $t$ in $H'$ and check whether its value $|f|$ is exactly $\sum_{v \in V} k(v)$.

If that's the case at least one valid orientation exists and it can be found by orienting $e = (u,v) \in E$ towards the unique endpoint $x \in \{u,v\}$ such that $f( \, (e,x) \, ) = 1$.

$\endgroup$
1
  • 1
    $\begingroup$ Didn't expect something so formal, thanks :) $\endgroup$ Jun 16 at 16:49

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.