A dominating set in a graph \(G\) is a set \(S\subseteq V(G)\) such that every vertex \(v\) is either an element of \(S\) or has a neighbour in \(S\text{.}\) The minimum cardinality of a dominating set in \(G\) is denoted \(\gamma(G)\text{.}\)
Write down an integer linear program for computing \(\gamma(G)\text{.}\)
Write down the LP relaxation of the ILP found in the previous part and take its dual. Explain what the dual problem is trying to do in plain English.
The decision problem which asks whether \(\gamma(G)\leq k\) for an input \((G,k)\) is NP-complete. Prove that the problem remains NP-complete if we restrict ourselves to instances in which the graph \(G\) is bipartite.
Let \(A\) be a rational \(m\times n\) matrix and let \(b\in\mathbb{R}^m\text{.}\) Show that the set \(\conv\left(\left\{x\in \mathbb{Z}^n:Ax\leq b\right\}\right)\) is a polyhedron.
Give an example to show that the statement in the previous part of the question may not be true if \(A\) is not a rational matrix.
Our goal is to use the fact that the Stable Set problem (Problem 1.7.3) is NP-complete to show that integer linear programming problems are NP-hard. Given an instance \((G,k)\) for the Stable Set problem where \(G\) has \(n\) vertices, construct, in polynomial time, an integer linear program in \(n\) variables such that \(G\) has a stable set of cardinality \(k\) if and only if the value of the integer linear program is \(k\text{.}\)
Recall the definition of a fractional stable set from Section 4.1. A fractional clique of a graph \(G\) is defined to be a fractional stable set of \(\overline{G}\text{.}\) Define \(\omega^*(G)\) to be the maximum of \(1^Tx\) over all fractional cliques of \(G\) where \(1\) is the all-ones vector. Use linear programming duality to prove that \(\chi(G)\geq \omega^*(G)\text{.}\)
Prove that if \(A\) is a square matrix in which every entry is an integer, then \(\det(A)\) is an integer.
Let \(A\) be an invertible matrix such that all entries of \(A\) are integers. Prove that all entries of \(A^{-1}\) are integers if and only if \(\det(A)\in\{-1,1\}\text{.}\) You may use the standard fact that \(\det(AB)=\det(A)\det(B)\) without proof.
Prove that, if \(A\) is totally unimodular, then any matrix obtained from \(A\) by adding a row in which all entries are zero except for at most one \(1\) or \(-1\) is totally unimodular.
Prove that, if \(A\) and \(B\) are totally unimodular, then the block matrix \(\begin{bmatrix}A\amp 0\\ 0\amp B\end{bmatrix}\) is totally unimodular.
Use the fact that incidence matrices of bipartite graphs are totally unimodular to reduce the maximum weight perfect matching problem for bipartite graphs to solving a linear program.
Let \(A\) be a totally unimodular matrix and let \(b\) be an integer vector. Suppose that \(x\) is an integer vector such that \(Ax\leq 2b\) and \(x\geq0\text{.}\) Prove that there exist integer vectors \(y,z\) such that all of the following hold simultaneously: \(Ay\leq b\text{,}\)\(Az\leq b\text{,}\)\(y\geq0\text{,}\)\(z\geq0\) and \(y+z=x\text{.}\)Hint:Exercise 6 and/or Exercise 7 from Section 6.4 may help, depending on your approach. You may use them without proof. There is more than one way to solve this; some ways are easier than others.
Prove that the determinant of the incidence matrix of an odd cycle is equal to \(2\) or \(-2\text{,}\) depending on how you order the rows/columns.
For a digraph \(D\) with vertices \(v_1,\dots,v_n\) and arcs \(a_1,\dots,a_m\text{,}\) the incidence matrix is the \(n\times m\) matrix in which the entry on the \(i\)th row and \(j\)th column is \(1\) if \(a_j\) starts at \(v_i\text{,}\) it is \(-1\) if \(a_j\) enters \(v_i\) and \(0\) otherwise. Prove that the incidence matrix of any digraph is totally unimodular.
A matrix \(A\) is called an interval matrix if it is \(\{0,1\}\)-valued and all of the \(1\)s on each row are consecutive. Show that, if \(A\) is a square interval matrix, then \(BA^T\) has at most one \(1\) and at most one \(-1\) in each column and all other entries are \(0\) (here, \(B\) is the matrix from the previous part of the question). Use this (and results from other parts of this exercise) to prove that all interval matrices are totally unimodular.
Use the first part of Exercise 11 to prove the Max-Flow Min-Cut Theorem.
