3
$\begingroup$

I'm completely stuck on this one. The obvious resemblance between the two that I see is that every vertex needs to have the same amounts going in and out, in the Eulerian cycle problem the amount is just the number of edges, and in the maximum flow problem it's the flow. But I can't figure out what I'm trying to maximize in that case, or what the flow is.

To clarify: a mixed graph is a graph with some directed edges and some undirected.

$\endgroup$
  • $\begingroup$ Here's an idea that I haven't been able to make work, but perhaps you can fix it. The problem is equivalent to assigning an orientation to each undirected edge so that in the resulting digraph, the ind-degree of each vertex equals its out-degree. We need only consider vertices incident on at least one undirected edge. Suppose the in-degree of some vertex is $5$, the out-degree is $3$, and there are $4$ undirected edges incident on it. We need to orient the undirected edges to that $3$ go out and $1$ comes in. For a flow network, this would mean we'd have to supply $2$ units (continued) $\endgroup$ – saulspatz May 27 '19 at 18:35
  • $\begingroup$ (cont.) from the source. We might similarly have to supply edges to the sink. For each undirected edge $uv$ I wanted to have and edge of capacity $1$ from $v$ to $u$ and another from $u$ to $v$. But I have two problems. First, I don't know how to orient the edge in the original graph if both $uv$ and $vu$ have a flow in the network. Second, I don't know how to enforce the condition that at least one of them must have a flow. I hope this gives you some ideas, or at least crosses off a wrong approach. $\endgroup$ – saulspatz May 27 '19 at 18:39

Your Answer

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

Browse other questions tagged or ask your own question.