This assignment concerns a simple (1+ k
k+2 )-approximation algorithm for the maximum k-dependent
set problem on bipartite graphs, proposed in [1]. To have a better understanding of the proof of
its approximation ratio, I recommend considering small (fixed) values of k, e.g., k = 1 and k = 2,
which lead to the approximation ratios of 4
3
and 3
2
, respectively. Some background graph-theory
definitions and terminology are presented next.
Bipartite Graph. A simple, undirected graph is called bipartite if its vertex set can be partitioned
into two sets of pairwise nonadjacent vertices; that is, G = (V, E) is bipartite if V = V1 ∪ V2,
V1 ∩ V2 = ∅, and {i, j} ∈/ E, ∀i, j ∈ V1 as well as ∀i, j ∈ V2 (there is no edge between any pair of
vertices in the same part).
Independent Set. Given a simple, undirected graph G = (V, E), an independent set is a subset
of pairwise nonadjacent vertices; that is, I ⊆ V is called an independent set if {i, j} ∈/ E, ∀i, j ∈ I,
or equivalently, if the subgraph induced by I, denoted by G[I], has no edge. The maximum
independent set problem is to find an independent set of maximum cardinality (largest) in G.
k-dependent Set. Given a simple, undirected graph G = (V, E), a subset of vertices I ⊆ V is
called a k-dependent set, k ≥ 1, if the degree of every vertex in G[I] is at most k. Note that an
independent set can be seen as a 0-dependent set (k = 0) by this definition; hence, the concept
of “k-dependent set” generalizes “independent set”. The maximum k-dependent set problem is to
find a k-dependent set of maximum cardinality (largest) in G.
Matching. Given a simple, undirected graph G = (V, E), a subset of edges M ⊆ E is called
a matching if no pair of them share an end-vertex; that is, i 6= k, i 6= `, j 6= k, and j 6=
`, ∀{i, j}, {k, `} ∈ M. The maximum (cardinality) matching problem is to find a matching of
maximum cardinality (largest) in G.
Vertex Cover. Given a simple, undirected graph G = (V, E), a subset of vertices C ⊆ V is
called a vertex cover if every edge in the graph has at least one end-vertex in C; that is, i ∈ C
or j ∈ C, ∀{i, j} ∈ E. The minimum vertex cover problem is to find a vertex cover of minimum
cardinality (smallest) in G.
Facts:
• The complement of every independent set is a vertex cover; if I is an independent set, then every
edge in the graph must have an end-vertex in V \I;
1 hence, C = V \I is a vertex cover. This
immediately implies |V | = |I| + |C| for every independent set I and vertex cover C = V \I.
2
In
particular, the complement of a maximum independent set is indeed a minimum vertex cover.
1B\A is the set of elements in the set B that are not in the set A; this is the correct set notation, but sometimes
people write B − A.
2
|A| denotes the cardinality of A.
1
• The cardinality of a minimum vertex cover is always greater than or equal to the cardinality of
a maximum matching in a graph; for every edge in a maximum matching M, one end-vertex
must be included in a (minimum) vertex cover C, but there may exist edges in E\M which do
not share any end-vertex with an edge in M and need to be covered by adding more vertices to
C. For bipartite graphs, the cardinality of a minimum vertex cover and the cardinality of a
maximum matching are equal; this result is known as the K¨onig-Egerv´ary matching theorem [2].
• The maximum independent set, maximum k-dependent set, and minimum vertex cover problems
are NP-hard in general. For bipartite graphs, the maximum independent set and minimum
vertex cover problems are polynomial-time solvable, but the maximum k-dependent set problem,
k ≥ 1, remains NP-hard. The maximum matching problem is polynomial-time solvable on general
graphs, hence on bipartite graphs.
• The maximum bipartite matching problem, i.e., finding a maximum matching on a bipartite
graph, has a very interesting property: an integer-programming formulation of this problem
has a totally unimodular (TU) coefficient matrix. A matrix is called TU if the determinant of
any of its square submatrices is −1 or 0 or 1. The importance of this result is due to the fact
that, if A is TU and b is integral, it can be shown that every extreme point of the polytope
P = {x | Ax ≤ b, x ≥ 0} is integral. Consider the following integer-programming formulation of
the maximum matching problem:
max P
e∈E
xe
s.t. P
e∈δ(i)
xe ≤ 1, ∀i ∈ V,
xe ∈ {0, 1}, ∀e ∈ E.
(1)
The constraints guarantee that, among the edges incident to any vertex i ∈ V , at most one will
have the value 1 in an optimal solution, i.e., the set of edges whose variables have the value 1 in an
optimal solution of (1) is a matching in G = (V, E). The coefficient matrix of formulation (1) is
the incidence matrix of the graph with n := |V | rows and m := |E| columns; an entry [i][e] of this
matrix is 1 if the vertex i ∈ V is incident to the edge e ∈ E, and 0 otherwise. It can be shown
that the incidence matrix of a bipartite graph is TU. Now, consider the LP-relaxation
of (1) and observe that dropping the constraint xe ≤ 1, ∀e ∈ E, will not harm the formulation,
as it is implied by the main constraints:
max P
e∈E
xe
s.t. P
e∈δ(i)
xe ≤ 1, ∀i ∈ V,
xe ≥ 0, ∀e ∈ E.
(2)
The facts that the coefficient matrix of (2), i.e., the incidence matrix of a bipartite graph G,
is TU and the right-hand side is integral, i.e., 1, imply that the optimal solution of the LPrelaxation problem (2) is integral (every variable is either 0 or 1); hence, it is feasible to the
original integer-programming formulation (1) and optimal. Therefore, the maximum bipartite
matching problem can be solved as a linear-programming problem through formulation (2).
• The dual of the linear-programming problem (2) is as follows:
min P
i∈V
yi
s.t. yi + yj ≥ 1, ∀{i, j} ∈ E,
yi ≥ 0, ∀i ∈ V.
(3)
2
It is easy to verify that the linear-programming formulation (3) is indeed the LP relaxation of
an integer-programming formulation of the minimum vertex cover problem on G 3
, as follows:
min P
i∈V
yi
s.t. yi + yj ≥ 1, ∀{i, j} ∈ E,
yi ∈ {0, 1}, ∀i ∈ V.
(4)
Patently, the coefficient matrix of (3) is the transpose of the coefficient matrix of (2), and by
the definition of TU matrices, is TU as well. Therefore, the minimum vertex cover problem on
bipartite graphs can be solved as a linear-programming problem through formulation (3). More
importantly, given an optimal solution to the maximum bipartite matching problem, one can use
the primal-dual relationship between (2) and (3), i.e., Complementary Slackness Theorem, to
construct an optimal solution to the vertex cover problem—hence, the maximum independent
set problem—on the same (bipartite) graph.
Assignments:
For the following assignment, submit your code as a .ipynb. or .py file. You will receive credit only
if your code runs with no error, generates the requested output, and produces a correct solution on
a test instance.
1. Implement the (1 + k
k+2 )-approximation algorithm for the maximum k-dependent set problem
on bipartite graphs, presented in [1].4 Your code should read an input graph given by the list
of edges from a .txt file, similar to the instances provided for Final Project. It should first
decide whether or not the input graph is bipartite; if not, it should output an error message,
e.g., ‘‘The input graph is NOT bipartite!’’ On a bipartite input graph, it should ask
the user for the value of k, run the algorithm, and output an approximation solution, i.e., a
list of vertices. Instead of the Hopcroft-Karp algorithm to find maximum matchings
(and independent set in the residual graph), you may use GUROBI to solve these
problems as linear programs, as explained above.
2. Present a 2-approximation algorithm for the maximum k-dependent set problem on bipartite
graphs (for any k ≥ 1). What is the time complexity of your algorithm? For this question,
submit your solution as a single .pdf file.
