MAX &SEPARATED MATCJ-JJNG INSTANCE: Graph G(V, E) and positive integer k. QUESTJON : Does G have a a-separated matching of size 2 k? Theorem 2.1. For each fixed 8 3 2, MAX &SEPARATED MATCHING is NP-complete. Moreover, this is true when restricted to bipartite graphs of degree 4. Proof. Fix some 6 a 2. Clearly the problem belongs to NP. We show that the NY-complete Vertex Cover Problem for graphs of degree 3 [2,3] is reducible to MAX S-SEPARATED MATCHING. VERTEXCOVER INSTANCE: QUESTION: Graph H(V, E) of degree 3, and integer k.
Using this information:
"MAX &SEPARATED MATCJ-JJNG INSTANCE: Graph G(V, E) and positive integer k. QUESTJON : Does G have a a-separated matching of size 2 k? Theorem 2.1. For each fixed 8 3 2, MAX &SEPARATED MATCHING is NP-complete. Moreover, this is true when restricted to bipartite graphs of degree 4. Proof. Fix some 6 a 2. Clearly the problem belongs to NP. We show that the NY-complete Vertex Cover Problem for graphs of degree 3 [2,3] is reducible to MAX S-SEPARATED MATCHING. VERTEXCOVER INSTANCE: QUESTION: Graph H(V, E) of degree 3, and integer k. Does H have a vertex cover of size or {bj, Cj} can be put in 9; this is a total of m edges. Say now that G has a a-separated matching M of size aam-l-n- k + 2m(6 - 2). There are two slightly different cases. Case 1. 6 = 2. (In this case there are no spikes.) We first transform M to a &separated matching M’ with IM’I 5 IMI such that (a) M’ contains no cross-edges, (b) for each j, 1 s j G m, M’ contains either {aj, cj] or {bj, cj}* If M contains a cross-edge e incident on Vi, M cannot contain {ui, vi}, SO we obtain another 6- separated matching by removing e from M and adding { ui, Vi}. Continue in this way until all cross-edges are removed. Now, if M contains neither {aj, cj} nor (bj, cj} for some j, add {aj, Cj} to M; if the v-edge at distance 1 from {aj, Cj} is in M, remove this v-edge from M. After M is transformed to M’, let C be the set of Vi such that ( ui, Vi} is not in M’. Property (a) of M’ ensures that ICI Q k, and property (b) ensures that C is a vertex cover for H. Case 2. 8 a 3. The only difference in the proof is the argument used to transform M to M’ satisfying (a) and (b). First, if M contains a spike edge e which is not a tip, remove e from M and add the tip of e’s spike. If M contains a cross-edge e, at least one endpoint of e is incident on a spike. No edge of this spike, being at distance less than 6 from e, can be in M. Therefore, we obtain another &separated matching by removing e and adding the tip of this spike. The method of transforming M to satisfy (b) is the same as in Case 1. The rest of the proof is also the same as above. "
Can you solve this using vertex-cover:
Consider the following generalization of the maximum matching problem, which we call Strict-Matching. Recall that a matching in an undirected graph G = (V, E) is a set of edges such that no distinct pair of edges {a, b} and {c, d} have endpoints that are equal: {a, b} ∩ {c, d} = ∅. Say that a strict matching is matching with the property that no pair of distinct edges have endpoints that are connected by an edge: {a, c} ̸∈ E, {a, d} ̸∈ E, {b, c} ̸∈ E, and {b, d} ̸∈ E. (Since a strict matching is also a matching, we also require {a, b} ∩ {c, d} = ∅.) The problem Strict-Matching is then given a graph G and an integer k, does G contain a strict matching with at least k edges. Prove that Strict-Matching is NP-complete.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
