Bidimensionality: An Overview
Tom´aˇs Vejpustek
June 19, 2013
Outline
Bidimensionality works with:
r × r grids
bounded treewidth (tw)
H-minor-free graphs
Bidimensionality theory includes:
graph structural results
framework for FPT algorithms
polynomial-time approximation schemes (PTAS)
2 / 21
Bounded Treewidth
w-tree-decomposition is FPT
allows nice dynamic FPT algorithms
many problems are FPT on bounded tw
r × r grid = typical graph of tw(r)
(cops and robber game)
Courcelle’s (meta)theorem
Let ϕ be a MSOL formula and G be a graph with tw(G) ≤ w. Then
in time f (|ϕ|, w)O(|V (G)|) it can be decided whether G satisfies ϕ.
3 / 21
Graph Minors
1. deleting vertices
2. deleting edges
3. contracting edges
Forbidden minor characterization
Each graph class closed on minors has a finite set of
forbidden minors (⇐ Robertson–Seymour theorem).
non-constructive (some forbidden minors unknown)
H-minor problem O(n3
) for fixed H
(superexponential w.r.t |H|)
4 / 21
H-Minor-Free Graphs
trees (triangle)
planar graphs (K5 and K3,3)
graphs embeddable on a fixed topological surface
tw(G) ≤ 3
many are easier for FPT algorithms
5 / 21
Minor-Free Graphs Classification
6 / 21
Minor-Free Graphs Classification
Bounded Genus Graph
Embeddable on a surface
with bounded Euler genus
(i.e. bounded number of
handles and cross-caps).
6 / 21
Minor-Free Graphs Classification
Single-crossing Graph
Can be drawn on a plane
with at most two edges
crossing.
6 / 21
Minor-Free Graphs Classification
Apex Graph
Planar after removing
a vertex (apex vertex).
6 / 21
Large Grid Minors
every planar graph of tw ≥ 6k − 5 has a Gk×k minor
every graph of tw ≥ 202k5
has a Gk×k minor
7 / 21
Large Grid Minors
every planar graph of tw ≥ 6k − 5 has a Gk×k minor
every graph of tw ≥ 202k5
has a Gk×k minor
Theorem
For any fixed graph H, every H-minor-free graph of
tw = k has a GΩ(k)×Ω(k) minor.
7 / 21
Proof Outline
1. H-minor-free graphs can be decomposed into
a clicque sum of almost embeddable graphs (R.S.)
2. clicque sum does not increase tw → component
with greatest tw
3. almost embeddable reduced to embeddable
4. bounded genus has large grid
(prior results – extended from planar)
8 / 21
Clicque Sum
Let G1 and G2 contain a k-clique W . G1 ⊕ 1G2:
1. delete some or no edges from W
2. attach G1 \ W to corresponding vertices
3. attach G2 \ W similarly
9 / 21
Clicque Sum
Let G1 and G2 contain a k-clique W . G1 ⊕ 1G2:
1. delete some or no edges from W
2. attach G1 \ W to corresponding vertices
3. attach G2 \ W similarly
tw(G1 ⊕ G2) ≤ max{tw(G1), tw(G2)}
1. tw(G1) ≥ tw(W ), tw(G2) ≥ tw(W )
2. W is in one bag in tree decompositions of G1, G2
3. we can get tree decomposition of G1 ⊕ G2 by joining
them by a bag containing only W
9 / 21
Bidimensional Problems
Minor Bidimensionality
A parameter P is g(r)-minor-BiD if it:
1. is at least g(r) on Gr×r
2. does not increase when taking minors
10 / 21
Bidimensional Problems
Minor Bidimensionality
A parameter P is g(r)-minor-BiD if it:
1. is at least g(r) on Gr×r
2. does not increase when taking minors
Θ(r2
)-minor-BiD – size of: vertex cover, feedback
vertex set, . . .
not minor-BiD: dominating set, Hamiltonian path
(removing edges)
10 / 21
Contraction Bidimensionality
Parameter P is g(r)-contraction-BiD if it:
1. is at least g(r) on Gr×r -like graph
2. does not increase when contracting edges
11 / 21
Contraction Bidimensionality
Parameter P is g(r)-contraction-BiD if it:
1. is at least g(r) on Gr×r -like graph
2. does not increase when contracting edges
Grid-like Graphs
planar partially triangulated Gr×r
bounded-genus above + genus(G) additional edges
apex-minor-free Gr×r + additional edges so that each
vertex is incident to c noboundary vertex
(depending on forbidden minor)
11 / 21
Contraction Bidimensionality
Parameter P is g(r)-contraction-BiD if it:
1. is at least g(r) on Gr×r -like graph
2. does not increase when contracting edges
Grid-like Graphs
planar partially triangulated Gr×r
bounded-genus above + genus(G) additional edges
apex-minor-free Gr×r + additional edges so that each
vertex is incident to c noboundary vertex
(depending on forbidden minor)
Dominating set (Θ(r2
)), Hamiltonian path (Θ(r2
)), . . .
11 / 21
FPA Schema
Let P be g(r)-minor bidimensional and G be
H-minor-free for some H. Is P(G) ≥ k?
1. G has a Gtw(G)×tw(G), so P(G) ≥ g(tw(G))
2. if g(tw(G)) ≥ k, return YES
3. otherwise, tw(G) ≤ k =⇒ use dynamic
programming (or Courcelle’s theorem)
12 / 21
FPA Schema
Let P be g(r)-minor bidimensional and G be
H-minor-free for some H. Is P(G) ≥ k?
1. G has a Gtw(G)×tw(G), so P(G) ≥ g(tw(G))
2. if g(tw(G)) ≥ k, return YES
3. otherwise, tw(G) ≤ k =⇒ use dynamic
programming (or Courcelle’s theorem)
Can we get subexponential FPTA (e.g. O(2
√
k
))?
12 / 21
Parameter-Treewidth Bounds
Theorem
Let P be g(r)-BiD for the graph G. Then
tw(G) = O g−1
(P(G)) .
13 / 21
Parameter-Treewidth Bounds
Theorem
Let P be g(r)-BiD for the graph G. Then
tw(G) = O g−1
(P(G)) .
Proof (minor-BiD): G has a GΩ(r)×Ω(r) minor R.
P(R) ≤ g(r) ≥ g(Ω(tw(G))). Since P does not increase
when taking minors, P(G) ≥ P(R), i.e.
P(G) ≥ g(Ω(tw(G))) and tw(G) = O g−1
(P(G)) .
13 / 21
Parameter-Treewidth Bounds
Theorem
Let P be g(r)-BiD for the graph G. Then
tw(G) = O g−1
(P(G)) .
Proof (minor-BiD): G has a GΩ(r)×Ω(r) minor R.
P(R) ≤ g(r) ≥ g(Ω(tw(G))). Since P does not increase
when taking minors, P(G) ≥ P(R), i.e.
P(G) ≥ g(Ω(tw(G))) and tw(G) = O g−1
(P(G)) .
If g(r) = Θ(r2
) then tw(G) = O P(G) .
13 / 21
Subexponantial FPTAs
Theorem
Assume P is g(r)-BiD and can be computed in
h(w)nO(1)
. Then there is an algorithm that computes
P(G) for a graph class corresponding to P which has the
complexity of h(O(g−1
(k))) + 2O(g−
1(k))
nO(1)
.
14 / 21
Subexponantial FPTAs
Theorem
Assume P is g(r)-BiD and can be computed in
h(w)nO(1)
. Then there is an algorithm that computes
P(G) for a graph class corresponding to P which has the
complexity of h(O(g−1
(k))) + 2O(g−
1(k))
nO(1)
.
Notably when g(r) = Θ(r2
) and h(w) = 2o(w2
)
, this time
is subexponential =⇒ subexponential algorithms for
vertex cover, feedback vertex set, dominating set,. . .
14 / 21
Locally Bounded Tree-Width
∀v. tw(G[Nr (v)]) ≤ f (r)
Theorem
Every apex-minor-free graph of diameter D has treewidth
in O(D).
Diameter-bounded tw ≈ locally-bounded tw
(neighbourhood is a minor)
15 / 21
Separators
Theorem
Every H-minor-free graph G has tw in O |V (G)| .
16 / 21
Separators
Theorem
Every H-minor-free graph G has tw in O |V (G)| .
Proof: Number of vertices is r2
-bidimensional.
Consequence: Every vertex-weighted H-minor free
graph has a separator of size O |V (G)| , which
separates into two parts with weight at most 2
3 of G
=⇒ divide and conquer
16 / 21
Separation Property of Problems
1. can be solved for each connected component
independently
2. there is a polynomial algorithm, which given a cut
of the graph and optimal solutions for all connected
components, computes solution for the whole graph
which is not much greater
3. optimal solution of the whole graph is not much
different from optimal solution of connected
components from cut
(much ≈ size of the cut)
17 / 21
PTAS for BiD problems
Theorem
When a BiD problem with separation property can be
approximated with constant factor in polynomial time it
has a PTAS (all on H-minor-free graphs).
18 / 21
PTAS for BiD problems
Theorem
When a BiD problem with separation property can be
approximated with constant factor in polynomial time it
has a PTAS (all on H-minor-free graphs).
Recursively decompose graph into subgraphs, until
approximate solutions are precise enough.
When decomposing, approximate tree
decomposition and choose one bag as a cut (which
divides most evenly).
Finally join solutions using separation property.
18 / 21
Open Problems
find better bounds for grid minors in general graphs
(lower bound r2
log r, conjecture r3
)
generalize BiD (and resulting PTASs) for weighted
problems
. . .
19 / 21
Summary
Every H-minor-free graph of tw = w has GΩ(w)×Ω(w) as
a minor. This can be used:
prove that problem is FPT
find subexponential FPTAs
build PTASs
20 / 21
Bibliography
Erik D. Demaine and MohammadTaghi Hajiaghayi.
The Bidimensionality Theory and Its Algorithmic
Applications.
The Computer Journal, 51(3):292–302, 2008.
21 / 21