Fixed-Parameter Algorithms, IA166
Sebastian Ordyniak
Faculty of Informatics
Masaryk University Brno
Spring Semester 2013
Color Coding
Introduction
Outline
1 Color Coding
Introduction
The k-s-t-PATH Problem
Generalization: Finding tree subgraphs
Generalization: Bounded Treewidth
Summary
Color Coding
Introduction
Color Coding
Color Coding
Introduction
Motivation
works best when we need to ensure that a small number of
“things” are disjoint.
We demonstrate it on the problem of finding s-t path of
length exactly k.
Randomized algorithm, but can be derandomized using
standard techniques.
Very robust technique, we can use it as an “opening step”
when investigating a new problem.
Color Coding
The k-s-t-PATH Problem
Outline
1 Color Coding
Introduction
The k-s-t-PATH Problem
Generalization: Finding tree subgraphs
Generalization: Bounded Treewidth
Summary
Color Coding
The k-s-t-PATH Problem
Introduction
k-s-t-PATH Parameter: k
Input: Graph G, 2 vertices s and t, and a natural number k.
Question: Find an s-t-path, i.e. a path from s to t in G, with
exactly k internal vertices.
Remark
The problem is NP-hard because it contains the
s-t-HAMILTONIAN PATH problem.
Color Coding
The k-s-t-PATH Problem
Basic Idea
Assign k colors to the
vertices in V(G) \ {s, t}
uniformly and
independently at random.
Check if there is a colorful
s-t-path, i.e., a path where
each color appears exactly
once on the internal
vertices. If so output YES,
if not output NO.
s t
Color Coding
The k-s-t-PATH Problem
Basic Idea
Assign k colors to the
vertices in V(G) \ {s, t}
uniformly and
independently at random.
Check if there is a colorful
s-t-path, i.e., a path where
each color appears exactly
once on the internal
vertices. If so output YES,
if not output NO.
s t
Color Coding
The k-s-t-PATH Problem
Basic Idea
Assign k colors to the
vertices in V(G) \ {s, t}
uniformly and
independently at random.
Check if there is a colorful
s-t-path, i.e., a path where
each color appears exactly
once on the internal
vertices. If so output YES,
if not output NO.
s t
Color Coding
The k-s-t-PATH Problem
Basic Idea
This gives us a randomized algrithm for k-s-t-PATH such that:
Given a NO instance of k-s-t-PATH, the algorithm always
outputs NO.
Given a YES instance of k-s-t-PATH, the algorithm outputs
YES with probability:
k!
kk ≈
√
2πk(1
e )k > e−k
Here we use Stirling’s formula: k! ≈
√
2πk(k
e )k .
Color Coding
The k-s-t-PATH Problem
Basic Idea
Observation
Let A be a randomized algorithm with success rate at least p.
Then repeating A at least 1/p-times leads to an error
probability of at most (1 − p)1/p ≤ (e−p)1/p = e−1 = 1/e ≈ 0.38
(Using the fact that 1 − x ≤ e−x ).
Hence, if p > e−k then the error probability of A is at most
1/e after ek repetitions.
Repeating the algorithm cek times (for some constant c)
decreases the error probability of the algorithm to an
arbitrary small constant, e.g., by trying 100ek random
colorings, the error probability becomes e−100.
Color Coding
The k-s-t-PATH Problem
A Monte Carlo FPT-algorithm for k-s-t-PATH
Provided that we can find a colorful s-t-Path in time f(k)nc the
above randomized algorithm decides k-s-t-PATH with arbitrary
low error probability in time O∗(ek f(k)nc). Such a randomized
algorithm is also called a Monte Carlo algorithm.
There are 2 important questions remaining:
Question (1)
How to find a colorful s-t-path in polynomial time?
Question (2)
Is it possible to derandomize the above algorithm?
Color Coding
The k-s-t-PATH Problem
Finding a Colorful s-t-Path
k-COLORFUL PATH Parameter: k
Input: A graph G, 2 vertices s and t of G, and a vertex-coloring
c of G with k colors.
Question: Does G contain a colorful s-t-Path?
We will now show two methods to solve the above problem:
Method 1: Trying all permutations;
Method 2: Dynamic Programming.
Color Coding
The k-s-t-PATH Problem
Method 1: Trying all permutations
The colors encountered on a colorful s-t-path form a
permutation π of {1, . . . , k}.
s
π(1) π(2)
. . .
π(k − 1) π(k)
t
We try all k! permutations. For a fixed permutation it is easy to
check if there is a path with this order of colors.
Color Coding
The k-s-t-PATH Problem
Method 1: Trying all permutations
Let π be such a permutation. The following algorithm decides
whether G has a colorful s-t-path representing π:
Remove edges connecting vertices colored by
non-neighboring colors with respect to π.
Direct the remaining edges according to π.
Check whether there is a directed s-t-path.
Running time is O(|E(G)|).
Color Coding
The k-s-t-PATH Problem
Method 1: Trying all permutations
Theorem
k-COLORFUL PATH can be decided in time O(k!|E(G)|), for an
instance (G, c, k).
Corollary
k-s-t-PATH can be decided by a randomized algorithm with
arbitrary high constant success probability in time
O(ek k!|E(G)|).
Color Coding
The k-s-t-PATH Problem
Method 2: Dynamic Programming
We introduce 2k |V(G)| boolean variables, i.e., for every
v ∈ V(G) and every C ⊆ {1, . . . , k} we introduce a variable
x(v, C) that is TRUE iff G contains an s-v-path that contains
only colors in C and each color in C appears exactly once on
this path.
Color Coding
The k-s-t-PATH Problem
Method 2: Dynamic Programming
Clearly, x(s, ∅) = TRUE. Furthermore, we can use the
following recurrence for a vertex v with color r:
x(v, C) = {u,v}∈E(G) x(u, C \ {r})
Using the above recurrence we can determine the values
of every x(v, C) from the values of every x(v, C ) with
|C | = |C| − 1. This allows us to determine the values of all
these variables in time O(2k |E(G)|).
Clearly, G has a colorful s-t-path iff
x(v, {1, . . . , k}) = TRUE for some neighbor v of t.
Color Coding
The k-s-t-PATH Problem
Method 2: Dynamic Programming
Theorem
k-COLORFUL PATH can be decided in time O(2k |E(G)|), for an
instance (G, c, k).
Corollary
k-s-t-PATH can be decided by a randomized algorithm with
arbitrary high constant success probability in time
O((2e)k |E(G)|).
Color Coding
The k-s-t-PATH Problem
Derandomization
Using Method 2, we obtain a O((2e)k |E(G)|) time Monte Carlo
algorithm. How can we make it deterministic?
Definition
A family H of functions from {1, . . . , n} to {1, . . . , k} is a
k-perfect family of hash functions if for every S ⊆ {1, . . . , n}
with |S| = k, there is a h ∈ H such that h(x) = h(y) for every
x, y ∈ S with x = y.
Instead of trying O(ek ) random colorings, we go through a
k-perfect family H of hash functions. If there is a solution then
the internal vertices are colorful for at least 1 such function and
our algorithm returns YES.
Color Coding
The k-s-t-PATH Problem
Derandomization
Theorem
There is a k-perfect family of hash functions from {1, . . . , n} to
{1, . . . , k} having size at most 2O(k) log n and such a family can
be constructed in polynomial time with respect to the size of the
family.
Corollary
There is a deterministic O(2O(k)nO(1)) time algorithm for the
k-s-t-PATH problem.
Color Coding
The k-s-t-PATH Problem
Some Simple Generalizations
k-CYCLE Parameter: k
Input: Graph G and a natural number k.
Question: Does G contain a cycle of length exactly k.
By computing k-s-t-PATH for every pair of distinct and adjacent
vertices s and t of G we obtain:
Corollary
There is a deterministic O(2O(k)nO(1)) time algorithm for the
k-CYCLE problem.
Color Coding
The k-s-t-PATH Problem
Some Simple Generalizations
k-LONGEST PATH Parameter: k
Input: Graph G and a natural number k.
Question: Does G contain a path of length at least k.
By computing k-s-t-PATH for every pair of distinct vertices s
and t of G and observing that G contains a path of lenght at
least k iff G contains a path of length exactly k we obtain:
Corollary
There is a deterministic O(2O(k)nO(1)) time algorithm for the
k-LONGEST PATH problem.
Color Coding
Generalization: Finding tree subgraphs
Outline
1 Color Coding
Introduction
The k-s-t-PATH Problem
Generalization: Finding tree subgraphs
Generalization: Bounded Treewidth
Summary
Color Coding
Generalization: Finding tree subgraphs
Introduction
k-TREE SUBGRAPH Parameter: |V(T)|
Input: A tree T and a graph G.
Question: Does G contain T as a subgraph?
As before, we start by solving its colorful version:
k-COLORFUL-TREE SUBGRAPH Parameter: |V(T)|
Input: A tree T and a graph G with a |V(T)|-vertex coloring
c : V(G) → |V(T)|.
Question: Does G contain a colorful copy of T as a subgraph?
Color Coding
Generalization: Finding tree subgraphs
A Dynamic Programming Approach
W.l.o.g. we can assume that the tree T is rooted at some
arbitrary vertex r ∈ V(T). We denote by T(t) the subtree of T
rooted in t.
We solve k-COLORFUL-TREE SUBGRAPH via a dynamic
programming algorithm that computes a set of records in a
bottom-up manner along the tree T, i.e, starting from the leaves
of T and progressing to the root of T. For every tree node t of
T the set of records (denoted R(t)) contains all pairs (v, C)
such that v ∈ V(G), C ⊆ {1, . . . , k} and G contains a colorful
copy (with respect to C) of T(t) where v takes the role of t.
Color Coding
Generalization: Finding tree subgraphs
A Dynamic Programming Approach
Recursion Start:
If l ∈ V(T) is a leave of T, then
R(l) := { (v, {c(v)}) : v ∈ V(G) }. Hence, R(l) can be
computed in time O(|V(G)|) for every leave node l of T.
Color Coding
Generalization: Finding tree subgraphs
A Dynamic Programming Approach
Recursion Step:
If t is an inner node of T with children t1, . . . , tl, then
R(t) := { (v, C) : v ∈ V(G) and
there is an ordered partition (C1, . . . , Cl) of C \ c(v)
and neighbors v1, . . . , vl of v in G such that:
(vi, Ci) ∈ R(ti)
}
Question
How can we compute the above efficiently?
Color Coding
Generalization: Finding tree subgraphs
A Dynamic Programming Approach
Lemma
If t is an inner node of T with children t1, . . . , tl and let v ∈ V(G)
with neighbors n1, . . . , nr in G. Then (v, C) ∈ R(t) iff c(v) ∈ C
and there is an ordered partition (C1, . . . , Cl) of C \ {c(v)} such
that the bipartite graph B(t) with vertices
{ t1, . . . , tl } ∪ { n1, . . . , nr }
and edges
{ {ti, nj} : (nj, Ci) ∈ R(ti) }
has a matching that saturates {t1, . . . , tl}.
Color Coding
Generalization: Finding tree subgraphs
A Dynamic Programming Approach
Because of the above Lemma we can decide whether a
potential record (v, C) is in the set R(t) as follows:
(1) Guess an ordered partition (C1, . . . , Cl) of C \ {c(v)}.
(2) Construct the bipartite graph B(t) as in the above lemma
(4) Check whether B(t) has a perfect matching. If so output
YES, otherwise output NO.
Color Coding
Generalization: Finding tree subgraphs
A Dynamic Programming Approach
Because of the above Lemma we can decide whether a
potential record (v, C) is in the set R(t) as follows:
(1) Guess an ordered partition (C1, . . . , Cl) of C \ {c(v)}. This
takes time O(2ll!) = O(2|V(T)|(|V(T)|)!).
(2) Construct the bipartite graph B(t) as in the above lemma
This takes time O(lr) = O(|V(T)||V(G)|).
(4) Check whether B(t) has a perfect matching. If so output
YES, otherwise output NO. This takes time
O((lr) = O(|V(T)||V(G)|).
Color Coding
Generalization: Finding tree subgraphs
A Dynamic Programming Approach
Because of the above Lemma we can decide whether a
potential record (v, C) is in the set R(t) as follows:
(1) Guess an ordered partition (C1, . . . , Cl) of C \ {c(v)}. This
takes time O(2ll!) = O(2|V(T)|(|V(T)|)!).
(2) Construct the bipartite graph B(t) as in the above lemma
This takes time O(lr) = O(|V(T)||V(G)|).
(4) Check whether B(t) has a perfect matching. If so output
YES, otherwise output NO. This takes time
O((lr) = O(|V(T)||V(G)|).
Hence, we can decide whether (v, C) ∈ R(t) in time O(2ll!lr) or
equivalently in time O(2|V(T)|(|V(T)|!)|V(T)||V(G)|).
Color Coding
Generalization: Finding tree subgraphs
A Dynamic Programming Approach
Since there are at most O(2|V(T)||V(G)|) potential records for
every tree node and at most |V(T)| tree nodes we obtain the
following:
Theorem
k-COLORFUL-TREE SUBGRAPH can be decided in time
O(4|V(T)|(|V(T)|!)(|V(T)|)2(|V(G)|)2).
By running the above algorithm for every hash function of a
perfect family of hash functions, we obtain:
Corollary
k-TREE SUBGRAPH can be decided in time
O(2O(|V(T)|)(|V(T)|!)(|V(T)|)2(|V(G)|)2).
Color Coding
Generalization: Finding tree subgraphs
Even More General
Let C be an arbitrary class of graphs.
k-C-SUBGRAPH Parameter: |V(H)|
Input: A graph H ∈ C and a graph G.
Question: Does G contain H as a subgraph?
Using the above algorithms we have seen that
k-C-SUBGRAPH is FPT if C is the class of all trees
respectively cycles.
Because k-C-SUBGRAPH is equivalent to the k-CLIQUE
problem if C is the class of all cliques we can note hope for
an FPT algorithm in general (unless FPT=W[1]).
Color Coding
Generalization: Finding tree subgraphs
Even More General
Question
Is there some class C in between trees (cycles) and cliques that
allows for fixed-parameter tractability of k-C-SUBGRAPH?
Color Coding
Generalization: Bounded Treewidth
Outline
1 Color Coding
Introduction
The k-s-t-PATH Problem
Generalization: Finding tree subgraphs
Generalization: Bounded Treewidth
Summary
Color Coding
Generalization: Bounded Treewidth
Introduction
Theorem
Let C be a class of graphs of treewidth at most w. Then
k-C-SUBGRAPH can be solved in time
O(2O(|V(H)|)(|V(G)|)w+O(1)) (if a tree decomposition of the
graph H of width w is given as the input).
Corollary
Let C be a class of graphs of bounded treewidth. Then
k-C-SUBGRAPH is fixed-parameter tractable.
Color Coding
Generalization: Bounded Treewidth
Solving the Colorful Problem
We first need to solve the following problem:
k-C-COLORFUL SUBGRAPH Parameter: |V(H)|
Input: A graph H ∈ C and a graph G with a |V(H)|-vertex
coloring c : V(G) → {1, . . . , |V(H)|}.
Question: Does G contain a colorful subgraph isomorphic to
H?
Color Coding
Generalization: Bounded Treewidth
Solving the Colorful Problem
Let (T, X) be a nice tree decomposition of H and let t ∈ V(T).
As always we compute a set of records R(t) for every t ∈ V(T)
in a bottom up manner. This time a record is a pair (φ, C) such
that φ is a 1-to-1 mapping between vertices in X(t) and exaclt
|X(t)| vertices in V(G) and C ⊆ {1, . . . , |V(H)|} is a set of
colors.
The semantics of a record is as follows:
(φ, C) ∈ R(t) iff G contains a colorful copy of X(t) using every
color in C exactly once such that the vertex φ(v) is mapped to
v for every v ∈ X(t).
Clearly, the solution for the k-C-COLORFUL SUBGRAPH problem
can be easily obtained from R(r) by checking wether
(∅, {1, . . . , |V(H)|}) ∈ R(r).
Color Coding
Generalization: Bounded Treewidth
Solving the Colorful Problem
Let (T, X) be a nice tree decomposition of H and let t ∈ V(T).
t is a leaf node with X(t) = {v}
R(t) := { ((v → v ), {c(v )}) : v ∈ V(G) }.
Color Coding
Generalization: Bounded Treewidth
Solving the Colorful Problem
Let (T, X) be a nice tree decomposition of H and let t ∈ V(T).
t is a leaf node with X(t) = {v}
R(t) := { ((v → v ), {c(v )}) : v ∈ V(G) }.
Can be computed in time |V(G)|.
Color Coding
Generalization: Bounded Treewidth
Solving the Colorful Problem
t is an introduce node with child t and {v} = X(t) \ X(t )
R(t) := { (φ + (v → v ), C ∪ {c(v )}) :
(φ, C) ∈ R(t ) and v ∈ V(G) and
∀w∈X(t ){v, w} ∈ E(H) → {v , φ(w)} ∈ E(G) }
Color Coding
Generalization: Bounded Treewidth
Solving the Colorful Problem
t is an introduce node with child t and {v} = X(t) \ X(t )
R(t) := { (φ + (v → v ), C ∪ {c(v )}) :
(φ, C) ∈ R(t ) and v ∈ V(G) and
∀w∈X(t ){v, w} ∈ E(H) → {v , φ(w)} ∈ E(G) }
Can be computed in time O(|R(t )||X(t)||V(G)|).
Color Coding
Generalization: Bounded Treewidth
Solving the Colorful Problem
t is a forget node with child t and {v} = X(t ) \ X(t)
R(t) := { (φ[X(t)], C) : (φ, C) ∈ R(t ) }
Color Coding
Generalization: Bounded Treewidth
Solving the Colorful Problem
t is a forget node with child t and {v} = X(t ) \ X(t)
R(t) := { (φ[X(t)], C) : (φ, C) ∈ R(t ) }
Can be computed in time O(|R(t )|).
Color Coding
Generalization: Bounded Treewidth
Solving the Colorful Problem
t is a join node with children t1 and t2
R(t) := { (φ1, C1 ∪ C2) :
(φ1, C1) ∈ R(t1) and (φ2, C2) ∈ R(t2) and
φ1 == φ2 and C1 ∩ C2 = { c(φ1(v)) : v ∈ X(t) }
Color Coding
Generalization: Bounded Treewidth
Solving the Colorful Problem
t is a join node with children t1 and t2
R(t) := { (φ1, C1 ∪ C2) :
(φ1, C1) ∈ R(t1) and (φ2, C2) ∈ R(t2) and
φ1 == φ2 and C1 ∩ C2 = { c(φ1(v)) : v ∈ X(t) }
Can be computed in time O(max{|R(t1)|, |R(t2)|}).
Color Coding
Generalization: Bounded Treewidth
Solving the Colorful Problem
Because there are at most O(|V(H)|) tree nodes and for each
tree node we need time at most O(|R(t)||X(t)||V(G)|) the total
running time of the algorithm is O(|R(t)||X(t)||V(H)||V(G)|) or
equivalently O(2|V(H)|(|V(G)|w+1(w + 1)|V(H)||V(G)|).
Theorem
Let C be a class of graphs of treewidth at most w. Then
k-C-COLORFUL SUBGRAPH can be decided in time
O(2|V(H)|(|V(G)|)w+2(w + 1)|V(H)|) (if a tree decomposition of
the graph H of width w is given as the input).
Color Coding
Generalization: Bounded Treewidth
Solving the whole problem
Theorem
Let C be a class of graphs of treewidth at most w. Then
k-C-COLORFUL SUBGRAPH can be decided in time
O(2|V(H)|(|V(G)|)w+2(w + 1)|V(H)|) (if a tree decomposition of
the graph H of width w is given as the input).
Using perfect hash functions we obtain:
Corollary
Let C be a class of graphs of treewidth at most w. Then
k-C-SUBGRAPH can be decided in time
O(2O(|V(H)|)(|V(G)|)w+O(1)) (if a tree decomposition of the
graph H of width w is given as the input).
Color Coding
Summary
Outline
1 Color Coding
Introduction
The k-s-t-PATH Problem
Generalization: Finding tree subgraphs
Generalization: Bounded Treewidth
Summary
Color Coding
Summary
Color Coding – Summary
Color Coding is a useful technique for solving various
subgraph problems; fixing a coloring makes dynamic
programming possible.
This method can be generalized to finding embendings
between general relations structures.
Color Coding makes use of the fact that we can guess
properties of a solution.
Giving a randomized (Monto Carlo) algorithm (as a first
step) is often easier than giving an algorithm that is always
correct.