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, 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.
Exploration9.1.1.
Consider the following undirected graph \(G\text{.}\)
(a)
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\) looks like a matching.
.
What is \(\Xi(G)\text{?}\) How can we be sure this is true?
(b)
Find \(\Xi(H)\) for \(H\text{:}\)
Activity9.1.2.
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{.}\)
We now construct a canonical maximization problem which can help compute a maximum matching.
(a)
For each vertex \(v_i\text{,}\) write an inequality to ensure that \(M\) is a matching.
(b)
Given the above constraints, do we need another constraint to ensure that \(x_{ij}\leq 1\text{?}\)
(c)
Find a linear objective function to compute \(\Xi(G)\text{.}\)
(d)
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.
(e)
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.
(f)
Solve the above optimization problem:
What do you notice?
(g)
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.
(h)
Solve the above optimization problem:
What do you notice?
Activity9.1.3.
Consider the general maximization problem constructed in Activity 9.1.2.
(a)
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.
(b)
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{?}\)
\(f(\x^*)\leq \Xi(G)\text{.}\)
\(f(\x^*)\geq \Xi(G)\text{.}\)
\(f(\x^*)= \Xi(G)\text{.}\)
No general relationship exists between \(f(\x^*)\) and \(\Xi(G)\text{.}\)
Prove your claim.
Activity9.1.4.
Consider the general maximization problem constructed in Activity 9.1.2. We now consider it’s dual problem.
(a)
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{?}\)
(b)
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?)
(c)
State the dual minimization problem to the primal maximum matching problem. We will refer to this problem as the dual covering problem.
(d)
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)?
Activity9.1.5.
Given a graph \(G\text{,}\) a vertex cover or \(cover\) is a colection of vertices \(U\) such that for any edge \(v_iv_j\) either \(v_i\) or \(v_j\) (possibly both) are in \(U\text{.}\)
Let \(\tau(G)\) denote the size of the smallest vertex cover 2
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?
(d)
Since we solved the matching problem for \(G\) in Exploration 9.1.1, use Sage to solve the dual problem
What do we notice?
(e)
We “solved” the matching maximixation problem for \(H\) in Exploration 9.1.1, use Sage to solve the dual problem
What do we notice?
Activity9.1.6.
Consider the general dual minimization problem constructed in Activity 9.1.4.
(a)
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.
(b)
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{?}\)
\(g(\y^*)\leq \tau(G)\text{.}\)
\(g(\y^*)\geq \tau(G)\text{.}\)
\(g(\y^*)= \tau(G)\text{.}\)
No general relationship exists between \(g(\y^*)\) and \(\tau(G)\text{.}\)
Prove your claim.
(c)
What can be said about the relationship between \(\Xi(G)\) and \(\tau(G)\text{?}\)
\(\Xi(G)\leq \tau(G)\text{.}\)
\(\Xi(G)\geq \tau(G)\text{.}\)
\(\Xi(G)= \tau(G)\text{.}\)
No general relationship exists between \(\Xi(G)\) and \(\tau(G)\text{.}\)
Prove your claim.
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.
Definition9.1.7.
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{.}\)
Prove that if a graph is bipartite, then it must not contain an odd length cycle 3
The coverse is also true, but we will leave that alone.
.
We now consider coverings and matchings on only bipartite graphs.
Activity9.1.10.
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 non-bipartite 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.
(b)
Show that if the dual covering problem has an optimal solution \(\y^*\) consisting of only integer values, then it corresponds to a minimum cover.
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.
Activity9.1.12.
Let \(G\) be a bipartite graph, and let \(\x^*\) be an optimal solution to the primal matching problem from Activity 9.1.2.
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.
To make notation bearable, we’ll understand that \(v_{k+1}=v_1\text{.}\)
(a)
Why must \(k\) be even?
(b)
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?
\(\epsilon=\min \{x^*_{i,i+1}: 1\leq i \leq k\} \text{.}\)
\(\epsilon=\min \{x^*_{i,i+1}: 1\leq i \leq k, i\text{ is odd}\} \text{.}\)
\(\epsilon=\min \{x^*_{i,i+1}: 1\leq i \leq k, i\text{ is even}\} \text{.}\)
(c)
Show that \(\x'\geq 0\text{.}\)
(d)
Show that for any vertex \(v_j\)not a part of \(C\text{,}\) the bound corresponding to \(v_j\) is still satisfied by \(\x'\text{.}\)
(e)
Show that for any vertex \(v_i\) part of \(C\text{,}\) the bound corresponding to \(v_i\) is still satisfied by \(\x'\text{.}\)
(f)
Show that \(f(\x') = f(\x^*)\text{.}\)
(g)
When comparing \(\x^*\) and \(\x'\text{,}\) which solution has fewer integer values?
\(\x^*\) has fewer integer values.
\(\x'\) has fewer integer values.
\(\x^*, \x'\) have the same number of integer values.
This cannot be determined.
Activity9.1.13.
Let \(G\) be a bipartite graph, and let \(\x^*\) be an optimal solution to the primal matching problem from Activity 9.1.2.
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.
Note that \(v_1, v_k\) are the endpoints of \(P\text{.}\)
(a)
Since \(P\) is maximal, any edges not a part of this path incident to \(v_1, v_k\) must be assigned an integer value. What must this value be?
(b)
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?
\(\epsilon=\min \{x^*_{i,i+1}: 1\leq i \leq k\} \text{.}\)
\(\epsilon=\min \{x^*_{i,i+1}: 1\leq i \leq k, i\text{ is odd}\} \text{.}\)
\(\epsilon=\min \{x^*_{i,i+1}: 1\leq i \leq k, i\text{ is even}\} \text{.}\)
(c)
Show that \(\x'\geq 0\text{.}\)
(d)
Show that for any vertex \(v_j\)not a part of \(P\text{,}\) the bound corresponding to \(v_j\) is still satisfied by \(\x'\text{.}\)
(e)
Show that for any vertex \(v_i\) part of \(P\text{,}\) the bound corresponding to \(v_i\) is still satisfied by \(\x'\text{.}\)
(f)
Show that \(f(\x') \geq f(\x^*)\text{.}\) Why does this imply \(f(\x') = f(\x^*)\text{?}\)
(g)
When comparing \(\x^*\) and \(\x'\text{,}\) which solution has fewer integer values?
\(\x^*\) has fewer integer values.
\(\x'\) has fewer integer values.
\(\x^*, \x'\) have the same number of integer values.
This cannot be determined.
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.
Activity9.1.14.
Let \(G\) be a bipartite graph, and let \(\y^*\) be an optimal solution to the dual covering problem from Activity 9.1.4.
Let \(F\subseteq V\) be the set of vertices where \(x^*_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{.}\)
(a)
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{.}\)
\(E_2\) denotes edges incident to vertices in \(F\cap V_1\) and \(F\cap V_2\text{.}\)
\(E_3\) denotes edges incident to vertices in \(F^c\cap V_1\) and \(F\cap V_2\text{.}\)
\(E_4\) denotes edges incident to vertices in \(F\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{?}\)
(b)
Recall that without loss of generality, \(|F\cap V_1|\geq |F\cap V_2|\text{.}\) Suppose we generate
(c)
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{?}\)
