Past exam of the computer science course of the University of Oxford / 2023 / Combinatorial optimisation / 3

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]