CAAM 476 & INDE 546 — Spring 22
Bonus Homework (Optional)
Due Date: May 3, 2022 (Tuesday)
This assignment concerns a simple (1+ k )-approximation algorithm for the maximum k-dependent
Copyright By PowCoder代写 加微信 powcoder
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 34 and 32, 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 aswellas∀i,j∈V2 (thereisnoedgebetweenanypairof 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 ̸= k, i ̸= l, j ̸= k, and j ̸= l, ∀{i,j}, {k,l} ∈ 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.
• 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.
• 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 e∈E xe
s.t. e∈δ(i) xe ≤ 1, ∀i ∈ V, (1)
xe ∈{0,1}, ∀e∈E.
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 e∈E xe
s.t. e∈δ(i) xe ≤ 1, ∀i ∈ V, (2)
xe ≥0, ∀e∈E.
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 LP- relaxation 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 i∈V yi
s.t. yi +yj ≥1, ∀{i,j}∈E, (3)
yi ≥0, ∀i∈V. 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 i∈V yi
s.t. yi +yj ≥1, ∀{i,j}∈E, (4)
yi ∈{0,1}, ∀i∈V.
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 )-approximation algorithm for the maximum k-dependent set problem k+2
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.
References
[1] and . An improved approximation for max- imum k-dependent set on bipartite graphs. Discrete Applied Mathematics, 307:95–101, 2022.
[2] . A short proof of matching theorem. Journal of Graph Theory, 33:138–139, 2000.
3Again, dropping the constraint yi ≤ 1, ∀i ∈ V , in the LP-relaxation problem does not harm the formulation, as “minimization” of the objective function guarantees the value of non-zero variables in an optimal solution will not exceed 1.
4The paper is available on Canvas.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com