# Questions tagged [parameterized-complexity]

Computational complexity with respect to one or more parameters of the input (apart from its plain length as a string), which capture intrinsically difficult instances

90 questions
Filter by
Sorted by
Tagged with
16 views

36 views

### Tree Decomposition Construction with Balanced Separations: Why 2/3?

I am working through the book "Parameterized Algorithms" https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf and at the chapter about tree decomposition I am trying to ...
73 views

### Polynomial kernelization for Set Splitting

In a set system $(U, F)$, $F\subseteq \mathcal{P}(U))$, we say that a function $f: U \to \{0, 1\}$ is a coloring of $(U, F)$. A set in $F$ is split by $f$ if $F$ receives both colors. The Set ...
46 views

### Prerequisites for studying parametrized complexity

Which areas of CS/Math should one have mastered before diving into parametrized complexity?
331 views

### Finding a kernel for d-Bounded degree deletion

In $d$ Bounded degree deletion problem, we are given an undirected graph $G$ and a positive integer $k$, and the task is to find at most $k$ such vertices whose removal decreases the the maximum ...
17 views

### What does a kernel of size n,n^2 ,... mean?

So according to Wikipedia, In the Notation of [Flum and Grohe (2006)], a ''parameterized problem'' consists of a decision problem $L\subseteq\Sigma^*$ and a function $\kappa:\Sigma^*\to N$, the ...
825 views

### Is there an NP-hard problem for which no Fixed-Parameter Tractable algorithm exists?

Question Is there an NP-hard problem for which we can add a parameter1 to create a "natural"2 parametrised problem for which no FPT algorithm exists? The adding a parameter is needed ...
387 views

### Are there any known W or W-hard problems?

We are currently working on a variant of domination parameter and we have shown that it is in W with regard to parameterized complexity. To show it is W-complete, we must show the problem is W...