Skip to content

Overview

  • Motivation for parameterized intractability
  • Fixed‑parameter tractable reductions (fpt‑reductions)
  • The classes para‑NP and XP
  • The class W[P]
  • Logic preliminaries (continued)
  • The W‑hierarchy (via Boolean circuits or weighted Fagin definability)
  • The A‑hierarchy (via parameterized model checking)
  • Picture of all classes and their relations

Motivation: Two classical problems

Problem Classical complexity Parameterisation Parameterized behavior
QUERIES (conjunctive query on a database) NP‑complete \(k = \vert query\vert\)​ \(O(n^k)\) – not FPT (belongs to W[1])
LTL‑Model‑Checking (LTL formula on a Kripke structure) PSPACE‑complete \(k = \vert\varphi\vert\) \(O(k \cdot 2^{2k} \cdot n)\) – in FPT

Take‑away: classical hardness does not directly predict parameterized hardness; we need a theory of parameterized intractability.

Fixed‑Parameter Tractable (FPT) – recapitulation

Definition

\(\langle Q, \kappa \rangle \in \mathsf{FPT}\) iff there exist a computable \(f:\mathbb N\to\mathbb N\), a polynomial \(p\), and an algorithm \(A\) that decides \(x\in Q\) in time \(\le f(\kappa(x)) \cdot p(|x|)\).

Slices: The \(\ell\)‑th slice of a parameterized problem is \(\langle Q,\kappa\rangle_\ell := \{x\in Q \mid \kappa(x)=\ell\}\).

Proposition: If \(\langle Q,\kappa\rangle \in \mathsf{FPT}\), then every slice \(\langle Q,\kappa\rangle_\ell \in \mathsf{PTIME}\).

  • Example: p‑COLORABILITY (parameter = number of colours) is not in FPT unless P = NP, because its 3‑rd slice is 3‑COLORABILITY (NP‑complete).

Fixed‑Parameter Reductions

Definition

A mapping \(R : \Sigma_1^* \to \Sigma_2^*\) is an fpt‑reduction from \(\langle Q_1,\kappa_1\rangle\) to \(\langle Q_2,\kappa_2\rangle\) if:

  1. \(x \in Q_1 \iff R(x) \in Q_2\)
  2. \(R\) is computable in time \(f(\kappa_1(x)) \cdot p(|x|)\) for some computable \(f\) and polynomial \(p\).
  3. \(\kappa_2(R(x)) \le g(\kappa_1(x))\) for some computable \(g\).

Notation: \(\langle Q_1,\kappa_1\rangle \le_{fpt} \langle Q_2,\kappa_2\rangle\).

Properties

  • \(\le_{fpt}\) is transitive.
  • If \(Q_1 \le_{fpt} Q_2\), then \(Q_2 \in \mathsf{FPT} \Rightarrow Q_1 \in \mathsf{FPT}\); and \(Q_1 \notin \mathsf{FPT} \Rightarrow Q_2 \notin \mathsf{FPT}\).

Relation to parameter comparison

\(\kappa_1 \succeq \kappa_2\) (i.e., \(\exists g\, \kappa_2(x) \le g(\kappa_1(x))\)) iff the identity reduction \(x\mapsto x\) is an fpt‑reduction from \(\langle Q,\kappa_1\rangle\) to \(\langle Q,\kappa_2\rangle\).

Examples

  • p‑CLIQUE \(\equiv_{fpt}\) p‑INDEPENDENT‑SET.
  • p‑DOMINATING‑SET \(\equiv_{fpt}\) p‑HITTING‑SET.
  • Non‑example: the polynomial reduction between p‑INDEPENDENT‑SET and p‑VERTEX‑COVER (complement) is not an fpt‑reduction, because the parameter \(k\) would become \(n-k\), which cannot be bounded by a function of \(k\).

Hardness & completeness

Let \(\mathcal C\) be a class of parameterized problems.

  • \([\mathcal C]^{fpt}\) = closure of \(\mathcal C\) under fpt‑reductions.
  • \(\langle Q,\kappa\rangle\) is \(\mathcal C\)‑hard if \(\mathcal C \subseteq [\langle Q,\kappa\rangle]^{fpt}\).
  • \(\langle Q,\kappa\rangle\) is \(\mathcal C\)‑complete if \(\langle Q,\kappa\rangle \in \mathcal C\) and it is \(\mathcal C\)‑hard.

The Class para‑NP

Definition

A parameterized problem \(\langle Q,\kappa\rangle\) is in para‑NP if there exist a computable \(f\), a polynomial \(p\), and a nondeterministic algorithm \(A\) that decides \(x\in Q\) in at most \(f(\kappa(x)) \cdot p(|x|)\) steps.

Properties

  • para‑NP is closed under fpt‑reductions.
  • \(\mathsf{NP} \subseteq \mathsf{para-NP}\).
  • Examples: p‑CLIQUE, p‑INDEPENDENT‑SET, p‑DOMINATING‑SET, p‑HITTING‑SET, p‑COLORABILITY are all in para‑NP.
  • \(\mathsf{FPT} = \mathsf{para-NP}\) iff \(\mathsf{P} = \mathsf{NP}\).
  • A problem is para‑NP‑complete iff a finite union of its slices is NP‑complete. → p‑COLORABILITY is para‑NP‑complete (slice 3 is NP‑complete).

The Class XP (slicewise polynomial)

Idea: problems whose slices are in P (non‑uniform XP = XP\(_{nu}\)) is too large (contains undecidable problems).

The robust uniform version is XP:

Definition

\(\langle Q,\kappa\rangle \in \mathsf{XP}\) if there exists a computable function \(f\) such that membership \(x\in Q\) can be decided in time \(|x|^{f(\kappa(x))} + f(\kappa(x))\) (equivalently, \(\le f(\kappa(x)) \cdot p_{\kappa(x)}(|x|)\) for some family of polynomials \(p_k\)).

Examples

  • p‑CLIQUE, p‑INDEPENDENT‑SET, p‑DOMINATING‑SET, p‑HITTING‑SET are in XP (by brute‑force on the parameter).
  • p‑COLORABILITY is not in XP (unless P = NP), because its 3‑rd slice is NP‑complete; solving a slice in polynomial time would put 3‑COLORABILITY in P.

Relations

  • \(\mathsf{FPT} \subsetneq \mathsf{XP}\) (strict).
  • If \(\mathsf{P} \neq \mathsf{NP}\), then \(\mathsf{para-NP} \not\subseteq \mathsf{XP}\).

The Class W[P]

“One of the most important parameterized complexity classes.” (Flum, Grohe)

Definition via limited nondeterminism

A nondeterministic Turing machine \(M\) is \(\kappa\)‑restricted if on input \(x\) it performs

  • at most \(f(\kappa(x)) \cdot p(|x|)\) steps,
  • of which at most \(h(\kappa(x)) \cdot \log|x|\) are nondeterministic,

for some computable \(f,h\) and polynomial \(p\).

W[P] is the class of all parameterized problems that can be decided by a \(\kappa\)‑restricted nondeterministic Turing machine.

Theorems

  • \(\mathsf{FPT} \subseteq \text{W[P]} \subseteq \mathsf{XP} \cap \mathsf{para-NP}\).
  • W[P] is closed under fpt‑reductions.
  • p‑CLIQUE, p‑INDEPENDENT‑SET, p‑DOMINATING‑SET, p‑HITTING‑SET are in W[P].

Complete problem for W[P]

  • p‑WSAT(CIRC) (weighted satisfiability of Boolean circuits):
    Input: circuit \(C\), integer \(k\); Parameter: \(k\); Question: does \(C\) have a satisfying assignment of weight exactly \(k\)? → This is W[P]‑complete under fpt‑reductions.
  • Consequently, p‑DOMINATING‑SET reduces to it, showing membership in W[P] but also W[2] (see below).

Relation to classical limited nondeterminism

Cai & Chen (1997): \(\mathsf{FPT} = \text{W[P]}\) iff there exists a computable, non‑decreasing, unbounded function \(\iota\) such that \(\mathsf{P} = \mathsf{NP}[\iota(n)\cdot\log n]\) (the class of problems solvable in polynomial time with only \(\iota(n)\cdot\log n\) nondeterministic bits).

Logic Preliminaries (Continued)

  • Prenex normal form: \(Q_1 x_1 \dots Q_k x_k \,\psi\), \(\psi\) quantifier‑free.
  • \(Σ_0 = \Pi_0\): quantifier‑free formulas.
  • \(Σ_{t+1}\): formulas \(\exists x_1 \dots \exists x_k \,\varphi\) with \(\varphi \in \Pi_t\).
  • \(Π_{t+1}\): formulas \(\forall x_1 \dots \forall x_k \,\varphi\) with \(\varphi \in \Sigma_t\).

The W‑Hierarchy

Two equivalent definitions are common:

Definition via Weighted Fagin Definability

Weighted Fagin definability problem WD\(_\varphi\) (for a FO formula \(\varphi(X)\) with a free relation variable \(X\) of arity \(s\)):

  • Input: structure \(\mathcal A\), integer \(k\);
  • Parameter: \(k\);
  • Question: Does there exist a relation \(S \subseteq A^s\) with \(|S|=k\) such that \(\mathcal A \models \varphi(S)\)?

W‑hierarchy (Downey & Fellows 1995):

\(W[t] := \big[\, \text{p-WD-}\Pi_t \,\big]^{fpt}\) for \(t \ge 1\). (Here p‑WD-Π_t denotes the problem with parameter \(k\) and formula \(\varphi\) restricted to \(\Pi_t\).)

Examples of placement

  • p‑CLIQUE ∈ W[1]
  • p‑DOMINATING‑SET ∈ W[2]
  • p‑HITTING‑SET ∈ W[2]

Definition via Boolean Circuits

A circuit \(C\) has weft \(\le t\) if on every path from input to output there are at most \(t\) gates of fan‑in > 2 (“large gates”). Let \(CIRC_{t,d}\) be the class of circuits with weft \(\le t\) and depth \(\le d\).

Parameterized weighted satisfiability: p‑WSAT(\(CIRC_{t,d}\)) – determine whether a circuit in \(CIRC_{t,d}\) has a satisfying assignment of weight exactly \(k\) (parameter \(k\)).

Alternative definition: \(W[t] := \big[\, \{ \text{p-WSAT}(CIRC_{t,d}) \mid d \ge 1 \} \,\big]^{fpt}\).

Properties

  • \(\mathsf{FPT} \subseteq W[1] \subseteq W[2] \subseteq \dots \subseteq W[P]\) (all inclusions are believed to be strict).
  • p‑CLIQUE is W[1]‑complete.
  • p‑DOMINATING‑SET and p‑HITTING‑SET are W[2]‑complete.

Conjecture: \(\mathsf{FPT} \neq W[1]\). (If true, then none of the W[1]‑hard problems are FPT.)

Characterisation via weighted Fagin

  • \(W[t] = [\text{p-WD-}\Pi_t]^{fpt} = [\text{p-WD-}\Sigma_{t+1}]^{fpt}\).
  • \([\text{p-WD-}\Sigma_1]^{fpt} \subseteq \mathsf{FPT}\).
  • \(\bigcup_{t\ge 1} W[t] = [\text{p-WD-FO}]^{fpt} \subseteq W[P]\).

The A‑Hierarchy

Definition (Flum & Grohe 2001): \(A[t] := \big[\,\text{p-MC}(\Sigma_t)\,\big]^{fpt}\) for \(t \ge 1\), where p‑MC(\(\Phi\)) (parameterized model checking) is:

  • Input: structure \(\mathcal A\), formula \(\varphi \in \Phi\);
  • Parameter: \(|\varphi|\);
  • Question: \(\mathcal A \models \varphi\)?

Examples

  • p‑CLIQUE ∈ A[1] (it is expressed by a \(\Sigma_1\) sentence).
  • p‑DOMINATING‑SET ∈ A[2].
  • p‑HITTING‑SET ∈ A[2].
  • p‑SUBGRAPH‑ISOMORPHISM ∈ A[1].
  • p‑VERTEX‑DELETION ∈ A[2].
  • p‑CLIQUE‑DOMINATING‑SET ∈ A[2] (dominating every clique of a given size).

Relations to W‑hierarchy

  • \(A[1] = W[1]\).
  • \(W[t] \subseteq A[t]\) for all \(t \ge 1\) (and likely strict for \(t > 1\)).
  • \(A[t]\) corresponds to model checking for the \(t\)‑th level of the polynomial hierarchy, whereas \(W[t]\) is a refinement inside NP.

Global Picture of Classes

Think about polynomial-time hierarchy

Inclusions (all believed proper):

\(\mathsf{FPT} \subsetneq W[1] = A[1] \subsetneq W[2] \subseteq A[2] \subsetneq \dots \subsetneq W[P] \subseteq \mathsf{XP} \cap \mathsf{para-NP}\).

  • p‑CLIQUE ∈ W[1]‑complete → not in FPT unless \(W[1] = \mathsf{FPT}\).
  • p‑DOMINATING‑SET ∈ W[2]‑complete → even harder than W[1] problems if the hierarchy is strict.
  • p‑COLORABILITY is para‑NP‑complete → not in XP unless P = NP, and therefore cannot be in W[P], XP, or FPT.

Why the Theory Matters

  • Avoids wasting effort on problems that are provably not FPT (unless the hierarchy collapses).
  • Shows hardness relative to well‑studied classes.
  • Helps identify the most general parameter under which a problem remains FPT.

Summary

  • Parameterized intractability arises naturally: some NP‑hard problems become easy (FPT), others remain hard.
  • fpt‑reductions allow to compare problems parametrically and to define completeness.
  • Para‑NP and XP are large classes above FPT; they capture problems whose classical slices are already hard.
  • W[P] is the parameterized analogue of NP, defined via limited nondeterminism.
  • The W‑hierarchy (W[1], W[2], …) stratifies NP‑hard problems according to their parameterized complexity, with complete problems like Clique (W[1]), Dominating Set (W[2]).
  • The A‑hierarchy (A[1], A[2], …) is obtained by model checking for \(\Sigma_t\) sentences; it refines the polynomial hierarchy in the parameterized world.
  • These hierarchies provide strong evidence that many fundamental combinatorial problems are not fixed‑parameter tractable.