Report

LP-Based Parameterized Algorithms for Separation Problems D. Lokshtanov, N.S. Narayanaswamy V. Raman, M.S. Ramanujan S. Saurabh Message of this talk It was open for quite a while whether Odd Cycle Transversal and Almost 2-Sat are FPT. A simple branching algorithm for Vertex Cover known since the mid 90’s solves both problems in time ∗ (4 ). Some more work gives ∗ (2.32 ). Results 4− [CPPW11] ≤ (Above LP) Multiway Cut ≤ 2.32− (Above LP) Vertex Cover 2.32 ≤ Almost 2-SAT 2.32 Odd Cycle Transversal How does one get a 4k-LP algorithm? Branching: on both sides k-LP decreases by at least ½. How to improve? Decrease k-LP more. Multiway Cut In: Graph G, set T of vertices, integer k. Question: ∃ ⊆ such that no component of G\S has at least two vertices of T? FPT by Marx, 04 Faster FPT by Chen et al, 07 Fastest FPT and FPT/k-LP by Cygan et al, 11 Vertex Cover In: G, t Question: ∃ ⊆ , ≤ t such that every edge in G has an endpoint in S? Long story... Here: ∗ (2.32− ). Almost 2-SAT In: 2-SAT formula , integer k Question: Can we remove k variables from and make it satisfiable? FPT by Razgon and O’Sullivan, 08 Here: ∗ (2.32 ). Odd Cycle Transversal In: G, k Question: ∃ ⊆ , ≤ k such that G\S is bipartite? FPT: ∗ (3 ) by Reed et al. Here: ∗ (2.32 ). Vertex Cover In: G, t Question: ∃ ⊆ , ≤ t such that every edge in G has an endpoint in S? Minimize ∑ ∀ ∈ : + ≥ 1 ≥ 0 ∈ Z Vertex Cover Above LP In: G, t Question: ∃ ⊆ , ≤ t such that every edge in G has an endpoint in S? Running Time: ∗ ( − ), where LP is the value of the optimum LP solution. = − Odd Cycle Transversal Almost 2-Sat ∨ ¬ x y x ¬ ∨ y ¬ ∨ ∨ ¬ z ¬ ∨ ∨ ¬ z Almost 2-SAT Vertex Cover/t-LP ∨ ∨ ¬ ¬ ¬ ¬ Nemhauser Trotter Theorem (a) There is always an optimal solution to Vertex 1 Cover LP that sets variables to {0 , , 1}. 2 1 , , 1}–solution 2 (b) For any {0 there is a matching from the 1-vertices to the 0-vertices, saturating the 1-vertices. Nemhauser Trotter Proof +ϵ -ϵ +ϵ < -ϵ > -ϵ Reduction Rule If exists optimal LP solution that sets xv to 1, then exists optimal vertex cover that selects v. Remove v from G and decrease t by 1. Correctness follows from Nemhauser Trotter Polynomial time by LP solving. Branching Pick an edge uv. Solve (G\u, t-1) and (G\v, t-1). LP(G\u) > LP(G) – 1 since otherwise there is an optimal LP solution for G that sets u to 1. Then LP(G\u) ≥ LP(G) − 1 2 Branching - Analysis LP – t drops by ½ ... in both branches! ≤ 2 − 1 2 ≤ 4 Total time: ∗ (4− ) Caveat: The reduction does not increase the measure! Moral Nemhauser Trotter reduction + classic «branch on an edge» gives ∗ 4− time algorithm for Vertex Cover and ∗ 4 time algorithm for Odd Cycle Transversal and Almost 2-Sat. Can we do better? Surplus The surplus of a set I is |N(I)| – |I|. The surplus can be negative! 1 , , 1}-LP 2 In any {0 solution, the total weight is n/2 + surplus(V0)/2. Solving the Vertex Cover LP is equivalent to finding an independent set I of minimum surplus. Surplus and Reductions If «all ½» is the unique LP optimum then surplus(I) > 0 for all independent sets. Can we say anything meaningful for independent sets of surplus 1? 2? k? Surplus Branching Lemma Let I be an independent set in G with minimum surplus. There exists an optimal vertex cover C that either contains I or avoids I. Surplus Branching Lemma Proof ∩ \ I N(I) R Branching Rule Find an independent set I of minimum surplus. Solve (G\I, t-|I|) and (G\N(I), t-|N(I)|). LP(G\I) > LP(G) - |I|, since otherwise LP(G) has an optimal solution that sets I to 1. So \I ≥ − + t-LP drops by at least ½. 1 2 Branching Rule Analysis Cont’d Analyzing the (G\N(I), t-N(I)) side: LP(G\N(I)) + |N(I)| = n/2 + surplus(I)/2 ≥ LP G + surplus(I)/2 So LP(G\N(I)) ≥ LP(G) − |N(I)| + surplus(I)/2 t-LP drops by at least surplus(I)/2 Branching Summary The measure k-LP drops by (½, surplus(I)/2). Will see that independent sets of surplus 1 can be reduced in polynomial time! Measure drops by (½,1) giving a ∗ 2.618− time algorithm for Vertex Cover Reducing Surplus 1 sets. Lemma: If surplus(I) = 1, I has minimum surplus and N(I) is not independent then there exists an optimum vertex cover containing N(I). I N(I) R Reducing Surplus 1 sets. Reduction Rule: If surplus(I) = 1, I has minimum surplus and N(I) is independent then solve (G’,t-|I|) where G’ is G with N[I] contracted to a single vertex v. I N(I) R Summary Nemhauser Trotter lets us assume surplus > 0 More rules let us assume surplus > 1 (≥ 2)* If surplus ≥ 2 then branching yields ∗ 2.618− time for Vertex Cover The correctness of these rules were also proved by NT! Can we do better? Can get down to ∗ (2.32− ) by more clever branching rules. Yields ∗ (2.32− ) for Almost 2-SAT and Odd Cycle Transversal. Should not be the end of the story. Better OCT? Can we get down to ∗ (2 ) for Odd Cycle Transversal? LP Branching in other cases I believe many more problems should have FPT algorithms by LP-guided branching. What about ... (Directed) Feedback Vertex Set, parameterized by solution size k?