Past exam of the computer science course of the University of Oxford / 2019 / Algorithms / 1

Use nonnegative amounts on the original directed edges of the flow network. A feasible flow is a function $f:E\to {\mathbb{R}}_{\ge 0}$ satisfying the capacity constraints $f(u,v)\le c(u,v)$ and flow conservation at every internal vertex:Its flow value is net outflow at the source,Summing flow conservation shows that this is also net inflow at the sink. Subtracting incoming flow matters when the source has incoming edges.

An $s$–$t$ cut of a flow network is a partition of a set $(S,V\setminus S)$ with $s\in S$ and $t\notin S$. Its cut capacity is the total outward flow network edge capacity,Incoming edges do not contribute to this sum. Equivalently, one may use the antisymmetric net-flow convention, but the nonnegative arc convention above will also be used in the subsequent reductions.

Sum net outflow over all vertices in the source side $S$. An internal directed edge occurs once positively and once negatively, so it cancels. All internal vertices have zero net outflow by flow conservation, and the sink is outside $S$. ThereforeThe second sum is nonnegative, while every term in the first satisfies its capacity constraint. Consequently,This is direct accounting from flow conservation; it does not invoke the max-flow min-cut theorem.

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, the flow value equals the number of selected edges. Maximizing either quantity therefore maximizes the other.

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.

Separate the forced integer portion from the choice of rounding direction. Put $p_{ij}=\lfloor a_{ij}\rfloor$ and $q_{ij}=a_{ij}-p_{ij}$. Define residual demandsThese are nonnegative integers, since the original row and column sums are integers. Also ${\sum }_i{r}_i={\sum }_j{c}_j=:T$. Each fractional part satisfies $0\le q_{ij}<1$.

Construct a flow network with a vertex for each row and column, source-to-row arcs of flow network edge capacity $r_i$, row-to-column arcs of flow network edge capacity one exactly where $q_{ij}>0$, and column-to-sink arcs of flow network edge capacity $c_j$. The amounts $q_{ij}$ themselves define a fractional feasible flow of flow value $T$. No flow can exceed $T$, the total source flow network edge capacity. Because all constructed flow network edge capacities are integers, an integral maximum flow also has flow value $T$ and saturates every source and sink arc.

Let $h_{ij}$ be its middle-arc flow, taking $h_{ij}=0$ when that arc is absent. Then $h_{ij}\in \{0,1\}$, and the required answer isAt an already integral entry no middle arc exists, so that entry stays fixed. At a nonintegral entry the two possibilities are precisely its floor and ceiling. Flow conservation gives ${\sum }_j{h}_{ij}=r_i$ and ${\sum }_i{h}_{ij}=c_j$, preserving every original row and column sum.

This is matrix rounding with fixed margins. There are $m+n+2$ vertices and at most $mn+m+n$ arcs. Exact rational arithmetic computes the floors and residual demands in polynomial time in the encoded input length; the resulting flow network edge capacities are small integers, so there is no need to scale by a potentially large common denominator.

First give $w$ the vote of every voter whose allowed set contains $w$. Let their number be $K$. This loses no possible strict victory: starting with any winning assignment, changing such a ballot to $w$ increases $w$'s score and weakly decreases an opponent's score. Thus a winning assignment exists exactly when one exists with these $K$ ballots fixed.

Every remaining voter must now be assigned to an allowed opponent, and each opponent may receive at most $K-1$ votes. If any allowed set is empty, there is no valid election assignment. With at least two candidates, $K=0$ immediately makes a unique victory impossible. With only the candidate $w$, every nonempty ballot set forces that candidate, so the answer is yes under the question's strict-comparison definition.

For the remaining case $K\ge 1$, make a flow network with a vertex for each remaining voter and each opponent. Add source-to-voter arcs of flow network edge capacity one, voter-to-opponent arcs of flow network edge capacity one for the allowed choices, and opponent-to-sink arcs of flow network edge capacity $K-1$. Compute an integral maximum flow. ThenA flow saturating all voter arcs assigns each remaining voter to exactly one allowed opponent, by integrality and flow conservation. The sink-arc capacity constraints give every opponent strictly fewer than $K$ votes. Conversely, any winning assignment with the fixed $K$ votes defines just such a saturating feasible flow. The flow network has at most $n+m+2$ vertices and $O(n+m+{\sum }_i|C_i|)$ arcs, hence the decision takes polynomial time.