Coverings and matchings on graphs are an integral part of the study of graph theory with numerous applications. A full exploration would be more appropriate for a graph theory or combinatorics course. However, to highlight some of the ways that linear optimization can be applied here, we examine the relationship between primal and dual problems, observe some limitations, and consider a case where we can employ linear optimization to solve problems without concern.
A matching is a collection of edges \(M\) such that no two edges in \(M\) are incident to the same vertex. Let \(\Xi(G)\) denote the size of the largest possible matching(s) 1
There is, too my knowledge, no standard notation for the size of a maximum matching for \(G\text{.}\) This is the proposed notation from Dr. Mark Kayll of the University of Montana, since the \(\Xi\text{,}\) the capital greek letter Xi, looks like a matching.
Let \(G\) be a graph with vertices \(v_1, \ldots, v_n\text{,}\) and \(M\) be any matching on \(G\text{.}\) For each edge \(v_iv_j\) let \(x_{ij}\in [0,1]\) such that if \(v_iv_j\in M\text{,}\) then \(x_{ij}=1\text{,}\) otherwise \(x_{ij}=0\text{.}\)
State the maximization linear optimization problem for computing the maximum matching of a graph \(G\text{.}\) We well refer to this problem as the matching primal problem.
Consider \(G\) from Exploration 9.1.1. Label each vertex and write out a Tucker tableau for the linear optimization problem for computing the maximum matching.
Consider \(H\) from Exploration 9.1.1. Label each vertex and write out a Tucker Tableau for the linear optimization problem for computing the maximum matching.
Prove that any graph \(G\) and matching \(M\) (maximum or not) corresponds to a feasible solution for this problem where \(x_{ij}=1\) if \(v_iv_j\in M\) and \(x_{ij}=0\) otherwise.
Let \(f(\x^*)\) be the maximum value of the objective function for this problem. What can be said about the relationship between \(f(\x^*)\) and \(\Xi(G)\text{?}\)
Let \(y_i\) denote the dual variable corresponding to the primal constraint for vertex \(v_i\text{.}\) What is the dual objective function in terms of \(y_i\text{?}\)
For each edge \(v_{i}v_j\text{,}\) there is a dual constraint, state this dual constraint. (Hint: in the original Tucker Tableau, when would an entry in the \(x_{ij}\) column be a zero, and when would it be a one?)
Suppose we restrict to only integer values, give an interpretation for the dual min problem (Hint: each \(y_i\) corresponds to a vertex \(v_i\text{.}\) Would \(y_i\) take on any values besides 0 or 1)?
Given a graph \(G\text{,}\) a vertex cover or \(cover\) is a collection of vertices \(U\) such that for any edge \(v_iv_j\) either \(v_i\) or \(v_j\) (possibly both) are in \(U\text{.}\)
For each vertex \(v_i\text{,}\) let \(y_i=1\) if \(v_i\in U\) and \(y_i=0\) otherwise. Show this is a feasible solution to the dual problem found in Activity 9.1.4 for \(G\text{.}\) Is it optimal?
Prove that any graph \(G\) and cover \(U\) (minimum or not) corresponds to a feasible solution for this problem where \(y_{i}=1\) if \(v_i\in U\) and \(y_i=0\) otherwise.
Let \(g(\y^*)\) be the minimum value of the objective function for this problem. What can be said about the relationship between \(g(\y^*)\) and \(\tau(G)\text{?}\)
Subsection9.1.1Königs Theorem and Bipartite Graphs
As mentioned above, a full discussion of covers and matchings, while fascinating, would be beyond the scope of this text. We will restrict ourselves to a specific family of graphs.
A graph \(G\) is said to be bipartite, if its vertices \(V\) may be partitioned into two disjoint sets, \(V_1, V_2\) where there are no edges between vertices in the same \(V_i\text{.}\)
For the graphs in Activity 9.1.8, find \(\Xi, \tau\text{.}\) What do you notice? Is there any difference in the results for bipartite and nonbipartite graphs?
Show that if the primal matching problem has an optimal solution \(\x^*\) consisting of only integer values, then it corresponds to a maximum matching.
We now consider a general bipartite graph \(G\text{,}\) and we suppose the primal matching problem has an optimal solution \(\x^*\) with potentially fractional values. We will explore how we can convert this solution into an integral valued optimal solution.
Suppose there were a collection of edges for which the corresponding \(x_{ij}^*\) had fractional values, such that these fractional edges formed a cycle \(C\text{.}\) Without loss of generality, we may label the vertices \(v_1, v_2, \ldots v_k\) so that for \(1\leq i \leq k-1\text{,}\)\(v_iv_{i+1}\) and \(v_kv_1\) have an edge between them, and \(x_{i,i+1}^*, x_{k,1}^*\) have fractional values.
Suppose we construct a new solution \(\x'\) by replacing \(x_{i,i+1}^*\) with \(x_{i,i+1}^*-\epsilon\) when \(i\) is odd, with \(x_{i,i+1}^*+\epsilon\) when \(i\) is even, and leaving every edge not part of \(C\) the same. What value for \(\epsilon\) would guarantee that at least one of the new \(x'_{i,i+1}\) is an integer?
Suppose there were no collection of edges for which the corresponding \(x_{ij}^*\) had fractional values, such that these fractional edges formed a cycle. Let \(v_1, v_2, \ldots v_k\) form a maximal path \(P\) where \(x^*_{i,i+1}, 1\leq i\leq k-1\) has fractional value.
Suppose we construct a new solution \(\x'\) by replacing \(x_{i,i+1}^*\) with \(x_{i,i+1}^*-\epsilon\) when \(i\) is odd, with \(x_{i,i+1}^*+\epsilon\) when \(i\) is even, and leaving every edge not part of \(P\) the same. What value for \(\epsilon\) would guarantee that at least one of the new \(x'_{i,i+1}\) is an integer?
We now switch our attention to covers. Suppose the dual covering problem has an optimal solution \(\y^*\) with potentially fractional values. We will explore how we can convert this solution into an integral valued optimal solution.
Let \(F\subseteq V\) be the set of vertices where \(y^*_i\) has a fractional value for all \(v_i\in F\text{.}\) Without loss of generality, suppose \(V_1\cap F\geq V_2\cap F\text{.}\)
Let \(F^c\) denote the complement of \(F\text{.}\) We may partition \(V(G)\) into four sets: \(F\cap V_1, F\cap V_2, F^c\cap V_1, F^c\cap V_2\text{,}\) Let edges of \(G\) be partitioned into four sets as follows:
\(E_1\) denotes edges incident to vertices in \(F^c\cap V_1\) and \(F^c\cap V_2\text{.}\)
Recall that each vertex \(v_i\) in \(F\) is assigned a fractional value \(y_i^*\) less than 1. For any edge \(v_iv_j\) in \(G\text{,}\) where \(v_j\not\in F\text{,}\) what can we say about \(y_j^*\text{?}\)
Recall that without loss of generality, \(|F\cap V_1|\geq |F\cap V_2|\text{.}\) Suppose we construct a new solution \(\y'\) by replacing \(y_i^*\) with \(y_i^*-\epsilon\) when \(v_i\in F\cap V_1\text{,}\) with \(y_{i}^*+\epsilon\) when \(v_i\in F\cap V_2\text{,}\) and leaving every vertex not in \(F\) the same. What value for \(\epsilon\) would guarantee that at least one of the new \(y'_i\) is an integer, and \(\y'\geq 0\text{?}\)