Past exam of the computer science course of the University of Oxford / 2023 / Combinatorial optimisation (A18330W1)

Worked solutions to all three questions of the Oxford examination held on 25 May 2023. Source release: released examination archive, member 2022/T/a18330w1.pdf; the cover identifies the examination as Trinity Term 2023. Numbering follows the source PDF, pages 2–4. The examination asks candidates to choose two questions; all three are solved here.

We use finite simple graphs throughout the graph arguments. In Question 1(c), $V$ must be nonempty for the stated minimum to exist. In Question 3(d), an edge cover exists only when there is no isolated vertex; for a nonempty connected graph this excludes the one-vertex graph. These minor domain qualifications are made explicit in the affected solutions.

For a set function $f:2^V\to \mathbb{R}$, the four properties are:

Here monotone set function means nondecreasing under inclusion; it does not require strict increase.

The intersection–union definition of a submodular set function isThe diminishing returns characterization of submodularity says that its marginal increments decrease as the conditioning set grows:To obtain diminishing returns from submodularity, apply the intersection–union inequality to $A\cup \{x\}$ and $B$. Their intersection is $A$ and their union is $B\cup \{x\}$, giving exactly the displayed comparison.

Conversely, assume diminishing returns, and enumerate $A\setminus B=\{x_1,\dots ,x_m\}$. Put $C_j=(A\cap B)\cup \{x_1,\dots ,x_j\}$ and $D_j=B\cup \{x_1,\dots ,x_j\}$. Since $C_{j-1}\subseteq D_{j-1}$ and $x_j\notin D_{j-1}$, summing the marginal increment comparisons gives the telescoping sumRearrangement proves submodularity. When $A\setminus B$ is empty, both sums are zero, so the proof includes that case.

Yes: this is a monotone set function. Assume $V\ne \varnothing$, as required by its definition at the empty set. If $\varnothing \ne A\subseteq B$, every weight considered in the maximum over $A$ is considered in the maximum over $B$, hence $f(A)\le f(B)$. If $A=\varnothing$ and $B\ne \varnothing$, the minimum over $V$ is at most every weight in $B$, hence again $f(A)\le f(B)$. No sign condition on the weights is needed.

For every $S\subseteq V$ and $x\notin S$, including $S=\varnothing$, the marginal increment isFor the empty set, this uses $w(x)\ge f(\varnothing )={\min }_{v\in V}w(v)$. The monotone set function property from (i) gives $f(A)\le f(B)$ when $A\subseteq B$. ConsequentlyThus diminishing returns holds, so $f$ is a submodular set function by (b).

Yes, for arbitrary signed weights. A hyperedge meets both $S$ and $V\setminus S$ exactly when it meets both $V\setminus S$ and $S$. Therefore $\delta (S)=\delta (V\setminus S)$, and their weighted sums agree. The hypergraph cut function is a symmetric set function regardless of the signs of its weights.

No. Take the hypergraph with $V=\{a,b\}$ and its single hyperedge $\{a,b\}$ of weight $1$. Then $\{a\}\subseteq V$ but $f(\{a\})=1>0=f(V)$, violating the monotone set function property. This example already has strictly positive weights.

No for arbitrary signed weights. Give the same single hyperedge weight $-1$. For $A=\{a\}$ and $B=\{b\}$,This directly violates the defining inequality for a submodular set function.

With nonnegative weights, the hypergraph cut function is a symmetric set function and a submodular set function, but need not be a monotone set function. The proofs of symmetry and failure of monotonicity in (i) and (ii) still apply.

For submodularity, write $f(S)={\sum }_{e\in E}w(e)q_e(S)$, where $q_e(S)$ is the indicator function that $e$ meets both sides. Fix $x\notin S$. If $x\notin e$, its marginal increment is zero. If $x\in e$, let $m=|e|\ge 2$ and $j=|S\cap (e\setminus \{x\})|$. Its marginal increment isFor $m=2$, the middle case is absent. As $S$ grows without acquiring $x$, $j$ can only increase, so these marginal increments can only decrease. Each $q_e$ therefore satisfies diminishing returns. Multiplying by $w(e)\ge 0$ and summing preserves the inequality, proving submodularity of $f$.

Use the chain lower bound for a submodular set function. Order $T=\{x_1,\dots ,x_n\}$, set $P_j=\{x_1,\dots ,x_j\}$ with $P_0=\varnothing$, and put $a_j=f(P_j)-f(P_{j-1})$. For each $U\subseteq T$, reveal its elements in this same order. Since $U\cap P_{j-1}\subseteq P_{j-1}$, diminishing returns and the normalised set function property giveApply this to each $T_i$ and interchange the finite sums. Every element occurs exactly $k$ times, soThis is the exact-cover inequality for submodular set functions. Some $a_j$ can be negative: exact multiplicity, rather than merely at least $k$ occurrences, is what makes the argument valid without monotonicity. In fact the nonnegative function hypothesis is unnecessary here. If $T=\varnothing$, every $T_i$ is empty and both sides vanish.

The monotone decomposition of a submodular set function subtracts each element's smallest possible marginal increment. For $x\in V$, defineThe set function $h$ is a modular set function: the contributions of each element, and the constant $f(\varnothing )$, cancel inSubtracting this equality from the submodularity inequality for $f$ proves that $g$ is a submodular set function. Also $g(\varnothing )=0$, so it is a normalised set function.

For $x\notin S$, the inclusion $S\subseteq V\setminus \{x\}$ and diminishing returns implyAdding elements one at a time now proves that $g$ is a monotone set function. Since it starts at zero, it is also a nonnegative function. Thus $f=g+h$ has all the required properties.

Here modular set function means equality in the intersection–union identity; a constant term is allowed. If one imposed the additional convention $h(\varnothing )=0$, the claimed decomposition of an arbitrary $f$ would require $f(\varnothing )=0$. The displayed constant is essential for the problem as stated. For $V=\varnothing$, take $g=0$ and $h=f$.

A matroid is a pair $(X,\mathcal{I})$, where $X$ is a finite ground set and $\mathcal{I}\subseteq 2^X$ is its collection of matroid independent sets, satisfying the matroid independence axioms:

The last axiom is augmentation. In particular, every maximal matroid independent set within a given subset has maximum cardinality there: otherwise augmentation would enlarge it.

On fixed labelled ground sets of cardinality $1,2,3$, the numbers of matroids are respectively $2,5,16$.

For one element, the element is either a loop of a matroid or a nonloop, giving two choices. For two elements, rank of a matroid zero and two each give one possibility. At rank of a matroid one, the nonloops form any nonempty subset, giving $2^2-1=3$ more possibilities: total $1+3+1=5$.

For three elements, classify by the total rank of a matroid. At rank of a matroid zero every element is a matroid loop; at rank of a matroid three every subset is a matroid independent set. At rank of a matroid one, choose any nonempty subset of nonloops; exactly the empty set and their singletons are matroid independent sets. This gives seven possibilities.

At rank of a matroid two, either exactly two elements are nonloops, giving three choices for the remaining loop of a matroid, or all three are nonloops. In the latter case, pairs that are matroid dependent sets define parallel elements of a matroid. There can be no such pair, giving the uniform matroid $U_{2,3}$, or exactly one such pair, giving three choices. There cannot be exactly two such pairs: if $\{a,b\}$ and $\{a,c\}$ were matroid dependent sets but $\{b,c\}$ a matroid independent set, augmentation from $\{a\}$ to $\{b,c\}$ would fail. If all three pairs were matroid dependent sets, the rank of a matroid would be one. Hence rank of a matroid two gives $3+1+3=7$ examples.

Every listed possibility satisfies augmentation: the only nontrivial comparison on three elements is from a singleton to a two-element matroid independent set, and with at most one two-element matroid dependent set at least one addition works. The total is therefore $1+7+7+1=16$.

Up to matroid isomorphism, the numbers for $n=1,2,3$ are $2,4,8$. A matroid isomorphism may relabel elements but preserves which subsets are matroid independent sets.

For $n=1$, the loop of a matroid and the nonloop are different types. For $n=2$, there is one type each at rank of a matroid zero and two, and two types at rank of a matroid one, distinguished by having one or two nonloops. Thus there are four.

For $n=3$, the seven labelled examples of rank of a matroid one reduce to three types, distinguished by having one, two or three nonloops. The seven labelled examples of rank of a matroid two also reduce to three types: one loop of a matroid and two independent elements; no matroid loops and one pair of parallel elements of a matroid; or the uniform matroid $U_{2,3}$. Different choices of labels within each description are isomorphic. Together with the unique types of rank of a matroid zero and three, this gives $1+3+3+1=8$. The rank of a matroid, number of matroid loops and presence of parallel elements of a matroid distinguish every type just listed.

The rank of a matroid on a subset $A\subseteq X$ isThe matroid independence axioms imply that every maximal matroid independent set in $A$ has this cardinality. We write $A+x=A\cup \{x\}$, as in the source. Directly from the definition,For the last upper bound, deleting $x$ from any matroid independent set in $A+x$ leaves an independent subset of $A$.

If $x\in Y$, then $Y+x=Y$, so $r(Y+x)=r(Y)$. By the definition of the closure of a matroid, $x\in \sigma (Y)$. Hence $Y\subseteq \sigma (Y)$.

We first justify the submodularity of matroid rank, which will also support later arguments. Choose a maximal matroid independent set $I_0$ in $A\cap B$, extend it to a maximal matroid independent set $I_A$ in $A$, and then to one $I_U$ in $A\cup B$. These extensions exist by successive additions, and their sizes are the respective values of the rank of a matroid. No element of $I_U\setminus I_A$ lies in $A$: such an element could have been added to $I_A$, contradicting maximality in $A$. Therefore $I_0\cup (I_U\setminus I_A)$ is an independent subset of $B$, givingNow let $Y\subseteq Z$ and $x\in \sigma (Y)$. If $x\in Z$, then $x\in \sigma (Z)$ by (ii). Otherwise apply submodularity of matroid rank to $Y+x$ and $Z$, whose intersection is $Y$:The monotonicity of the rank of a matroid supplies the opposite bound $r(Z+x)\ge r(Z)$, so equality holds. Thus $x\in \sigma (Z)$, proving $\sigma (Y)\subseteq \sigma (Z)$.

Since $Y$ is a maximal matroid independent set in $Z$, augmentation gives $r(Y)=|Y|=r(Z)$. For any $x\in X$, the rank of a matroid of $Z+x$ equals that of $Y+x$. Indeed, if $x\notin Z$, either $Y+x$ is independent and has the largest possible size $|Y|+1$, or it is dependent and $Y$ is still maximal in $Z+x$: no element of $Z\setminus Y$ can be added, and neither can $x$. If $x\in Z$, both ranks are simply $|Y|$.

Consequently $r(Y+x)=r(Y)$ if and only if $r(Z+x)=r(Z)$, which proves $\sigma (Y)=\sigma (Z)$ for the closure of a matroid.

Choose a maximal matroid independent set $B\subseteq Y$. Its cardinality is $r(Y)=r(Z)$, so it is also maximal in $Z$. Apply (iv) first inside $Y$ and then inside $Z$:This proves that nested subsets of equal rank of a matroid have the same closure of a matroid.

List $\sigma (Y)\setminus Y=\{x_1,\dots ,x_m\}$ and put $Y_j=Y\cup \{x_1,\dots ,x_j\}$. Each $x_j\in \sigma (Y)$ also belongs to $\sigma (Y_{j-1})$ by (iii). Thus the definition of the closure of a matroid gives $r(Y_j)=r(Y_{j-1})$ at every step. Iteration yieldsIn particular, collecting all elements that individually fail to increase the rank of a matroid does not create a collective increase.

By (ii), $Y\subseteq \sigma (Y)$, and by (vi) these subsets have equal rank of a matroid. Apply (v) to this pair to obtainThus the closure of a matroid is an idempotent function.

Write $r(Y)=r$. Since $y\notin \sigma (Y)$, the one-element increment bound gives $r(Y+y)=r+1$. Since $y\in \sigma (Y+x)$,But $Y+y\subseteq Y+x+y$ gives the reverse lower bound $r(Y+x+y)\ge r(Y+y)=r+1$. Hence $r(Y+x+y)=r(Y+y)$, which is precisely $x\in \sigma (Y+y)$. This is the matroid closure exchange property; it follows from one-element rank of a matroid increments and does not require exchanging an entire matroid basis.

A matching in a graph is a subset $M\subseteq E$ whose edges have pairwise disjoint endpoints. It is a perfect matching when every vertex is incident to exactly one edge in $M$.

Use Tutte's theorem on perfect matchings: a finite graph has a perfect matching if and only if, for every $S\subseteq V$, the number $q(S)$ of connected components of a graph of odd integer order in $G-S$ is at most $|S|$.

First, the handshaking lemma gives $3|V|=2|E|$, so $|V|$ is an even integer. Fix $S\ne \varnothing$. For each connected component of a graph $C$ of odd integer order in $G-S$, let $d(C)$ count its edges to $S$. Counting vertex degrees inside $C$ givesThus $d(C)$ is an odd integer; it is positive because $G$ is a connected graph. If $d(C)=1$, its unique outgoing edge is a bridge. Distinct such components yield distinct bridges, so there are at most two of them. Every other such component has $d(C)\ge 3$. ThereforeThe last inequality holds because each vertex of $S$ has vertex degree three. Furthermore,since components of even integer order do not affect parity, and $|V|$ is an even integer. If $q(S)>|S|$, this parity forces $q(S)\ge |S|+2$, contradicting the bound $3q(S)\le 3|S|+4$.

For $S=\varnothing$, the only component is the whole connected graph, of even integer order, so $q(\varnothing )=0$. Thus every $S$ satisfies the criterion, and $G$ has a perfect matching. This proves the perfect matching theorem for a cubic graph with at most two bridges directly from Tutte's theorem on perfect matchings.

Choose a perfect matching $M$ from (i). Every vertex has exactly two incident edges in $E\setminus M$, so this spanning subgraph is a disjoint union of graph cycles. Orient each graph cycle cyclically, and let $s(v)$ be the next vertex after $v$ along its oriented graph cycle.

For each $uv\in M$, take the three-edge sequenceIts four vertices are distinct. Each $s(u)\ne u$ and $s(v)\ne v$ because the graph is a simple graph. Also $s(u)\ne v$ and $s(v)\ne u$, since $uv$ belongs to $M$, rather than $E\setminus M$. Finally $s(u)\ne s(v)$ because the successor map $s$ is a bijection on the disjoint graph cycles. Thus this is a graph path of length exactly three.

Every edge of $M$ is used once as a middle edge. Every edge of $E\setminus M$ is used once as the outgoing edge of its tail, whose unique edge of $M$ determines which graph path contains it. Hence these graph paths are pairwise edge-disjoint and cover $E$. This is the three-edge path decomposition from a perfect matching.

The maximum-weight matching problem asks for a matching in a graph $M\subseteq E$ maximizing its total weight:The requirement is on weight; a maximum cardinality matching need not solve this optimization problem.

The sharp approximation algorithm factor is $c=2$. Charge each edge $e$ of an optimal maximum-weight matching $M_o$ to an edge of the greedy matching $M_g$. If $e\in M_g$, charge it to itself. Otherwise it was rejected because a previously selected edge $g\in M_g$ shared an endpoint; charge $e$ to one such $g$. Since the scan is in nonincreasing weight order, $w(e)\le w(g)$.

Each $g\in M_g$ receives at most two charges, since each of its two endpoints meets at most one edge of the matching in a graph $M_o$. If $g\in M_o$, only its own charge is possible. ThusThis inequality also covers the edgeless graph, for which both weights are zero and the displayed ratio in the question is undefined.

For tightness, take a four-vertex path graph with weights $1,1+\epsilon ,1$ in order, where $0<\epsilon <1$. The greedy matching chooses only the middle edge, of weight $1+\epsilon$, whereas the optimal matching in a graph chooses both outer edges, of total weight $2$. HenceTo obtain infinitely many different sizes, for each $k\ge 2$ take $k$ disjoint copies with $\epsilon =1/k$. Their weights add, so their ratio is $2/(1+1/k)\to 2$. All weights are strictly positive, and the middle edge is uniquely heaviest in each copy. With all three weights equal to $1$, a permitted tie order selecting each middle edge first attains ratio $2$ exactly. The greedy two-approximation for maximum-weight matching is therefore best possible.

Assume $G$ has no isolated vertex; otherwise an edge cover does not exist. In particular, a one-vertex connected graph is an excluded degenerate case of the statement.

Let $M$ be a maximum cardinality matching, of size $m(G)$, and let $U$ be its unmatched vertices in a matching. There is no edge joining two vertices of $U$, since adding it would enlarge $M$. Choose one incident edge for each $u\in U$. These chosen edges are distinct and outside $M$, so together they form an edge cover of sizeConsequently $e(G)\le |V|-m(G)$.

For the opposite bound, let $F$ be a minimum-cardinality edge cover. It is inclusion-minimal. Every selected edge has an endpoint of vertex degree one in $(V,F)$: otherwise deleting that edge would leave both endpoints covered. Each connected component of a graph of $(V,F)$ is therefore a star graph. To see this, a component can have at most one vertex of vertex degree greater than one; a shortest graph path between two such vertices would contain an edge whose endpoints both have vertex degree greater than one. A component with no such vertex is a single edge, also a star graph.

If there are $t$ such star graphs, each has one fewer edge than vertices, so $|F|=|V|-t$. Select one edge from each component to get a matching in a graph of size $t$. Hence $m(G)\ge t=|V|-e(G)$, proving the edge cover and matching identity

First test for an isolated vertex, reporting infeasibility if one exists. Otherwise compute a maximum cardinality matching $M$ using a general-graph polynomial-time algorithm, then add one arbitrary incident edge for each unmatched vertex in a matching. The proof in (i) shows that the resulting edge cover has minimum cardinality $|V|-|M|$.

The final scan takes $O(|V|+|E|)$ time with adjacency lists; the maximum cardinality matching computation is polynomial. One may obtain it from a general-graph maximum-weight matching routine with every weight equal to one.^[ref]

Use minimum-weight edge cover by matching savings. Reject inputs with an isolated vertex. For every vertex $v$, choose a cheapest incident edge $e_v$ and write $c_v=w(e_v)$. Define a baseline and a saving for each edge $uv$ byCompute a maximum-weight matching $M$ using $p$ as its weights, allowing the empty matching in a graph and imposing no maximum-cardinality condition. Negative savings may be ignored. ReturnThis is an edge cover. Since original weights are nonnegative, removing duplicate appearances of an edge cannot increase the total, and henceTo prove optimality, take a minimum-weight edge cover and remove redundant edges until it is inclusion-minimal. Nonnegative weights ensure that its weight does not increase, so it remains optimal. As proved in (i), its components are star graphs. Choose one edge from each star graph, forming a matching in a graph $N$.

In a star graph with center $a$, selected leaf $b$, and other leaves $L$, this choice contributes $w(ab)+{\sum }_{v\in L}{c}_v$ to $B-p(N)$. Each other leaf $v$ has its edge $av$ available, so $c_v\le w(av)$. Thus this contribution is at most the weight of that star graph. Summing over components yieldsSince $M$ maximizes saving, $p(M)\ge p(N)$, and consequentlyAll inequalities are equalities. Therefore $F_M$ is a minimum-weight edge cover. This proof also handles zero weights and duplicate cheapest-edge choices.

Finding all $c_v$ and constructing $F_M$ takes $O(|V|+|E|)$ time. A general-graph maximum-weight matching polynomial-time algorithm supplies the only substantial step; the documented routine runs in $O(|V{|}^3)$ arithmetic time. Exact rational or integer weights avoid floating-point comparisons affecting optimality.^[ref]