Exact exponential algorithms and parameterized complexity

We usually want algorithms that:

• in polynomial time;
• for all instances;
• find an exact solution;

We can settle for 2 out of 3:

• relax 1: exponential algorithm
• relax 2: parameterized
• relax 3: approximate solutions

1. Exact exponential algorithms

• the length of a certificate at most: ∣ y ∣ ≤ m ( x ) |y|\le m(x) ∣y∣≤m(x); m ( x ) ∈ O ( p o l y ∣ x ∣ ) m(x)\in O(poly|x|) m(x)∈O(poly∣x∣)
• every problem in NP has a simple brute-force algorithm:
  • Given a instance x x x, try all potential certificates y y y with ∣ y ∣ ≤ m ( x ) |y|\le m(x) ∣y∣≤m(x) and check if R ( x , y ) = 1 R(x,y)=1 R(x,y)=1 for any of them.
  • since y ≤ m ( x ) y\le m(x) y≤m(x), there are at most O ( 2 m ( x ) ) O(2^{m(x)}) O(2m(x)) potential certificates, and it takes O ( p o l y ∣ x ∣ ) O(poly|x|) O(poly∣x∣) time to check each certificate, so the brute force algorithm for a NP problem can run in O ( 2 m ( x ) p o l y ∣ x ∣ ) O(2^{m(x)}poly|x|) O(2m(x)poly∣x∣).

2. Notation: O ∗ ( ⋅ ) O^*(·) O∗(⋅):

For any a > 1 a>1 a>1, ε > 0 \varepsilon>0 ε>0, and any c ∈ R c\in R c∈R , we have the running time for the simple brute-force algorithm O ∗ ( 2 m ( x ) ) O^*(2^{m(x)}) O∗(2m(x)).

Since: O ( n c ⋅ a n ) ⊂ O ( ( a + ε ) n ) O(n^c·a^n)\sub O((a+\varepsilon)^n) O(nc⋅an)⊂O((a+ε)n), where n c n^c nc denotes polynomial and a n a^n an denotes exponential.

3. Size of a problem

• certificate size: m ( x ) m(x) m(x)

4. TSP via Dynamic Programming

Give cities c 1 . . . c n c_1...c_n c1​...cn​, find a minimum length to go over all cities exact once.

Equivalently, find permutation π \pi π minimizing:

d ( c π ( n ) , c π ( 1 ) ) + ∑ i = 1 n − 1 d ( c π ( i ) , c π ( i + 1 ) ) d(c_{\pi(n)},c_{\pi(1)})+\sum_{i=1}^{n-1}d(c_{\pi(i)},c_{\pi(i+1)}) d(cπ(n)​,cπ(1)​)+∑i=1n−1​d(cπ(i)​,cπ(i+1)​)

idea: transform TSP into subproblems.

• line 3: let all vertices except the first one to be the end point;
• line 7: in each iteration of line 4, we pick j j j vertices, and we need to find the minimum path in these j j j vertices;
• also, we have to let each vertex to be the end point, except the first one, and calculate d ( c k , c i ) d(c_k,c_i) d(ck​,ci​) where c k c_k ck​ is the end point and c i c_i ci​ is the start point.
• Now we can understand the proof.
• line 3 and line 8 only compute n − 1 n-1 n−1 paths.

Dynamic Programming in general

• Divide problem into subproblems;
• solve all smaller subproblems in order of increasing size;
• cache results, and each subproblem is only solved once.
• In TSP example, the original problem doesn’t have the optimal substructure property, but our algorithm OPT does have the property. Once we know that for all c i c_i ci​ we can solve the problem.

5. Maximum independent set

Find out the maximum set of vertices in G ( V , E ) G(V,E) G(V,E), each of them do not connected with each other.

Naïve algorithm: O ( 2 n ) O(2^n) O(2n), n = ∣ V ∣ n=|V| n=∣V∣. Each of the vertex can be in/not in the independent set.

5.1 Algorithm(branching)

• choose a vertex with minimum degree;
• N ( v ) N(v) N(v): the set of vertex v v v and its neighbors;
• Detail for figures: -
  • Choose vertex a a a , N ( a ) = { a , b } N(a)=\{a,b\} N(a)={a,b};
  • delete the vertices connected with vertex a a a;
  • choose another vertex with minimum degree, repeat the first step;
  • until there are no vertices left or there are only one independent vertex left;
  • do the work on b b b;
  • while there are branches, just branch.

5.2 Number of subproblems

• First bound: choose a vertex, and add up the subproblems when each vertex in N ( v ) N(v) N(v) is deleted from the graph. d ( w ) + 1 d(w)+1 d(w)+1: the number of neighbors and the vertex itself.

• Second bound: as d ( v ) d(v) d(v) is what we choose at the beginning, then d ( v ) ≤ d ( w ) d(v)\le d(w) d(v)≤d(w), and the number of vertices in d ( v ) d(v) d(v) is equal to the size of N ( v ) N(v) N(v), then we have the upper bound.

6. Bar fight prevention

• Suppose in a graph, if there are edges between different vertices, there are conflicts. So we can think it as finding a maximum independent after we reject the at least k k k people.

6.1 How to boost our algorithm?

• find people who have no conflicts;
• find people who fight with k + 1 k+1 k+1 people;

Note: ∣ E ∣ = 2 ∣ V ∣ |E|=2|V| ∣E∣=2∣V∣, which is always hold.

Update: we have ∣ V ∣ ≤ 2 k 2 |V|\le 2k^2 ∣V∣≤2k2, people have conflicts at least one and at most k k k.

• find people who have only one fight, and reject his neighbors;

Update: we have ∣ V ∣ ≤ k 2 |V|\le k^2 ∣V∣≤k2, people have conflicts at least two and at most k k k.

6.2 Kernelization

General idea: remove the easy part, what’s left is the core part. If we use some parameter k k k, for example, for bar fight problem,then the size of the problem would depend only on k k k.

6.3 via Bounded Search Tree

Idea: each time randomly choose an edge, and try to reject each of them. Recursively do it, and the recursive depth is k k k, since we reject k k k vertices.

The number of subproblems: 2 k 2^k 2k. The depth is k k k, and in each depth, there are two vertices we can reject.

Suppose we have rejected the vertices of degree d ( v ) ≥ k + 1 d(v)\ge k+1 d(v)≥k+1. There are at most 1 2 n k \frac{1}{2}nk 21​nk edges. ( d ( v ) ≤ k d(v)\le k d(v)≤k and there are n vertices, each two vertices have one edge)

The total running time O ( m + n k ⋅ 2 k ) O(m+nk·2^k) O(m+nk⋅2k).

7. FTP vs XP

• A parameterized problem is Fixed Parameter Tractable(FPT) if it is has an algorithm with running time f ( k ) ⋅ n c f (k) · n^c f(k)⋅nc for some function f f f and some constant c c c.

• A parameterized problem is Slice-wise Polynomial (XP) if it is has an algorithm with running time f ( k ) ⋅ n g ( k ) f (k) · n^{g(k)} f(k)⋅ng(k) for some functions f , g f,g f,g.

Note: FPT → \rightarrow → XP, simply set g ( k ) = c g(k)=c g(k)=c.

7.1 Vertex Coloring

Two vertices in one edge must have distinct colors.

Since vertex coloring is a np hard problem, so unless P = N P P=NP P=NP, there can be no algorithm for k k k with running time f ( k ) ⋅ n g ( k ) f (k) · n^{g(k)} f(k)⋅ng(k).

7.2 k-clique

Given graph G G G and integer k k k, does G G G have a clique of size k k k. In other words, find a subset C ⊆ G C\subseteq G C⊆G, such that each vertex have edges with all the other vertices. (a complete graph)

Lemma k k k clique is X P XP XP.

There can be ( n k ) ≤ n k \binom{n}{k}\le n^k (kn​)≤nk such subsets, and we can check in O ( k 2 ) O(k^2) O(k2) time whether it’s a clique. Thus, the running time is O ( k 2 ⋅ n k ) O(k^2·n^k) O(k2⋅nk), X P XP XP. But it’s unknow if it is FTP.

7.3 k k k-Clique parameterized by Δ \Delta Δ

Δ \Delta Δ is the maximum degree of graph G G G.

Lemma: the problem now is F P T FPT FPT.

There are at most n ⋅ 2 Δ n·2^\Delta n⋅2Δ subsets, and each subsets can be checked in O ( Δ 2 ) O(\Delta ^2) O(Δ2) .