Parameterized Algorithms
Parameterized Algorithms
Md. Saidur Rahman
Department of Computer Science and Engineering,
Bangladesh University of Engineering and Technology, Dhaka
Parameterized Algorithms
Parameterized Algorithms
Basic Concepts
Parameterized complexity measures complexity not only in
terms of input length but also in terms of a parameter which is a
numerical value not necessarily depend on input length.
Roughly speaking, parameterized complexity seeks the
possibility of obtaining algorithms whose running time can be
bounded by a polynomial function of the input length, and
usually an exponential function of the parameter.
Parameterized Algorithms
Parameterized Algorithms
Vertex Cover Problem
A vertex cover of a graph G = (V , E) is a set Q ⊆ V that
contains at least one endpoint of every edge. A vertex cover of
a graph G is a minimum vertex cover if it contains the minimum
number of vertices among all vertex covers of G. The vertex
cover problem asks to find a minimum vertex cover of a graph.
The decision version of the problem is described as follows:
Given a graph G = (V , E) of n vertices and a number k , does
G contain a vertex cover of size at most k ?
Parameterized Algorithms
Parameterized Algorithms
Brute Force Algorithm:
Assume that k is a fixed constant.
For each subset S of V of size k we check whether S is a
vertex cover of G or not.
We can check whether S is a vertex cover by deleting the
vertices in S from G and checking whether the resulting graph
has an edge or [Link] process takes at most O(kn) time.
The number of subsets of V of size exactly k is kn . Hence this
bruteforce approach takes O(nk kn ) = O(knk +1 ) time.
Parameterized Algorithms
Vertex Cover Problem
Parameterized Vertex Cover: Idea
Obtain an algorithm whose time complexity is O(2k kn).
Parameterized Algorithms
bruteforce
1x1030 PVC
number of comptational steps
1x1025
1x1020
1x1015
1x1010
100000
1
6 7 8 9 10
vertex cover size k
Parameterized Algorithms
Vertex Cover Problem
Observation
Let e = (u, v ) an edge of G and let S be a vertex cover of
G of size exactly k . Then at least one of u and v is in S.
If u is in S, then G − u has a vertex cover of size at most
k − 1. Similarly if v is in S, then G − v has a vertex cover
of size at most k − 1.
We thus devise a recursive algorithm to decide whether G
has a vertex cover of size k .
Parameterized Algorithms
u k=3?
w
x v
−u −v
y
u
k=2?
w w
x v x
k=2?
−x
−x y −y −u y
k=1? u
w w w
v x v
x k=1?
k=1? k=1? w
−v y −x −v y
−w −x −y
−w
−u y
w
v w
w u
k=0? k=0? w
v k=0? x x
w w
y y No No k=0? k=0? k=0? k=0?
No y k=0?
Yes No Yes
y No
Yes y
Parameterized Algorithms
How many edges can be covered by a vertex cover of
size k ?
Observation
Let ∆ be the maximum degree of G. Then a vertex cover of
size k can cover at most k ∆ edges. Since ∆ can be at most
n − 1 in G of n vertices, a vertex cover of size k can cover at
most (n − 1)k edges. Thus if a graph G has more than (n − 1)k
edges, then G has no vertex cover of size k .
Parameterized Algorithms
Algorithm 1: Algorithm PVC(G, k )
Input: A graph G of n vertices and an integer k .
Output: A vertex-cover S of size at most k if it exists
1 if there is no edge in the graph then
2 then S is empty
3 return S = ∅
4 if G has more than k (n − 1) edges then
5 G has no vertex cover of size at most k
6 return “no”
7 let (u, v ) be an edge of G.
8 if PVC(G − u, k − 1) = “no” and PVC(G − v , k − 1) = “no” then
9 return “no”
10 else
11 if PVC(G − u, k − 1) ̸= “no” or PVC(G − v , k − 1) ̸= “no” then
12 Say PVC(G − u, k − 1) ̸= “no” and it returns set S
13 return S ∪ {u}
Parameterized Algorithms
Time Complexity
Let T (n, k ) be the time required to decide whether a graph of n
vertices has a vertex cover of size k . If k = 0 then the graph is
a null graph, i.e. the graph has no edges. So one can
determine in linear time whether G has a vertex cover of size 0.
Thus T (n, 0) ≤ cn for some constant c. For n > 0, the following
recurrence relation holds:
T (n, k ) ≤ 2T (n, k − 1) + ckn
Parameterized Algorithms
Time Complexity
T (n, k ) ≤ 2T (n, k − 1) + ckn
< 2{2T (n, k − 2) + ckn)} + ckn
= 4T (n, k − 2) + 2ckn + ckn
< 8T (n, k − 3) + 4ckn + 2ckn + ckn
= 23 (n, k − 3) + 22 ckn + 2ckn + ckn
..
.
< 2k cn + 2k −1 ckn + 2k −2 ckn + · · · + 22 ckn + 2ckn + ckn
< 2k cn + 2k ckn
= O(2k kn)
Parameterized Algorithms
Parameterized Complexity
The vertex cover problem has two parameters n and k . The
bruteforce algorithm takes O(knk +1 ) time and the PVC
algorithm takes O(2k kn) time to check whether a G of n
vertices has a vertex cover of size k . Although the time
complexity PVC has an exponential term, it is faster than the
bruteforce algorithm. Here k taken as a parameter where the
time complexity is allowed to grow on this paramerer
exponentially, but the algorithm is useful for small values of the
parameter. To find such a parameter, not the input length, is the
basic principles of parameterized algorithm.
Parameterized Algorithms
bruteforce
1x1030 PVC
number of comptational steps
1x1025
1x1020
1x1015
1x1010
100000
1
6 7 8 9 10
vertex cover size k
Parameterized Algorithms
Fixed-Parameter Tractable (FPT) Algorithm
The PVC algorithm solves the vertex cover problem in time that
is exponential only in the size of the fixed parameter k while it is
polynomial in the size of the input. Such an algorithm is called a
fixed-parameter tractable (fpt-)algorithm , because the problem
can be solved efficiently for small values of the fixed parameter.
Thus vertex cover problem is fixed parameter tractable.