1
$\begingroup$

Given an undirected graph $G=(V,E)$, describe an algorithm that computes an orientation of $E$ such that each vertex has out-degree at least 3.

I know how to check if a vertex $v$ has at least $k$ edge-disjoint paths to any other vertex (using Ford-Fulkerson), so I thought I may use that for $k=3$.

Would appreciate your help :)

$\endgroup$
1
$\begingroup$

Given $G=(V,E)$, create a directed bipartite graph $H=(V+E, F)$ where there is an edge $(v,e) \in F$ iff $v \in V$ is an endpoint of $e \in E$. All these edges have capacity $1$.

Augment $H$ as follows: add two additional vertices $s$ and $t$; for each $v \in V$ add an edge $(s,v)$ with capacity $3$; for each $e \in E$ add the edge $(e, t)$ with capacity $1$.

Compute a maximum flow $\phi$ from $s$ to $t$ in the augmented version of $H$. Your problem admits a solution if and only if the amount of flow $|\phi|$ is $3|V|$.

To see this, first observe that $3|V|$ is an upper bound on $|\phi|$. Then suppose that there exists a feasible orientation $\mathcal{O}$ and look at any partial orientation $\mathcal{O}'$ in which each vertex $v$ has exactly three outgoing edges. A flow $\phi$ such that $|\phi|=3|V|$ is obtained by sending one unit of flow across each edge $(v,e) \in F$ such that $e$ is oriented away from $v$ in $\mathcal{O}'$, the flow across each edge $(s,v)$ is $3$, and the flow across $(e,t)$ is 1 if $e$ is oriented in $\mathcal{O}'$ and $0$ otherwise.

Suppose now that there is a flow $\phi$ such that $|\phi|=3|V|$. W.l.o.g., $\phi$ is integral. A feasible orientation is obtained by orienting each edge $e \in E$ away from the (at most one) endpoint $v$ of $e$ for which $\phi(v,e)=1$. If no such endpoint exists, then $e$ can be oriented arbitrarily. Notice that this procedure is constructive and immediately yields an algorithm for your problem.

$\endgroup$

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.