LP-Based Parameterized Algorithms for Separation

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?

similar documents