Parameterized Algorithms Ch. 1: exploiting a small k

Book: Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh, Parameterized Algorithms (Springer, 2016), Chapter 1 On the writing: the content and the reasoning here are mine. I used an AI to reorder it and format the tables.

---

So to start with the author picks up the Bar Fight Prevention Problem which is basically a problem which states:

"You have a list of all of the n people who will come to the bar, and for each pair of people a prediction of whether or not they will fight if they both are admitted. You need to figure out whether it is possible to admit everyone except for at most k troublemakers, such that no fight breaks out among the admitted guests."

The diagram of the graph the author gives:

---

My analysis for the solution

This is clearly the vertex cover problem which is a NP complete problem as everyone knows.

The standard non optimal solution is a exponential solution in $n$ which for bounds like $n = 10^4$ takes the time $2^{10^4}$, which is a extremely large number, much larger than even the Avogadro’s constant.

$2^{10^4} \approx 10^{3010} \qquad \text{(3,011 digits, Avogadro's constant has 24)}$

Now suppose we have the fact that $k$ ($\le 15$) is very small, thus we can exploit its advantage to solve the problem. We now do a chain of thoughts of different observations for the optimal solution:

Idea one

We can chose any pair of $k$ elements which is $\binom{n}{k}$ which is still large for the bounds:

$\binom{10^4}{15} \approx 7.6 \times 10^{47} \approx 10^{24} \times \text{Avogadro's constant}$

Idea two

We know that any node that has more than $k$ edges surely must be removed since for keeping that node we must remove the other $k+1$ nodes and hence that invalidates the answer, similarly for the nodes that are not connected to other nodes can surely be taken (isolated islands).

One precheck

We know that total edges count must be less than $k^2 + 1$.

(Why?) Reason is that at worst case even if each node is connected to $k$ other nodes, even after removal of $k$ nodes there will surely exist at least one edge which shows answer does not exist.

$k \text{ nodes} \times k \text{ edges each} = k^2 \implies m > k^2 \text{ has no solution}$

This is a very similar idea to what we do after removal of edges as in reverse process of the Kruskal Algorithm, reverse the idea and then it builds the answer. Please be clear this isn’t the actual answer and it just a heuristic unlike the correct idea of removing nodes with degree $k+1$ or higher.

Idea three

Now suppose we have a list of people who are admitted and some who aren’t, can have at max $k$ conflicts and minimum 1, thus there can be a total of $2k^2$ nodes in worst case for $k^2$ edges not used, as this is a dense graph overall it can be fast overall.

$\sum_v \deg(v) = 2m \le 2k^2$

Hence this takes the following number of operations:

$\binom{2k^2}{k}$

Idea four (Kernelization)

Say for some person with one edge we can surely take that.

(Why?) Reason is suppose we don’t take it and instead take someone else then we surely know that the other guy will have the node degree $\ge 1$. Hence it is always optimal to take those nodes with degree $1$.

Now we can reduce the bound of $2k^2$ to $k^2$, the reason is pretty simple, all the nodes with degree one aren’t present hence min degree is 2 and hence total edges at worst case $k^2$ has 2 end points thus nodes used $2k^2$ and there we know that each has atleast 2 edges hence worst case unique nodes is $k^2$.

$2 \cdot (\text{nodes}) \le \sum_v \deg(v) = 2m \le 2k^2 \implies \text{nodes} \le k^2$

Idea five

We can also bound the time complexity by another logic of bounding the search space, for each conflict try removing one of the two and keep going deep into the tree with remaining options decreased by 1, this way the worst case of recursive calls is $2^k$ as we know that at each height nodes double by 2 as the recurrence:

$T(k) = 2 \cdot T(k-1) + O(n + m)$

to check and verify if the solution exists as we know we can easily check any NP complete problem in polynomial time. Here $m$ is the possible conflicts which is bounded again by $nk/2$ reason being very similar to what it was above:

$2m = \sum_v \deg(v) \le nk \implies m \le nk/2$

hence the solution of recurrence becomes:

$O(2^k \cdot k \cdot n)$

Worst case bound is $2^k \cdot k \cdot n$ which is computable with smart implementation. If we kernelize first then $n \le k^2$, so each call costs $O(k^2)$ and the total is $O(2^k \cdot k^2)$.

---

The numbers

For $n = 10^4$ and $k = 15$:

Approach	Cost	Roughly	Runnable
Every subset	$2^n$	$10^{3010}$	no
Every $k$-subset (1)	$\binom{10^4}{15}$	$7.6 \times 10^{47}$	no
After forced removals (3)	$\binom{2k^2}{k} = \binom{450}{15}$	$3.8 \times 10^{27}$	no
After kernelization (4)	$\binom{k^2}{k} = \binom{225}{15}$	$9.1 \times 10^{22}$	no
Search tree (5)	$2^k \cdot k \cdot n$	$4.9 \times 10^{9}$	seconds
Kernelize, then search (4 + 5)	$2^k \cdot k^2$	$7.4 \times 10^{6}$	instant

The idea of exploiting small $k$ to find a much efficient solution is what motivates this topic.

---

FPT

A problem parameterized by $k$ is fixed-parameter tractable (FPT) if it can be solved in time $f(k) \cdot |I|^{O(1)}$, where $f$ is a computable function depending only on $k$.

A similar idea for finding cliques with the constraint of max degree bounded by some value delta say ($\Delta = 50$), this can be done by FPT as well. Any clique then has at most $\Delta + 1$ vertices, so for each vertex we only search its own neighbourhood:

$O(n \cdot 2^{\Delta+1} \cdot \mathrm{poly})$

---

I won’t state the standard definitions because those aren’t the point of discussion here unlike my understanding for the topic and that’s it for the first note. Do mail me for any suggestions as that would help me learn more about writing and expressing my thoughts!