= Solution
A <path-cycle matching> is exactly an <edge> <subset> whose resulting <subgraph> has maximum <degree> at most two: every nontrivial <connected component of a graph> of this form is a <graph path> or a <cycle in a graph>. Thus the task is a <bipartite b-matching> problem with bound two at every <vertex>.
Find a <bipartition> $L,R$, orient every original <edge> from $L$ to $R$, and add a source $s$ and sink $t$. Give each arc $s\to u$, for $u\in L$, <flow network edge capacity> two; each original arc $u\to v$ <flow network edge capacity> one; and each arc $v\to t$, for $v\in R$, <flow network edge capacity> two. Compute an integral <maximum flow> and select the original <edges> whose <flow> is one. The <integral max-flow theorem> guarantees such an integral optimum.
By <flow conservation>, at most two selected <edges> touch each <vertex>, so they decompose into the required <vertex-disjoint paths> and <cycles in a graph>. Conversely, any permissible <path-cycle matching> gives a <feasible flow>: send one unit through its middle arc for each selected <edge>, with the outside arc amounts equal to the endpoint <degrees>. In both directions, \b[the <flow value> equals the number of selected <edges>]. Maximizing either quantity therefore maximizes the other.
\Image[/past-exam-of-the-computer-science-course-of-the-university-of-oxford/2019/algorithms-path-cycle-flow.png]
{title=An original <path-cycle matching> example and its integral <maximum flow> representation}
The blue <edges> in this example form a four-<cycle in a graph> and a one-<edge> <graph path>; the dashed <edge> is unused. Their five units of <flow> are optimal: the two left <vertices> $a,b$ can each contribute at most two selected <edges>, and $c$ has only one incident <edge>.
The constructed <flow network> has $|V|+2$ <vertices> and $|E|+|V|$ arcs. A <polynomial-time algorithm> for <maximum flow>, such as the <Edmonds–Karp algorithm>, followed by a traversal of the selected <subgraph>, gives an efficient solution.
Back to article page
