Parameterized Complexity and ETH

We look into Parameterized Complexity theory (introduced by Downey and Fellows via many papers) and its connections to classical complexity theory specifically via the Exponential Time Hypothesis (of Impaggliazzo and Paturi 2001) in this post. Parameterized complexity provides a framework for a more refined analysis of hard problems. Heuristics, parallel algorithms, approximation schemes, randomized algorithms are some of the approaches used to counter such problems. But these approaches suffer from many defects ranging from no hard bounds on the quality of the solution (heuristics), to not being applicable to really large instances (parallel algorithms) to impractical solutions (like some PTAS's etc.).

Introduction:

Classical complexity classifies problems using the concept of some resource (time or space). This leads to a good theory but it also ignores any structural information in the input which makes problems appear harder then they really are. There is a wide variation in the worst-case complexities of known exact algorithms for the NP-complete problems. For e.g., there are pretty good 3SAT solvers present right now which scale to a large number of variables.

Parameterized complexity tries to explain these differences by assuming that there is some part of the problem (the `parameter') will be small and allow us to develop efficient poly-time algorithms. The classic example for this is to consider a database query - it has two parts the database and the query of which query is usually much smaller than the database. The query size $k$ would be the natural paramter for a parameterized complexity analysis by admitting algorithms whose non-polynomial behavior is restricted by the parameter: if $k$ is small and $n$ is large, $O(2^k . n)$ is better than $O(n^k)$.

The main contribution of the theory is establishing the intractability of certain problems by classifying problems into complexity classes by reductions which are inherently 2-dimensional depending on the problem size as well the parameter. A problem can have different parameterizations also, each leading to different results.


Complexity Classes - FPT and the W[t] hierarchy:

A parameterized language $L$ is a subset of $\Sigma^* x \Sigma^*$ where $\Sigma$ is a finite alphabet. Let $(x, k) \in L$, then we call $x$ the main part and $k$ the parameter.

a) Tractability - Fixed-parameter tractable (FPT): $L \in FPT$ if it can be decided in time at most $f(k) . |x|^{O(1)}$ for an arbitary function $f$. For a fixed $k$ it is in P, moreover for every $k$ it is in the same polynomial class via the same machine. As an example, consider the $p-SAT$ problem where given the formula $\phi$ and the parameter $k = $ number of variables in $\phi$ decide whether $\phi$ is satisfiable. This is clearly in FPT as the obvious brute force approach for formula of size $n$ with $k$ variables will take time $O(2^k . n)$. There are many real world problems which are in FPT like parameterized Vertex Cover which uses the kernelization technique to get a $O(k . n + 1.286^k)$ algorithm (due to Chen, Kanj and Jia, 2001). Note that the classical Vertex Cover is NP complete - yet this result shows that it
is not as `hard' as say Independent Set.

b) Parametric Intractability: Analogously to classical complexity theory, Downey and Fellows developed a completeness program for intractable parameterized problems. In order to compare the hardness of parameterized problems, we need a 2-dimensional reduction (called `parameterized-reduction'). Roughly, a language $L$ is parameterically reducible to $L'$ if there is an FPT algorithm that transforms $(x, k)$ to $(x', k')$ so that $(x, k) \in L$ iff $(x', k') \in L'$ and $k' = g(k)$ where $g$ is an unrestricted function. Note that Karp reductions are rarely parameterized reductions (e.g. Clique to Independent Set is one of the exceptions).


1) W[1]: The lowest class of parameterized intractability can be defined as the set of languages that are reducible to the Short-Turing Machine Acceptance problem (also called the $k$-step halting problem) where we want to determine for an input consisting of a nondeterministic Turing machine M and a string x, whether M has a computation path accepting x in at most k steps. In some sense, this is the parameterized analogue to the Turing machine acceptance problem: the basic generic NP-complete problem in classical complexity theory. Canonical problems include Independent Set (does $G$ have an independent of size $k$), Weighted 3SAT (does $\phi$ have a satisfying assignment of weight $k$) etc. We will also give an alternative definition of W[1] afterwards which is actually used for the basic results.


2) The W[t] hierarchy: Interestingly, while general $k-$SAT and 3SAT are equivalent for NP-hardness in classical complexity, there is no known parameterized reduction computing general satisfiability from 3-CNF formulae. This leads to a realization that the logical depth of a formula affects its parameterized complexity. Intuitively it is related to the number of alternations between unbounded fan-in AND and OR gates. Hence, we can base the hierarchy on the complexity of circuits required to check a solution.

The W[t] is based on Circuit-SAT problem (parameterized by the weight of input like for Weighted 3SAT) for family of circuits $F_{h, t}$ having:
1. Small gates: with constant fan-in
2. Large gates: with unbounded fan-in

and of depth $h$ (max. number of gates in the path) and weft (max. number of large gates in the path) at most $t$. Clearly, we have the containments:

$FPT \subseteq W[1] \subseteq W[2] \ldots $

It is not known whether the containments are strict or not. Note that W[1] can now be defined as the class that can be reduced to an parameterized Circuit SAT on the family of constant depth weft 1 circuits. Downey and Fellows (1995) proved that parameterized Independent Set is W[1]-complete. The hardness proof is very intricate and we omit it here. Note that using this definition it is easy to see why Independent Set is in W[1] (sketch):
1. Each vertex in $G$ corresponds to one input gate in the circuit
2. For every edge $(v, u) \in G$ build a small OR gate: $(1-v) \wedge (1-u))$
3. Output from small gates are given as input to a single large AND gate.

Interestingly unlike NP-hardness results, W[1]-hardness for the $k-$Halting Problem uses Independent Set completeness as intermediate results. There have been many papers demonstrating naturally occuring W[t]-complete problems like Dominating Set for W[2] etc.)- for an extensive list of already classified problems see the Downey and Fellows monograph.

Exponential Time Hypothesis (ETH)

ETH was first studied by Impagliazzo, Paturi and Zane 2001 and it states that 3SAT $\notin$ DTIME$(2^{o(n)})$, where $n$ is the number of variables. They also proved that the hypothesis is robust to analogous hypotheses for other NP-complete problems like Independent Set etc. In fact, they also showed that the ETH is independent of size measure: 3SAT is solvable in time $2^{o(n)}$ iff it is solvable in time $2^{o(m)}$ for input size $m$. Note that this suggests that weighted 3SAT should also be intractable for `any parameter'.

Connections with Classical complexity:

The above paragraph suggests that ETH and parameterized complexity might be related. In fact they are and Chen and Grohe recently proved that ETH and paramterized complexity theory are isomorphic by an explicit reduction preserving isomorphism. We don't show that here, instead we prove a simpler result that yet provides a strong link to ETH (proof is a version from Downey, Castro et. al 2003 and uses parameterized miniaturization and is different from the original proof by Abhramson, Downey and Fellows):

Theorem: If FPT = W[1], then ETH fails i.e. 3SAT $\in$ DTIME$(2^{o(n)})$.

Proof: We use the equivalent definition of ETH based on simple Circuit SAT. The idea is to capture the ETH perfectly in a parameterized complexity class. The starting point is the Mini-Circuit SAT problem which is a parameterized miniaturization of simple Circuit SAT:
Input: Positive integers $k$ and $n$, and a Boolean circuit of total size at most $k\log n$.
Decision: Does there exist any $x$ for which $C(x) = 1$.

Note that the parameter here is $k$. Also, trying all possible inputs gives a brute force $O(n^k)$ algorithm. Next we give a cruicial lemma due to Cai and Juedes 2001. It essentially fully characterizes the ETH with a complexity class in parameterized theory.

Lemma 1: Mini-Circuit SAT is in FPT iff ETH fails.
Proof: One direction follows from the brute force algorithm and noting that $2^{o(k \log n)}$ is a FPT function.

Now suppose we are given a boolean circuit $C$ of size $N$ and that Mini-Cirsuit SAT is solvable in FPT time $f(k)n^c$. Set $k = f^{-1}(N)$ and $n = 2^{N/k}$. In general $k = f^{-1}(N)$ will be some slowly growing function of $N$; so $N/k = o(N)$ and also $cN/k = o(N)$. Hence using the FPT algorithm for Mini-Circuit SAT we have a running time for Circuit SAT as: $f(f^{-1}(N)) (2^{N/k})^c = N 2^{cN/k} = 2^{cN/k + \log N} = 2^{o(N)}$.
Thus ETH fails. Proved.

Now lets define the complexity class MINI[1] to be the set of languages that are FPT reducible to Mini-Circuit SAT. It turns out that many $k\log n$ miniatures of familiar NP-complete problems are MINI[1] complete (Downey, Fellows et al. 2002). It is easy to see this because essentially all the usual NP-complete reductions of Circuit SAT to these problems work as FPT reductions because they were also linear size reductions.

We concentrate on the Mini-Independent Set problem. Surprisingly, it can be reduced to the usual parameterized Independent Set problem.

Lemma 2: Independent Set parameterized by the size of independent set is MINI[1]-hard.
Proof: We give a Turing reduction. Let graph $G = (V, E)$ be the miniature, for which we wish to determine whether $G$ has an independent set of size $r$ with $|V| \leq k\log n$. We can think of verices of $G$ as organized in $k$ blocks $V_1, V_2, \ldots, V_k$ each of size $\log n$. So for each possible way of writing $r$ as a sum of $k$ terms $r = r_1 + r_2 + r_3 + \ldots + r_k$ with each $r_i \leq \log n$, we have a turing reduction branch which represnts a commitment to choose $r_i$ vertices from the corresponding block $V_i$ to be in the independent set. The total number of branches are $(\log n)^k$ and again it is a FPT-function.

For each branch, we produce a graph $G'$ that has an independent set of size $k$ iff the miniature $G$ has an independent set of size $r$ distributed as indicated by the commitment made on that branch. The graph $G'$ consists of $k$ cliques with some cross edges. The ith clique consists of vertices in correspondence with the subsets of $V_i$ of size $r_i$. An edge connects a vertex $x$ in the ith clique and a vertex $y$ in the jth clique iff there is a vertex $u$ in the subset $S_x \subseteq V_i$ represented by $x$ and a vertex $v$ in the subset $S_y \subseteq V_j$ represented by $y$, such that $(u, v) \in E$.

From Lemma 2 we can conclude that $FPT \subseteq MINI[1] \subseteq W[1]$. We just need to observe now that if FPT = W[1] it implies $M[1] \subseteq FPT$. By Lemma 1, ETH fails.
Proved.

Discussion:

The above result hints that FPT vs W[1] problem is like the P vs NP problem of classical complexity theory. In fact it was also proved by Downey and Fellows that FPT $\neq$ W[1] implies P $\neq$ NP. But it is not known that if FPT $\neq$ W[1] implies anything about the rest of W[t] hierarchy. Importantly, practical intracbility of problems in NP, which are unlikely to be complete for NP, can be shown using W[t] hardness results. Parameterized complexity has deep connections to other complexity results as well. Just recently (a week back) Galesi and Lauria showed a connection with Proof Complexity based on randomized algorithms for W[t]-hard problems. The field is very active and there are many papers and surveys being published in it.