Applications of Treewidth in Algorithm Design
Applications of Treewidth in
Algorithm Design
Daniel Lokshtanov
Based on joint work with Hans Bodlaender ,Fedor
Fomin,Eelko Penninkx, Venkatesh Raman, Saket Saurabh
and Dimitrios Thilikos
Background
Most interesting graph problems are
NP-hard
on
general graphs.
Often input graphs are
planar
or
almost planar
.
Can this be used to give efficient algorithms?
Most interesting graph problems
remain NP-
hard
on
planar graphs
.
Are planar graphs as hard as general
graphs?
On planar graphs many problems admit:
-
Faster
exact algorithms
.
-
Faster
parameterized algorithms
.
-
Good preprocessing rules (
kernels
).
-
Better
approximation algorithms
.
Case Study: Dominating Set
Bidimensionality [DFHT]
A
framework
that gives fast exact algorithms,
paramterized algorithms, kernels and
approximation schemes for problems on
planar
graphs
.
Main tool:
Graph Minors
theory of Robertson and
Seymour.
Extends
to larger classes of graphs.
Here
; only
planar graphs.
Preliminaries
Problems considered
Input:
G
Max / Min:
κ
(G,S)
(S
⊆
V(G) / S
⊆
E(G))
Subject to:
φ
(G,S)
Technical note: we demand that
κ
(G,S) ≤ |S|
and that
κ
(G,OPT) = |OPT|
.
Value of optimal solution on
G =
π
(G)
.
Minors and Contractions
H
is a
minor
of
G
(
H ≤
m
G
)if
H
can be obtained
from
G
by a sequence of
edge contractions
,
edge deletions
and
vertex deletions
.
H
is a
contraction
of
G
(
H ≤
c
G
) if
H
can be
obtained from
G
by a sequence of
edge
contractions
.
g
rids and
Γ
ammas
g
4
Γ
4
Bidimensionality
A problem
Π
is
(minor)-bidimensional
if:
–
If
H ≤
m
G
then
π
(H) ≤
π
(G)
.
–
There is a constant
c
such that
π
(g
t
) ≥ ct
2
.
A problem
Π
is
contraction-bidimensional
if:
–
If
H ≤
c
G
then
π
(H) ≤
π
(G)
.
–
There is a constant
c
such that
π
(
Γ
t
) ≥ ct
2
.
Examples of Bidimensional problems
•
Vertex Cover
,
Feedback Vertex Set
,
Longest
Path
and
Cycle Packing
are
minor-
bidimensional
.
•
Dominating Set
,
Connected Vertex Cover
and
Independent Set
are
contraction-
bidimensional
.
Facts about
Treewidth
1.
Many graph probems can be solved in
2
O(tw(G))
n
time.
2.
If
H ≤
m
G
then
tw(H) ≤ tw(G)
.
3.
The treewidth of
g
k
is
k
.
4.
Every graph
G
has a
balanced separator
of size
tw(G)
.
5.
On
planar
graphs, treewidth is constant factor
approximable.
Excluded Grid Theorem
Theorem [RS]:
Every planar graph
G
contains
g
(1/6)*tw(G)
as a
minor
.
Excluded
Γ
amma Theorem
Theorem [FGT]:
There exists a constant c such
that every planar graph
G
contains
Γ
c*tw(G)
as a
contraction
.
Subexponential Parameterized
Algorithms
Parameter-treewidth bound
Lemma [Parameter-treewidth bound]:
For
every bidimensional problem
Π
there is a
constant
c
such that for any
planar graph
G,
tw(G) ≤ c
π
(G)
1/2
Proof:
By excluded grid theorem,
g
c*tw(G)
≤
m
G
.
Since
Π
is bidimensional,
π
(g
c*tw(G)
) ≥ c’tw(G)
2
.
Since
Π
is minor closed,
π
(G) ≥ c’tw(G)
2
.
Algorithm on planar graphs
Constant-factor approximate treewidth. Output
a decomposition of width
t =
O(
π
(G)
1/2
)
.
Solve problem in
2
O(t)
n
(or
t
O(t)
n
) time. Total time
taken is
2
π
(G)
1/2
n
(or
π
(G)
π
(G)
1/2
n
).
More general graph classes
Note:
The only place we used planarity was for
the
excluded grid theorem
. So results hold on
H-minor-free
graphs for
minor-bidimensional
problems and
apex-minor-free
graphs for
contraction-bidimensional
problems.
Exercise 1:
Prove:
For any fixed
d
,
if
G
is
planar
and
has a
set
X
such that
tw(G \ X) ≤ d
then
tw(G) ≤ d +
O(|X|
1/2
)
.
Soln:
Vertex deletion into treewidth
d
graphs is
minor closed and at least
(t/(d+1))
2
on
g
t
grids.
Approximation
Separability
Want:
EPTASes
for all bidimensional problems
on planar graphs.
Can’t handle
Longest Path
. Parameter-
treeewidth bound is not enough, but ”almost
enough”.
Separability
A problem
Π
is
separable
*
if for any partition of
V(G)
into
L
,
S
,
R
such that there is no edge
from
L
to
R
, and optimal solution
OPT
⊆
V(G)
:
-
π
(G \ R) ≤
κ
(G \ R, OPT \ R) + O(|S|)
-
π
(G \ L) ≤
κ
(G \ L, OPT \ L) + O(|S|)
*
For contraction-bidimensional problems a slightly different definition is used.
Think ”OPT of left hand side”
Excercise 2
Show that
Vertex Cover
is separable.
Solution:
OPT \ R
is a feasible solution for
G[L
∪
S]
. Hence
π
(G \ R) ≤ |OPT \ R|
.
Exercise 3:
Show that
Independent Set
is separable.
Solution:
Let
OPT
be a maximum independent set of
G
.
Suppose
π
(G \ R) > |OPT \ R| + |S|
.
Then
π
(G[L]) > |OPT \ R|
Then
G
has an independent set of size:
π
(G[L]) + |OPT ∩ R| > |OPT \ R| + |OPT ∩ R| =|OPT|
.
Decomposition Theorem
Theorem:
For any
minor-bidimensional
,
separable
problem
Π
on
planar
graphs, there
is a function
f : N
N
and polynomial time
algorithm that given
G
and
ε
> 0
outputs a set
X
such that
-
|X| ≤
επ
(G)
-
tw(G \ X) ≤ f(
ε
)
.
Exercise 4:
Assume
Feedback Vertex Set
(
FVS
)
is
minor-
bidimensional
,and
separable
. Give an
EPTAS
for
FVS
on
planar
graphs using the
decomposition theorem.
Solution:
For a fixed
ε
and given
G
find
X
. Solve
FVS
optimally on
G \ X
in
g(
ε
)n
time. Add
X
to
the solution. Solution size
≤ (1+
ε
)
π
(G)
.
Decomposition
’
Theorem
Theorem:
For any
contraction-bidimensional
,
separable
problem
Π
on
planar
graphs, there
is a function
f : N
N
and polynomial time
algorithm that given
G
and
ε
> 0
outputs a set
X
such that
-
|X| ≤
επ
(G)
-
tw(G \ X) ≤ f(
ε
)
.
Example
Dominating Set
(
DS
)
is
contraction-
bidimensional
,and
separable
. Thus it has an
EPTAS
for on
planar
graphs.
Proof:
For a fixed
ε
and given
G
find
X
using
decomposition’
. Mark
N(X)
. Find a smallest set
S
in
G\X
that dominates all unmarked vertices
of
G\X
. Now
S
∪
X
is a
DS
of
G
of size
≤
(1+
ε
)
π
(G)
.
Remainder of talk:
Proof Sketch of Decomposition
Theorem
Balanced Separator Lemma
For any graph
G
of treewidth
t
and vertex set
X
there is a partition of
V(G)
into
L
,
S
,
R
such
that:
-
There is no edge between
L
and
R
-
The separator
S
is small;
|S| ≤ t+1
.
-
The separator is balanced;
|X ∩ L| ≤ 2|X|/3
and
|X ∩ R| ≤ 2|X|/3
W
eak,
N
on-constructive,
D
ecomposition
T
heorem
WNDT:
For any
minor-bidimensional
,
separable
problem
Π
on
planar
graphs, there
exists a
constant
c
such that any instance
G
has a
vertex set
X
such that
-
|X| ≤ c
π
(G)
-
tw(G \ X) ≤ c
.
WNDT
Proof
1.
By
parameter-treewidth bound
, there is a
constant
d
such that
tw(G) ≤ d
π
(G)
1/2
.
2.
Let
T(k)
be the smallest number
t
such that
any
planar
graph
G
with
π
(G) = k
contains a
set
X
of size
t
such that
tw(G \ X) ≤ d
.
3.
Need to prove
T(k) = O(k)
.
4.
Base Case:
T(1) = 0
since
tw(G) ≤ d
π
(G)
1/2
≤ d
.
WNDT
recurrence
Let
Z
be an optimal solution in
G
, then
k=|Z|=
π
(G)
.
Now,
tw(G) ≤ dk
1/2
.
Balanced Separator Lemma applied to
G
,
Z
yields
decomposition of
V(G)
into
(L, S, R)
such that
|S|≤ dk
1/2
,
L ∩ Z ≤ 2|Z|/3
,
R ∩ Z ≤ 2|Z|/3
.
WNDT
recurrence
Since
Π
is separable:
π
(G \ R) ≤
κ
(G \ R, Z \ R) + O(k
1/2
)
≤ |Z\R|+ O(k
1/2
)
G\R
has a set
X
L
of size
T(|Z\R|+ O(k
1/2
) )
such
that
tw((G\R)\X
L
) ≤ d
.
G\L
has a set
X
R
of size
T(|Z\L|+ O(k
1/2
) )
such
that
tw((G\L)\X
R
) ≤ d
.
WNDT
recurrence
X = X
L
∪
X
R
∪
S
is a set of size
T(|Z\R|+ O(k
1/2
) ) + T(|Z\L|+ O(k
1/2
) ) + O(k
1/2
)
such that
tw(G \ X) ≤ d
.
Observe:
|
Z
\R| + |Z\L| ≤ |Z| + |S|
.
WNDT
recurrence
T(k) ≤ T(
⍺
k + O(k
1/2
)) + T((1-
⍺
)k + O(k
1/2
)) + O(k
1/2
)
...where
1/3 ≤
⍺
≤ 2/3
.
This solves to
T(k) = O(k)
.
Breathe Break
Questions?
Scaling Lemma
For any
c
there is a polynomial time algorithm
and a function
f : N
N
that given a
planar
graph
G
, a set
X
such that
tw(G\X) ≤ c
, and
ε
>
0
outputs a set
X’
of size
ε
|X|
such that for
any component
C
of
G \ X’
-
|C ∩ X| ≤ f(
ε
)
-
|N(C)| ≤ f(
ε
)
Proof Idea for Scaling Lemma
For a fixed
γ
let
T
γ
(k)
be the smallest integer
t
such that any
G
with
X
such that
|X|≤ k
and
tw(G\X) ≤ d
contains a set
X’
of size
≤ t
such
that for any component
C
of
G \ X’
-
|C ∩ X| ≤
γ
-
|N(C)| ≤
γ
Proof Idea for Scaling Lemma
For every
γ
> d
prove that
T
γ
(k) ≤ g(
γ
)k
where
g(
γ
)
0 as
γ
∞
.
Prove
T
γ
(k) ≤ g(
γ
)k
using balanced separation as
in the proof of
WNDL
.
Recurrence for Scaling Lemma
T
γ
(
γ
) = 0
T
γ
(k)
≤ T
γ
(
⍺
k + O(k
1/2
))
+ T
γ
((1-
⍺
)k + O(k
1/2
)) + O(k
1/2
)
...where
1/3 ≤
⍺
≤ 2/3
.
Thus
T
γ
(k) ≤ g(
γ
)k
but what is
lim g(
γ
)
when
γ
∞?
Analyzing
g(
γ
)
cheat:
set
⍺
= ½
and move lower order terms
outside function calls.
T
γ
(
γ
) = 0
T
γ
(k)
≤ 2T
γ
(½k) + O(k
½
)
Analyzing
g(
γ
)
T
γ
(
γ
) = 0
T
γ
(k)
≤ 2T
γ
(½k) + O(k
½
)
2
0
*(½
0
k)
½
= 2
0/2
k
½
2
1
*(½
1
k)
½
= 2
1/2
k
½
2
2
*(½
2
k)
½
= 2
2/2
k
½
2
3
*(½
3
k)
½
= 2
3/2
k
½
Making Proof of Scaling Lemma
constructive
Proof naturally makes a divide and conquer
algorithm for constructing
X’
from
G
,
X
and
ε
.
Making Proof of Scaling Lemma
constructive
Proof naturally makes a divide and conquer
algorithm for constructing
X’
from
G
,
X
and
ε
.
What we have, what we want
Have:
W
eak
N
onconstructive
D
ecomposition
T
heorem and Scaling Lemma
If we could make
WNDT
constructive, we would
be done!
Want:
Constant factor approximation of
”treewidth-
d
deletion” on
H
-minor free
graphs.
Protrusion Lemma
For every
d
, there are constants
c
such that for
every
planar
graph
G,
if
tw(G)>d
then there is a
vertex set
C
such that:
–
d < tw(G[C]) ≤ c
–
N(C) ≤ c
Proof:
Let
X
be smallest set such that
tw(G)<d
.
Apply Scaling Lemma on
X
with
ε
=½
. Set
c=f(½)
.
Since
X’ < X
some component
C
of
G\X’
has
tw(G[C]) > d
.
protrusion:
appendage
,
bagginess
,
blob
,
bump
,
bunch
,
bunching
,
convexity
,
dilation
,
distention
,
excess
,
excrescence
,
gibbosity
,
growth
,
hump
,
intumescence
,
jut
,
lump
,
nodulation
,
nodule
,
outgrowth
,
outthrust
,
projection
,
prominence
,
promontory
,
protuberance
,
sac
,
sagging
,
salience
,
salient
,
superfluity
,
swelling
,
tuberosity
, tumefaction,
tumor
,
wart
Approximation algorithm for
Treewidth-d deletion
Let
c
be as in Protrusion Lemma.
While
tw(G) > d
:
Find a vertex set
C
such that
d < tw(G[C]) ≤ c
and
N(C) ≤ c
.
Find best treewidth-d-deletion X
C
in
G[C].
Add
X
c
and
N(C)
to
X
.
G
G \ (C
∪
N(C))
Output
X
Approximation Ratio
We deleted
X
1
, X
2
, X
3
.... X
t
≤ OPT
N(C
1
), N(C
2
) ... N(C
t
) ≤ ct
Each
C
i
contains a vertex from
OPT
so
t ≤ |OPT|
.
Hence
|X| ≤ (c+1)|OPT|
Proof of Decomposition Theorem
By
WNDT
there exists a treewidth
d
-deletion of
size
O(
π
(G))
.
By approximation we can
find
a treewidth
treewidth
d
-deletion
X
of size
O(
π
(G))
.
By Scaling Lemma we can turn
X
into a
treewidth-
f(
ε
)
deletion set
X’
of size
ε
|X|
.
Choosing
ε
small enough we get
|X’| ≤
επ
(G).
Approximation - recap
Saw a
decomposition lemma
for
bidiemsional
,
separable
problems on
H
-minor-free graphs
and how it can be used to give
EPTAS
’es for
many problems on
H
-minor free graphs
Kernelization
The decomposition lemma can be modified as follows:
Lemma:
For any
minor-bidimensional
,
separable
problem
Π
on
H-minor-free
graphs, there is a constant
c
and
polynomial time algorithm that given
G
outputs a set
X
such that
|X| ≤ c
π
(X)
and
G\X
can be partitioned into
C
1
,
C
2
, ...
C
t
where
t ≤ c
π
(X)
such that
- there are no edges between
C
i
and
C
j
-
tw(G[Ci]) ≤ c
-
tw(G[Cj]) ≤ c
Kernelization
Each
C
i
can be replaced with a constant size
graph using techniques from
[BFLPST09]
.
Kernels of size
O(
π
(G))
.
Very Short Summary
Bidimensionality
is a framework for giving
subexponential time algorithms
,
EPTAS
’es and
kernels
, based on
excluded grid
theorems and
balanced separation
techniques.
The study delves into the efficient algorithms for graph problems using treewidth, focusing on planar and general graphs. The research investigates the complexities, parameterized algorithms, kernels, and approximation schemes for problems on planar graphs through bidimensionality, emphasizing the significance in algorithm design.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Applications of Treewidth in Algorithm Design Daniel Lokshtanov Based on joint work with Hans Bodlaender ,Fedor Fomin,Eelko Penninkx, Venkatesh Raman, Saket Saurabh and Dimitrios Thilikos
Background Most interesting graph problems are NP-hard on general graphs. Often input graphs are planar or almost planar. Can this be used to give efficient algorithms? Most interesting graph problems remain NP- hard on planar graphs.
Are planar graphs as hard as general graphs? On planar graphs many problems admit: - Faster exact algorithms. - Faster parameterized algorithms. - Good preprocessing rules (kernels). - Better approximation algorithms.
Case Study: Dominating Set General Graphs Planar Graphs 2O(n1/2) 1.49n Exact Algorithm Parameterized Complexity 2O(k1/2) W[2]-complete O(k) Kernel W[2]-complete log(n) 1+ Approximation
Bidimensionality [DFHT] A framework that gives fast exact algorithms, paramterized algorithms, kernels and approximation schemes for problems on planar graphs. Main tool: Graph Minors theory of Robertson and Seymour. Extends to larger classes of graphs. Here; only planar graphs.
Problems considered Input: G Max / Min: (G,S) (S V(G) / S E(G)) Subject to: (G,S) Technical note: we demand that (G,S) |S| and that (G,OPT) = |OPT|. Value of optimal solution on G = (G).
Minors and Contractions H is a minor of G (H mG)if H can be obtained from G by a sequence of edge contractions, edge deletions and vertex deletions. H is a contraction of G (H cG) if H can be obtained from G by a sequence of edge contractions.
grids and ammas g4 4
Bidimensionality A problem is (minor)-bidimensional if: If H m G then (H) (G). There is a constant c such that (gt) ct2. A problem is contraction-bidimensional if: If H c G then (H) (G). There is a constant c such that ( t) ct2.
Examples of Bidimensional problems Vertex Cover, Feedback Vertex Set, Longest Path and Cycle Packing are minor- bidimensional. Dominating Set, Connected Vertex Cover and Independent Set are contraction- bidimensional.
Facts about Treewidth 1. Many graph probems can be solved in 2O(tw(G))n time. 2. If H m G then tw(H) tw(G). 3. The treewidth of gk is k. 4. Every graph G has a balanced separator of size tw(G). 5. On planar graphs, treewidth is constant factor approximable.
Excluded Grid Theorem Theorem [RS]: Every planar graph G contains g(1/6)*tw(G) as a minor.
Excluded amma Theorem Theorem [FGT]: There exists a constant c such that every planar graph G contains c*tw(G) as a contraction.
Subexponential Parameterized Algorithms
Parameter-treewidth bound Lemma [Parameter-treewidth bound]: For every bidimensional problem there is a constant c such that for any planar graph G, tw(G) c (G)1/2 Proof: By excluded grid theorem, gc*tw(G) m G. Since is bidimensional, (gc*tw(G)) c tw(G)2. Since is minor closed, (G) c tw(G)2.
Algorithm on planar graphs Constant-factor approximate treewidth. Output a decomposition of width t = O( (G)1/2). Solve problem in 2O(t)n (or tO(t)n) time. Total time taken is 2 (G)1/2n (or (G) (G)1/2n).
More general graph classes Note: The only place we used planarity was for the excluded grid theorem. So results hold on H-minor-free graphs for minor-bidimensional problems and apex-minor-free graphs for contraction-bidimensional problems.
Exercise 1: Prove: For any fixed d, if G is planar and has a set X such that tw(G \ X) d then tw(G) d + O(|X|1/2). Soln: Vertex deletion into treewidth d graphs is minor closed and at least (t/(d+1))2 on gt grids.
Separability Want: EPTASes for all bidimensional problems on planar graphs. Can t handle Longest Path. Parameter- treeewidth bound is not enough, but almost enough . (1+ )-approximation in f( )poly(n) time.
Separability A problem is separable* if for any partition of V(G) into L, S, R such that there is no edge from L to R, and optimal solution OPT V(G): - (G \ R) (G \ R, OPT \ R) + O(|S|) - (G \ L) (G \ L, OPT \ L) + O(|S|) Think OPT of left hand side *For contraction-bidimensional problems a slightly different definition is used.
Excercise 2 Show that Vertex Cover is separable. Solution: OPT \ R is a feasible solution for G[L S]. Hence (G \ R) |OPT \ R|.
Exercise 3: Show that Independent Set is separable. Solution: Let OPT be a maximum independent set of G. Suppose (G \ R) > |OPT \ R| + |S|. Then (G[L]) > |OPT \ R| Then G has an independent set of size: (G[L]) + |OPT R| > |OPT \ R| + |OPT R| =|OPT|.
Decomposition Theorem Theorem: For any minor-bidimensional, separable problem on planar graphs, there is a function f : N N and polynomial time algorithm that given G and > 0 outputs a set X such that - |X| (G) - tw(G \ X) f( ).
Exercise 4: Assume Feedback Vertex Set (FVS) is minor- bidimensional,and separable. Give an EPTAS for FVS on planar graphs using the decomposition theorem. Solution: For a fixed and given G find X. Solve FVS optimally on G \ X in g( )n time. Add X to the solution. Solution size (1+ ) (G).
Decomposition Theorem Theorem: For any contraction-bidimensional, separable problem on planar graphs, there is a function f : N N and polynomial time algorithm that given G and > 0 outputs a set X such that - |X| (G) - tw(G \ X) f( ).
Example Dominating Set (DS) is contraction- bidimensional,and separable. Thus it has an EPTAS for on planar graphs. Proof: For a fixed and given G find X using decomposition . Mark N(X). Find a smallest set S in G\X that dominates all unmarked vertices of G\X. Now S X is a DS of G of size (1+ ) (G).
Remainder of talk: Proof Sketch of Decomposition Theorem
Balanced Separator Lemma For any graph G of treewidth t and vertex set X there is a partition of V(G) into L, S, R such that: - There is no edge between L and R - The separator S is small; |S| t+1. - The separator is balanced; |X L| 2|X|/3 and |X R| 2|X|/3
Weak, Non-constructive, Decomposition Theorem WNDT: For any minor-bidimensional, separable problem on planar graphs, there exists a constant c such that any instance G has a vertex set X such that - |X| c (G) - tw(G \ X) c.
WNDT Proof 1. By parameter-treewidth bound, there is a constant d such that tw(G) d (G)1/2. 2. Let T(k) be the smallest number t such that any planar graph G with (G) = k contains a set X of size t such that tw(G \ X) d. 3. Need to prove T(k) = O(k). 4. Base Case: T(1) = 0 since tw(G) d (G)1/2 d.
WNDT recurrence Let Z be an optimal solution in G, then k=|Z|= (G). Now, tw(G) dk1/2. Balanced Separator Lemma applied to G,Z yields decomposition of V(G) into (L, S, R) such that |S| dk1/2 , L Z 2|Z|/3, R Z 2|Z|/3.
WNDT recurrence Since is separable: (G \ R) (G \ R, Z \ R) + O(k1/2) |Z\R|+ O(k1/2) G\R has a set XL of size T(|Z\R|+ O(k1/2) ) such that tw((G\R)\XL) d. G\L has a set XR of size T(|Z\L|+ O(k1/2) ) such that tw((G\L)\XR) d.
WNDT recurrence X = XL XR S is a set of size T(|Z\R|+ O(k1/2) ) + T(|Z\L|+ O(k1/2) ) + O(k1/2) such that tw(G \ X) d. Observe: |Z\R| + |Z\L| |Z| + |S|.
WNDT recurrence T(k) T( k + O(k1/2)) + T((1- )k + O(k1/2)) + O(k1/2) ...where 1/3 2/3. This solves to T(k) = O(k).
Breathe Break Questions?
Scaling Lemma For any c there is a polynomial time algorithm and a function f : N N that given a planar graph G, a set X such that tw(G\X) c, and > 0 outputs a set X of size |X| such that for any component C of G \ X - |C X| f( ) - |N(C)| f( ) Implies tw(G[C]) f ( )
Proof Idea for Scaling Lemma For a fixed let T (k) be the smallest integer t such that any G with X such that |X| k and tw(G\X) d contains a set X of size t such that for any component C of G \ X - |C X| - |N(C)|
Proof Idea for Scaling Lemma For every > d prove that T (k) g( )k where g( ) 0 as . Prove T (k) g( )k using balanced separation as in the proof of WNDL.
Recurrence for Scaling Lemma T ( ) = 0 See board T (k) T ( k + O(k1/2)) + T ((1- )k + O(k1/2)) + O(k1/2) ...where 1/3 2/3. Thus T (k) g( )k but what is lim g( ) when ?
Analyzing g() cheat: set = and move lower order terms outside function calls. T ( ) = 0 T (k) 2T ( k) + O(k )
Analyzing g() T (k) 2T ( k) + O(k ) T ( ) = 0 20 *( 0k) = 20/2k 21 *( 1k) = 21/2k 22 *( 2k) = 22/2k 23 *( 3k) = 23/2k
Making Proof of Scaling Lemma constructive Proof naturally makes a divide and conquer algorithm for constructing X from G, X and .
Making Proof of Scaling Lemma constructive Proof naturally makes a divide and conquer algorithm for constructing X from G, X and .
What we have, what we want Have: Weak Nonconstructive Decomposition Theorem and Scaling Lemma If we could make WNDT constructive, we would be done! Want: Constant factor approximation of treewidth-d deletion on H-minor free graphs.
Protrusion Lemma For every d, there are constants c such that for every planar graph G, if tw(G)>d then there is a vertex set C such that: d < tw(G[C]) c N(C) c outgrowth, outthrust, projection, prominence, promontory, protuberance, sac, sagging, salience, salient, superfluity, swelling, tuberosity, tumefaction, tumor, wart protrusion: appendage, bagginess, blob, bump, bunch, bunching, convexity, dilation, distention, excess, excrescence, gibbosity, growth, hump, intumescence, jut, lump, nodulation, nodule, Proof: Let X be smallest set such that tw(G)<d. Apply Scaling Lemma on X with = . Set c=f( ). Since X < X some component C of G\X has tw(G[C]) > d.
Approximation algorithm for Treewidth-d deletion Let c be as in Protrusion Lemma. While tw(G) > d: Find a vertex set C such that d < tw(G[C]) c and N(C) c. Find best treewidth-d-deletion XC in G[C]. Add Xc and N(C) to X. G G \ (C N(C)) Output X
Approximation Ratio We deleted X1, X2, X3.... Xt OPT N(C1), N(C2) ... N(Ct) ct Each Ci contains a vertex from OPT so t |OPT|. Hence |X| (c+1)|OPT|
Proof of Decomposition Theorem By WNDT there exists a treewidth d-deletion of size O( (G)). By approximation we can find a treewidth treewidth d-deletion X of size O( (G)). By Scaling Lemma we can turn X into a treewidth- f( ) deletion set X of size |X|. Choosing small enough we get |X | (G).
