Parameterized complexity

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. Then the theory analyses how the running time (or space) for solutions to the problem behave as the parameters get larger. To illustrate the idea, the for a fixed k we can solve instances of vertex cover problem (vertices cover edges) in linear time, whereas the only known algorithms for dominating set problem (vertices cover vertices) is more or less search all possible size k subsets and hence require about Ω(n^k) time. When this idea is made formal, the first behaviour is called fixed parameter tractability, since, although both are polynomial time algorithms, the former is of the form O(n^c) independent of the parameter, and the latter is of the form Ω(n^{f(k)). Researchers had often studied restrictions of problems by restricting parameters such as maximum vertex degree, cutwidth, treewidth, or genus. Several authors had noted that there might be a general method of attacking intractability obtained through understanding the complexity as a function of parameters, including Vardi (in the context of databases) and Regan (in finite model theory).…

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. Then the theory analyses how the running time (or space) for solutions to the problem behave as the parameters get larger. To illustrate the idea, the for a fixed k we can solve instances of vertex cover problem (vertices cover edges) in linear time, whereas the only known algorithms for dominating set problem (vertices cover vertices) is more or less search all possible size k subsets and hence require about Ω(n^k) time. When this idea is made formal, the first behaviour is called fixed parameter tractability, since, although both are polynomial time algorithms, the former is of the form O(n^c) independent of the parameter, and the latter is of the form Ω(n^{f(k)). Researchers had often studied restrictions of problems by restricting parameters such as maximum vertex degree, cutwidth, treewidth, or genus. Several authors had noted that there might be a general method of attacking intractability obtained through understanding the complexity as a function of parameters, including Vardi (in the context of databases) and Regan (in finite model theory). Gurevich, Stockmeyer & Vishkin explicitly noted this: ``The message there is that although it is convenient in theory to express the size of a problem instance as a single number, the size of an instance is sometimes more accurately expressed in termsof several independent parameters, and it may be useful to know the running time of an algorithm as a function of more than one parameter. None of these approaches identified the key idea which is classifying problems according to how the exponent of the running time is affected as the parameters increased. The main idea in parameterized complexity is to stratify a problem by (collections of) parameters and then and to classify in terms of how running times grow with the parameter, typically f(k)n^c vs n^{f(k)}. This idea was first proposed by Abrahamson, Fellows, Ellis and Mata by classifying families of relations. In a series of papers, Downey and Fellows , sometimes with co-authors , laid the foundations of this area. For a computational complexity theory, we need a notion of what it means to be tractable, methods of comparing problems (reductions), and classes we regard as intractable, along with evidence for this belief. These were first identified in these basic papers . Although the theory of fixed parameter tractability is most often applied to analyse NP-complete and NP-hard languages, it also can be applied more generally. For example, the definition of fixed-parameter tractability can be applied to (unparameterized) languages of arbitrary complexity, meaning that there are languages L which are not, for example, elementary recursive yet have parameterizations which are fixed parameter tractable. Similarly, problems like Graph Isomorphism which are likely not NP-hard admit tractable parameterizations by fixing maximum degree of a vertex or treewidth . The existence of efficient, exact, and deterministic solving algorithms for NP-complete, or otherwise NP-hard, problems is considered unlikely, if input parameters are not fixed; all known solving algorithms for these problems require time that is exponential (so in particular super-polynomial) in the total size of the input. However, some problems can be solved by algorithms that are exponential only in the size of a fixed parameter while polynomial in the size of the input. Under the assumption that P ≠ NP, there exist many natural problems that require super-polynomial running time when complexity is measured in terms of the input size only but that are computable in a time that is polynomial in the input size and exponential or worse in a parameter . Hence, if is fixed at a small value and the growth of the function over is relatively small then such problems can still be considered "tractable" despite their traditional classification as "intractable". Such an algorithm is called a fixed-parameter tractable (FPT) algorithm, because the problem can be solved efficiently (i.e., in polynomial time and where the exponent of the polynomial does not increase with the increase of the parameters) for constant values of the fixed parameter. A parameterized problem that allows for such an FPT algorithm is said to be a fixed-parameter tractable problem and belongs to the class , and the early name of the theory of parameterized complexity was fixed-parameter tractability. The parameterised complexity approach has led to the discover of a large number of new exact algorithmic techniques for problems . These include the method of bounded search trees, color-coding, Courcelle's Theorem, Kernelization, iterative compression, and many others. An example of a problem that is thought not to be in FPT is graph coloring parameterised by the number of colors. It is known that 3-coloring is NP-hard, and an algorithm for graph -coloring in time f(k)n^{O(1)} for k=3 would run in polynomial time in the size of the input. Thus, if graph coloring parameterised by the number of colors were in FPT, then P = NP. There are a number of alternative definitions of FPT. For example, the running-time requirement can be replaced by f(k) + |x|^{O(1)} . Also, a parameterised problem is in FPT if it has a so-called kernel. Kernelization is a preprocessing technique that reduces the original instance to its "hard kernel", a possibly much smaller instance that is equivalent to the original instance but has a size that is bounded by a function in the parameter. FPT is closed under a parameterised notion of reductions called fpt-reductions. We say that one parameterized problem L fpt-reduces to L' iff there exists two functions (x, k) \mapsto x', k \mapsto k' , such that (x, k) \in L iff (x', k') \in L' (x, k) \mapsto x' is itself fixed parameter tractable. That is, there exists a constant c , and a function k \mapsto k , such that (x, k) \mapsto x' is computable in time \leq k|x|^c Obviously, FPT contains all polynomial-time computable problems. Moreover, it contains all optimisation problems in NP that allow an efficient polynomial-time approximation scheme (EPTAS) . Here k=\frac{1}{\epsilon} is the parameter, and showing a PTAS is hard according to one of the hierarchies below (e.g. W[1]-hard) and this parameter implies that the problem. likely has no EPTAS, and hence no fully polynomial time approximatin scheme. \textsf{FPT}=\textsf{para-NP} if and only if \textsf{P}=\textsf{NP} . A problem is para-NP-hard if it is \textsf{NP} -hard already for a constant value of the parameter. That is, there is a "slice" of fixed that is \textsf{NP} -hard. A parameterized problem that is \textsf{para-NP} -hard cannot belong to the class \textsf{XP} , unless \textsf{P}=\textsf{NP} . A classic example of a \textsf{para-NP} -hard parameterized problem is graph coloring, parameterized by the number of colors, which is already \textsf{NP} -hard for k=3 (see ). The class W[w] is then defined as their union: W[w][1] \subset W[w][2]\subset \dots \subset W[w] := \bigcup_{d \geq 1} W[w][d] More succinctly, W[w] is the set of problems fpt-reducible to a family of instance-specific Boolean circuits with weft \leq w and depth bounded by some problem-specific constant. A normalized circuit of weft w and depth d is a circuit, where the first d-w layers contain only small gates, and the last w layers contain alternating big gates of AND and OR. One can iterate the associative laws and de Morgan distribution laws to normalize the circuit in fpt-time. Therefore, without loss of generality, we can consider only normalized circuits. Model-theoretically, the class W[t] is defined as the class of problems fpt-reducible to \operatorname{p-MC}(\Sigma_{t, 1}) . While the W hierarchy is a hierarchy contained in NP, the A hierarchy more closely mimics the polynomial-time hierarchy from classical complexity. Machine-theoretically, the A hierarchy of problems are defined as problems that are fpt-reducible to computations by certain kinds of alternating Turing machines. The "A" stands for "alternating". Model-theoretically, the class A[t] is defined as the class of problems fpt-reducible to \operatorname{p-MC}(\Sigma_{t}) . For example, the k-clique problem can be specified as a model checking problem. The language has a single binary relation E , where E(x, y) means " x, y share an edge". Then, a finite model A is a graph, and it has a k-clique iff A \models \phi_k , where \phi_k := \exists x_{1:k}, \bigwedge_{1 \leq i This shows that the k-clique problem is in A[1] . A problem is A[i]-complete if it is A[i], and any A[i] problem fpt-reduces to it. By definition, W[0] \subset W[1] \subset \cdots, \quad W[i] \subset A[i], \quad A[0] \subset A[1] \subset \cdots \mathsf{FPT} = W[0] = A[0] : W[0] = A[0] since \Sigma_0 has no quantifiers at all, so there is no difference between \Sigma_0 and \Sigma_{0, 1} . \mathsf{FPT} \subset W[0] . For any FPT problem L can be trivially fpt-reduced thus: Solve the problem (x, k) \in L in fpt-time, then output a trivial Yes/No circuit that does nothing except output the correct Boolean. \mathsf{FPT} \supset W[0] . For any W[0] problem L , and any problem-instance c \in L , the circuitry c has 0 weft and \leq d depth, where d is fixed. Therefore, the output is determined by up to 2^d inputs. All other inputs are free for use. Therefore, one simply brute-force compute all 2^{2^d} possible inputs. If a certain input has weight k' and makes the circuit output True, then check if there are still enough inputs to fill the weight: \#(\text{inputs of }c) - 2^d \geq k - k' . W[1] = A[1] . Intuitively, problems in W[1] class can be interpreted of the form: Is there an object of size k with a certain locally-checkable property? In formula, it would be of the form \bigvee_{u_1, \dots, u_k}(\text{object constructed according to } u_1, \dots, u_k \text{ has a certain local property}) In fact, W[1] collapses to W[1, 2], the class of problems fpt-reducible to Boolean circuits of the form \bigwedge_i (x_{i, 1} \or x_{i, 2}) . That is, a big AND over many OR of fan-in 2. Examples of W[1]-complete problems include: Independent set Input: a graph G Parameter: an integer k Output: Whether G contains an independent set of size k Clique Input: a graph G Parameter: an integer k Output: Whether G contains a clique of size k Bipartite nonblocker Input: a bipartite graph (V_1, V_2, E) Parameter: an integer k Output: Whether there exists a subset S \subset V_1 of size k, such that any v \in V_2 has a neighbor u \not\in S . In other words, S does not block V_2 . Weight-k 2-satisfiability Input: a conjunctive normal formula of form \bigwedge_i (p_{i, 1} \or p_{i, 2}) , where i ranges over clauses. Parameter: an integer k Output: Whether there exists a weight-k satisfying assignment to the formula. Short Turing machine problem. Input: nondeterministic Turing machine M, a string x, an integer k. Output: Whether there exists one computational path, with which M accepts x in at most k steps. Note that the plain nonblocker problem is FPT. Note on the nondeterministic Turing machine. The machine may be specified by one of any of the standard formulations. One usually considers the one-tape Turing machine, but the short Turing machine problem remains W[1] even if we allow with f(k) tapes and even f(k) of f(k)-dimensional tapes, but even with this extension, the restriction to f(k) tape alphabet size is FPT. Crucially, because the machine M itself is part of the problem input, the input size n is bigger than the number of states of M. In this way, the Turing machine can take one of n possible computation paths per step, accessing n^{O(k)} steps in total within time k. Thus, we see that W[1] is not obviously contained within FPT. Downey and Fellows argue that the Short Turing Machine problem is the natural analog of the Cook-Levin Theorem that the satisfiability problem is NP-complete and gives as compelling evidence that W[1] is not FPT as the Cook-Levin Theorem does that P does not equal NP. The independent set problem can be encoded thus. Given each graph (V, E) , its independent set problem is encoded by the following weft-1 Boolean circuit: \Phi_{\text{IS}}(V, E) := \bigwedge_{\{u, v\}\in E} (\neg x_u \or \neg x_v) where E is the set of edges in the graph. The graph has an independent set of size k iff there is a weight-k input to its Boolean circuit, such that it outputs 1. The clique problem can be coded as \Phi_{\text{clique}}(V, E) := \bigwedge_{\{u, v\} \subset V, u \neq v, \{u, v\}\not\in E} (\neg x_u \or \neg x_v) It checks that any pair vertices that don't make an edge cannot be chosen, so any chosen set of vertices is forced to be a clique. The short Turing machine problem can be converted to a Boolean formula using the same proof idea as of the Cook–Levin theorem, which shows SAT is NP-complete by coding Turing machine computational traces as Boolean formulas. The following proof is from. Specifically, define the propositional variables: s_{t, i, j, a, b} : at time t, the Turing machine is in state i, and transitions to state j, reading a, and writing b, y_{t, p, a, b} : at time t, the tape position p has symbol a, and at time (t+1) has symbol b. Of the indices, time t and tape position p range over 1:k, The ranges of the indices to the Turing machine state i, j, transition m, and symbols a, b are determined by the description of the machine M, but they are both bounded within 1:n. Then, the formula \Phi_{\text{STM}, k}(M, x) is a conjunction of clauses enforcing the following constraints: Every Turing machine state transition is not disallowed by the nondeterministic transition rule. These look like s_{t, i, j, a, b} \to \neg s_{t+1, i', j', a', b'} , in other words, \neg s_{t, i, j, a, b} \or \neg s_{t+1, i', j', a', b'} . There are O(kn^4) such clauses. The Turing machine cannot be at two positions at a time, and cannot make two transitions at a time. Every tape cell state transition is not disallowed by the nondeterministic transition rule. Every tape cell state cannot have two symbols at a time. At time 0, the Turing machine is not out of its initial state and position, and x is not unwritten on the tape. The Turing machine is not in an unaccepting state at time k. A computational trace through the Turing machine is then fully specified by setting k variables of s_{t, i, j, a, b} to True to indicate the Turing machine state transitions at each time, and setting k^2 variables of y_{t, p, a, b} to True to indicate the tape state transition at each time. This reduces the short Turing machine problem to a problem of finding a weight- (k+k^2) satisfying assignment to a weft-1, depth-2, antimonotone Boolean circuit. One example showing how parameterised analysis differs from classical analysis is provided by Vapnik-Chervonenkis Dimension, which is known not to be NP-complete unless NP is a subset of DTIME (n^{\log n}) , and yet the parameterized version is W[1]-complete . The dominating set problem has formula \Psi_{\text{dom}}(V, E) = \bigwedge_{u \in V} \bigvee_{v \in \operatorname{Neighbor}[u]} x_v . \text{monotone-}W[i] = W[i] . Weighted Monotone i-Normalized Satisfiability is W[i]-complete. Weighted Monotone (i+1)-Normalized Satisfiability is in W[i]. If i>0 is odd, then \text{antimonotone-}W[i] = W[i] Weighted Antionotone i-Normalized Satisfiability is W[i]-complete. If i \geq 3 , then Weighted Antimonotone (i+1)-Normalized Satisfiability is in W[i]. These problems are essentially "artificial", in that they are not studied except within the context of parameterized complexity. The literature reports few naturally occurring problems that are W[i]-complete for i \geq 3 : Detection of inclusion dependencies in relational databases is W[3]-complete. Certain problems in supply-chain models are W[3]-complete or W[4]-complete. It is related to W by: W^*[1] = W[1], \; W^*[2] = W[2], \; W[t] \subset W^*[t] \subset W[t+2], \quad \forall t \geq 1 The AW hierarchy is obtained by adding alternation to the W hierarchy. The AW[t] class is defined as the class of problems fpt-reducible to this problem: Input: a Boolean circuit of weft at most t, and a partition of its inputs to I_1 \cup I_2 \cup \cdots \cup I_r Parameter: (r, k_1, \dots, k_r) Output: Whether the Boolean circuit is satisfiable under alternating weight- (k_1, \dots, k_r) conditions. The alternating weight- (k_1, \dots, k_r) is defined as follows: There exists a subset J_1 \subset I_1 of size k_1 , such that if we set exactly those inputs to True and the others to False, then, for any subset J_2 \subset I_2 of size k_2 , such that if we set exactly those inputs to True and the others to False, then, ... the Boolean circuit outputs True. One can interpret this as a 2-player game, with the first player trying to make the circuit output True, and the second player trying to make the circuit output False. The first player makes a move by setting exactly k_1 inputs of I_1 to True and the others to False, then the second player makes a move on I_2 , etc. The circuit is under alternating weight- (k_1, \dots, k_r) conditions iff player 1 has a winning strategy. It turns out that the finite levels of this hierarchy collapses: AW[1] = AW[2] = \cdots . Thus, the literature writes just a common symbol for them: AW[\ast] := AW[1] = AW[2]=\cdots . Above this class remain two classes, AW[SAT] and AW[P], the first allows boolean formulas in the circuit and the second arbitrary ones. Notably, deciding if a nondeterministic Turing machine has an accepting computation visiting at most k tape squares is put hard for AW[SAT] and lies in AW[P] . Abrahamson, Downey and Fellows observe that many problem complete for PSPACE have parameterized versions in this class. For instance asking if an instance of the Generalised Geography problem has a k-move winning strategy is complete for this class . There are a number of other hierarchies for parameterized complexity such as counting versions analogous to #P , as well as the M-hierarchy based around parameterizing the size of the problem rather than some aspect of the problem. For example, the problem of MiniCircuitSat_t takes inputs k and n in unary and a weft t circuit of size at most k log n, and asks if has a satisfying assignment. This problem is in FPT iff n variable 3 Sat is in DTIME(2^{o(n)}), that is, the Exponential Time Hypothesis fails. This observation allowed Cai and Juedes to give sharp lower bounds on parameterized exponential algorithms, assuming the ETH, and demonstrated a very close connection between parameterized complexity and subexponential complexity . Yijia Chen and Martin Grohe demonstrated that in fact there is an underlying isomorphism .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378823420 under CC BY-SA 4.0; modifications have been made.