Week 7 (FPT+Kernels, Exponential Time Hypothesis) Flashcards
(18 cards)
What time complexity does a parameterised problem need to be considered FPT?
f(k) * n^{ O(1) }.
What does FPT stand for?
Fixed-Parameter Tractable.
Define the k-VC problem.
k-VC is parameterised Vertex Cover problem.
Given an undirected graph G = (V,E) .
Solve for if there exist subset X of V of size <= k.
Such that all edge in E has a point in X.
Assume P != NP What can you deduct about the time complexity of algorithms for k-VC
You cannot expect it to run in polynomial time in both k and n.
Describe the bounded-search tree algorithm on k-VC and argue its correctness
With G as the root of the tree.
The tree has a branching factor of 2.
Each layer, pick an edge and the next nodes remove one of the vertex in the edge.
The tree has a height of k
If any of the leaf nodes have no edges left then there’s a solution of size <= k
And vice versa.
If there is a vertex cover of size <= k, then at least one of the graphs at the leaf nodes has no edges. If there is no vertex cover of size <=k. then none of the leaf nodes are empty graphs
Show the running time of bounded-search tree on k-VC
The binary search tree has the maximum height of k.
So, It has at most 2^{ k+1 } - 1 nodes.
Each node takes n^{ O(1) } time.
So, final time complexity is [ 2^ { k+ 1} - 1 ] * [ n ^ { O(1) } ].
Does Independent Set have an FPT?
No, there’s no function for k-IS that runs in f(k) * n^ { O(1) }.
What is 2-Hitting-Set?
Given a set U and S where S contains every subset of U that is of size 2.
Solve for set X where it “hits” every subset (contains at least a element for every subset in S).
What is k-2-Hitting-Set?
Given a set U and S where S contains every subset of U that is of size 2. Does there exist Y⊆U of size <= k such that each subset of S contains at least one element of y.
Which problem is 2-Hitting-Set equivalent to?
Vertex Cover.
How to convert VC into 2-HS and vice versa?
VC to 2-HS:
Given G = (V, E), Let U=V and S=set of each edge.
2-HS to VC:
Given U&S, Let G = (U, edges formed by S)
What is a kernel?
An algorithm ALG which given an instance (I, k) of a parameterised problem produces (I’, k’) of the same problem that satisfies:
- Running time of ALG is poly(|I|, k).
- (I’, k’) and (I, k) are equivalent instances.
- There exist g and h such that |I’| <= g(k) and k’ <= h(k)
What are equivalent instances?
Both instances represent the same answer to the decision problem.
Considered interchangeable.
Show a kernel of k-VC.
Kernel for Vertex Cover:
X = Empty, G’ = G and k’ = k.
While k’ != 0 and the graph G has edges.
Find a vertex v of degree >= k’ + 1 and add it to X.
G’ = G’ - v and k’ = k’ - 1.
If k’ = 0 and the graph G’ still has edges left to cover, then return NO.
If k’ != 0 and the graph G’ has no edges left to cover, then return YES.
Otherwise, return G’ and k’
This is a kernel for k-Vertex Cover:
We have taken only poly(n, k) time so far
We stopped the algorithm so max degree of G’ is <= k’
If number of edges in G is > (k’)^2 , then return NO.
Otherwise, we have an equivalent instance with <= (k’)^2 edges.
How do we go from a Kernel to a FPT?
Suppose there is a poly(n,k) algorithm which constructs an equivalence instance with graph size n’<=g(k) and parameter k’<=h(k).
- Let f(k) be a brute force algorithm to check Y/N
- Total running time = n^O(1).k^O(1) + f(k) <= n^O(1).k^O(1). f(k)
Combine k^O(1) and f(k) to some other function f(k)
How are the Independent set and Vertex cover problems equivalent?
We can show that for any f(n) time algorithm for one problem works on another:
- Independent Set ≤P Vertex Cover
If s is an independent set, V\S is a vertex cover
How do you equate k-3-hitting set and Vertex cover?
Use 3 branches to get a running time of 3^K.|U|^O(1)
How do we go from a FTP to a Kernel?
Suppose there is an algorithm ALG that runs in f(k).n^O(1) time = f(k).n^c where c is a constant
- Run ALG for n^(c+1) time
- If ALG finishes, output Y/N as per what ALG computed
- If ALG doesn’t finish, f(k).n^c > n^(c+1) => f(k) > n
