Motivation

Classical Complexity

Analyzing problems by resources: space or time. Needed to solve them on a reasonable machine model.

As a function of the input size $n=\vert x\vert$

Variety of complexity classes: $\mathsf{P},\mathsf{LOGSPACE},\mathsf{NP},\mathsf{PSPACE},\cdots$.

Tractable problems: polynomial-time computable $\in\mathsf{P}$.

Theory of intractability: reductions, $\mathsf{NP}$-completeness.

Drawback

They measure problem size $n=\vert x\vert$, only in terms of input instances $x$, and ignores structural information about instances.

Sometimes problems are easier to solve if additional structure information of input is available.

Parameterized Complexity

It measures complexity also in terms of a parameter $k=\kappa(x)$ that may depend on the input $x$.

Fixed-parameter tractable problems

Relaxing polynomial time solvability to algorithms whose non-polynomial behavior $f(k)\cdot p (n)$ is restricted by parameter $k$.

Complexity classes: $\mathsf{FPT},\mathsf{XP},\mathsf{W[P]},\mathsf{W}$- and $\mathsf{A}$- hierarchies.

Theory of fixed-parameter intractability

Parameterized VS. Classical Problems

A classical decision problem is a pair $\langle\Sigma,Q\rangle$ where

$Q\subseteq\Sigma^*$ the set of problem yes-instances over a finite alphabet $\Sigma$.

A parameterized decision problem is a triple $\langle\Sigma,Q,\kappa\rangle$ where

$Q\subseteq\Sigma^*$ the set of problem yes-instances over a finite alphabet $\Sigma$.
$\kappa:\Sigma^*\to\mathbb N$ a function, the parameterization.

We regularly shorten $\langle\Sigma,Q,\kappa\rangle$ to $\langle Q,\kappa\rangle$.

Assumption: The parameterization $\kappa$ can be efficiently computed.

Examples of Parameterized Problems

A Parameterized Clique Problem

$p$-CLIQUE:

Input: a graph $G$ and an integer (parameter) $k$.
Output: Does there exists a clique of size $k$ in $G$?

$p$-HITTING SET:

Input: a universe $U=\{x_1,\cdots,x_n)\}$, a collection of sets $\mathcal S=\{S_1,\cdots,S_m)\}$ where $S_i\subseteq U$ and an integer $k$.
Output: Does there exists a set $S\subseteq U$ s.t. $|S|\leq k$ and $S\cap S_i\neq\emptyset$, for all $i$.
Parameter: $\max_i|S_i|$.
The problem is $\mathsf{NP}$-hard even if $\max_i|S_i|=2$. But it is fixed-parameter tractable.

The Art of Parameterization

What is a good parameter?

"Small"
Intuitive
Efficiently computable

Different types of parameters

Size of the solution we are looking for
Size of some parts of the instance
Structural property of the instance
Combination of values

Examples:

Graph problems: maximum degree, treewidth, diameter...
Social choice problems: number of voters, candidates, correlation of preferences...
Boolean formulas: number of variables, number of clauses...
String problems: maximum length of a string, size of the alphabet...

Fixed Parameter Tractability

Class $\mathsf{FPT}$

Definition: A parameterized problem $\langle Q,\kappa\rangle$ is fixed-parameter tractable if $\exists f:\mathbb N\to\mathbb N$ computable $\exists p\in\mathbb N[X]$ polynomial, $\exists\mathbb A$ algorithm, which takes inputs in $\Sigma^*$ and $\forall x\in\Sigma^*$

$\mathbb A$ decides if $x\in Q$ in time $\leq f(\kappa(x))\cdot p(|x|)$.

$\mathsf{FPT}$ is the complexity classes of all fixed-parameter tractable problems.

Assumption $\kappa$ is polynomially computable, or itself $\mathsf{FPT}$-computable.

Goal in parameterized algorithmics:

Designing $\mathsf{FPT}$ algorithms.
Trying to make both factors $f(\kappa(x))$ and $p(x)$ as small as possible, or showing that finding such factors is impossible.

Slices of FPT Problems are in P

The $\ell$-th slice of a parameterized problem $\langle Q,\kappa\rangle$: $\langle Q,\kappa\rangle_\ell=\{x\in Q|\kappa(x)=\ell\}$ (as a classical problem).

Proposition: If $\langle Q,\kappa\rangle\in\mathsf{FPT}$, then $\langle Q,\kappa\rangle_\ell\in\mathsf{P}$ for all $\ell\in\mathbb N$.

If $\langle Q,\kappa\rangle\in\mathsf{FPT}$, then there are a computable function $f:\mathbb N\to\mathbb N$, a polynomial $p$, and an algorithm $\mathbb A$ that decides $x\in\Sigma^*$ in running time $\leq f(\kappa(x))\cdot p(|x|)$. This algorithm can also be used to decide the $\ell$-th slice in time $\leq f(\ell)\cdot p(|x|)$, which for fixed $\ell$ is a polynomial.

Application of proposition:

$p$-COLORABILITY

Input: a graph $G$ and $k\in\mathbb N$ ($k$ as the parameter)
Output: Is $G$ $k$-colorable?

Known: $3$-COLORABILITY is $\mathsf{NP}$-complete. Since $3$-COLORABILITY is equivalent to $p$-COLORABILITY₃, it follows that $p$-COLORABILITY $\not\in\mathsf{FPT}$.

Slice-Wise Polynomial Problems

Class $\mathsf{XP}$

Definition: A parameterized problem $\langle Q,\kappa\rangle$ is slice-wise polynomial if $\exist f,g:\mathbb N\to\mathbb N$ computable, $\exist\mathbb A$ algorithm, which takes inputs in $\Sigma^*$ and $\forall x\in\Sigma^*$

$\mathbb A$ decides if $x\in Q$ in time $\leq f(\kappa(x))\cdot|x|^{g(\kappa(x))}$.

$\mathsf{XP}$ is the complexity class of slice-wise polynomial problems.

Slices of XP Problems are in P

Similar proposition and proof as for $\mathsf{FPT}$.

By the same argument, $3$-COLORABILITY $\not\in\mathsf{XP}$.

Kernelization

Kernelization is

a systematic study of polynomial-time preprocessing algorithms.
an important tool in the design of parameterized algorithms

It

is often a collection of efficient preprocessing rules.
transforms an instances $x$ into a smaller equivalent instance $x'$. Hopefully, $|x'|\leq g(\kappa(x))$ - use a non-efficient exact algorithm.

Definition: Let $\langle Q,\kappa\rangle$ be a parameterized problem over $\Sigma$. A kernelization of $\langle Q,\kappa\rangle$ is a function $K:\Sigma^*\to\Sigma^*$ such that:

$\forall x\in\Sigma^*:x\in Q\Leftrightarrow K(x)\in Q$
$K$ is polynomial-time computable.
There is a computable function $h:\mathbb N\to\mathbb N$ s.t. $\forall x\in\Sigma^*:|K(x)|\leq h(\kappa(x))$

We say that such a kernelization $K$ is polynomial (resp. linear), and $Q$ has a polynomial (resp. linear) kernel, if the function $h$ is polynomial (resp. linear)

Lemma: If $\langle Q,\kappa\rangle$ admits a kernel and is decidable, then $\langle Q,\kappa\rangle\in\mathsf{FPT}$.

Since $\langle Q,\kappa\rangle$ is decidable: $\exists\mathbb A$ that decides $x\in\Sigma^*$ in time $\leq f(|x|)$ steps.

Assuming a polynomial algorithm $\mathbb A_K$ for the kernel $K$, we construct a FPT algorithm $\mathbb A(K)$ for $\langle Q,\kappa\rangle$:

If $K(x)\not\in Q$ output no. If $K(x)\in Q$, output yes.

Running time: $\mathbb A(K)=\mathsf{time}(\mathbb A_K)+\mathsf{time}(\mathbb A(K(x)))=p(|x|+f(|K(x)|))\leq p(|x|)+f(h(\kappa(x)))$

$=(f\circ h)(\kappa(x))\cdot(1+p)(|x|)=\tilde f(K(x))\cdot\mathsf{poly}(|x|)\in\mathsf{FPT}$.

Lemma: If $\langle Q,\kappa\rangle\in\mathsf{FPT}$, then $\langle Q,\kappa\rangle$ admits a kernel.

Let $\mathbb A$ be an algorithm that solves $\langle Q,\kappa\rangle$ in time $f(\kappa(x))\cdot p(|x|)$, for all $x\in\Sigma^*$, where $f$ computable, and $p$ polynomial. We assume $p(n)\geq\max\{n,1\}\forall n\in\mathbb N$.

If $Q=\emptyset$ or $Q=\Sigma^*$, we define $K(x)=\epsilon$. Otherwise we have $\emptyset\subsetneq Q\subsetneq\Sigma^*$, and we choose some $x_0\in Q$ and $x_1\in\Sigma^*\backslash Q$.

We define the polynomial-time computable function $K:\Sigma^*\to\Sigma^*$ by: $$ K(x)= \begin{cases} x_0:\mathbb A\text{ accepts }x\text{ in}\leq p(|x|)\cdot p(|x|)\text{ steps.} \newline x_1:\mathbb A\text{ rejects }x\text{ in}\leq p(|x|)\cdot p(|x|)\text{ steps.} \newline x:\mathbb A\text{ doesn't terminate in}\leq p(|x|)\cdot p(|x|)\text{ steps.} \end{cases} $$ We have $p(|x|)\cdot p(|x|)\leq f(\kappa(x))\cdot p(|x|)$, and hence $|K(x)|=|x|\leq p(|x|)\leq f(\kappa(x))$. Therefore $K$ is a kernel.

The Point Line Cover Problem

$p$-POINT-LINE-COVER:

Input: $n$:points in the plane and an integer $k$ ($k$ as a parameter)
Output: Do there exist $k$ lines that cover all points?

How to kernelize the problem:

If we have a line that hits $\geq k+1$ points: include it in the solution, remove the points hit by it, decrease $k$ by $1$.
If we cannot apply rule 1, and we have more than $k^2$ points, then say no, and return a trivial no instance.

Observation: Let $(x,\kappa)$ be a yes instance of the problem s.t. rule 1 cannot be applied, then $n\leq k^2$ holds.

Proposition: $p$-POINT-LINE-COVER $\in\mathsf{FPT}$ and it admits a kernel of size with $k^2$ points.

The Vertex Cover Problem

$p$-VERTEX-COVER

Input: A graph $G$ and an integer $k$ ($k$ as a parameter)
Output: Does there exist a vertex cover of size at most $k$?

Definition: Let $G$ be a graph and $S\subseteq V(G)$. The set $S$ is called a vertex cover if for every edge of $G$ at least one of its endpoints is in $S$.

Kernelization:

Delete all isolated vertex.
If there is a vertex $v$ of degree at least $k+1$, delete $v$ and incident edges, decrease $k$ by $1$.
Let $(G,k)$ be an instance to which rule 1 and 2 are not applicable. If $G$ has $>k^2+k$ vertices or $>k^2$ edges, then $(G,k)$ is a no instance that can be replaced by a trivial no-instance.

Observations:

After exhaustive application of Rule 1 and 2, all vertices have degree between $1$ and $k$.
If $G$ has maximum degree $d$, $k$ vertices can cover $\leq k\cdot d$ edges.
If $G$ has a vertex cover of $\leq k$ vertices after exhaustive application of two rules, then $G$ has $\leq k^2$ edges (and $\leq k^2+k$ vertices)

Theorem (Samuel Buss): $p$-VERTEX-COVER $\in\mathsf{FPT}$, because it admits a kernel with at most $O(k^2)$ vertices and $O(k^2)$ edges.

Crown Decomposition and Crown Lemma

A crown decomposition of a graph $G$ is a partitioning $(C,H,R)$ of vertices s.t.

$C\neq\emptyset$.
$C$ is an independent set.
$H$ separates $C$ and $R$.
$G$ contains a matching of $H$ into $C$.

Crown lemma (König, Hall): Let $G$ be a graph with no isolated vertices and with at least $3k+1$ vertices. There is a polynomial-time algorithm that:

either finds a matching of size $k+1$ in $G$;
or finds a crown decomposition of $G$.

Better Kernel for Vertex Cover

Rule 1: Delete isolated vertices.

Rule 2: If $|V|\geq 3k+1$ apply Crown lemma.

If it returns a matching of size $k+1$ then conclude that $(G,k)$ is no instance.

If it returns a crown decomposition $V=C\cup H\cup R$:

Pick the vertices in $H$ in the solution
Reduce $(G,k)$ to $(G-H,k-|H|)$
Reduce $(G-H,k-|H|)$ to $(G-H-C,k-|H|)$ by rule 1.

Theorem: $p$-VERTEX-COVER admits a kernel with at most $3k$ vertices.

Dual Coloring Problem

$p$-COLORABILITY

Let $k\in\mathbb N$. A graph $G(V,E)$ is $k$-colorable if there is a function $C$ s.t. $C(u)\neq C(v)\forall (u,v)\in E$.

We can obtain a kernel with $O(k)$ vertices using crown decomposition.

Rule 1: Remove all isolated vertices, add random color to them.

Rule 2: Consider the complement graph $\bar G$. If $|V|>3k$, apply the Crown lemma to $\bar G$.

If it returns a matching of size $k+1$, then conclude that $(G,k)$ is a yes-instance.

If it returns a crown decomposition $V=\bar V=C\cup H\cup R$

The vertices in $H$ can be saved.
Reduce $(G,k)$ to $(G-H-C,k-|H|)$ if $|H|<k$, and otherwise to a yes-instance.
Note that the vertices in $C$ belong to a clique in $G$, that is we need $|C|$ colors, and that we need different colors for $R$.

$p$-DUAL-COLORING admits a kernel with at most $3k$ vertices.

Sunflower Lemma

Definition: A sunflower with $k$ petals and a core $Y$ is a collection of sets $S_1,\cdots,S_k$ s.t. $S_i\cap S_j=Y$ for all $i\neq j$. The sets $S_i\backslash Y$ are petals and must be non-empty.

Sunflower Lemma (Erdös, Rado): Let $\mathcal A$ be a family of sets over a universe $U$ s.t. each set in $\mathcal A$ has cardinality $d$.

If $|\mathcal A|>d!(k-1)^d$, then $\mathcal A$ contains a sunflower with $k$ petals which can be computed in time polynomial in $|\mathcal A|,|U|,k$.

Application to d-Hitting Set

$p$-$d$-HITTING-SET

Input: A family $\mathcal A$ of sets over a universe $U$, where each set has cardinality$\leq d$ and a positive integer $k$. ($k$ as a parameter)

Output: Does there exists a subset $H\subseteq U$ of size at most $k$ s.t. $H$ intersects each set in $\mathcal A$?

Observation: If $\mathcal A$ contains a sunflower $\mathcal S$ of $k+1$ sets, then every hitting set $H$ of $\mathcal A$ with $|H|\leq k$ must intersect the core $Y$ of $\mathcal S$. Otherwise it is a no-instance, because $H$ cannot intersect each of the $k+1$ petals $S_i\backslash Y$.

Rule: Let $(U,\mathcal A,k)$ be an instance of $d$-HITTING-SET. Assume that $\mathcal A$ contains a sunflower $\mathcal S$ of cardinality $k+1$ with core $Y$. Then return $(U',\mathcal A',k)$ where $\mathcal A'=(\mathcal A\backslash\mathcal S)\cup Y,U'=\bigcup\mathcal A'=\bigcup_{X\in\mathcal A'}X$.

There is a kernel of $p$-$d$-HITTING-SET with $\leq d!k^dd$ sets and $\leq d!k^dd^2$ elements.

If for some $d'\in[d]$, the number of sets in $\mathcal A$ of size $d'$ is more than $d'!k^{d'}$, then the sunflower lemma yields a sunflower of size $k+1$. Rule applies. By applying this rule exhaustively, we obtain a new family of sets $\mathcal A'$ with $\leq d'!k^{d'}$ sets of size $=d'$ for every $d'=[d]$. Hence $|\mathcal A'|\leq d!k^dd$ and $|U'|=d!k^dd^2$.

If $\emptyset\in\mathcal A'$ (a sunflower had an empty core), then it is a no instance.