The study of the computational complexity of problems with respect to more than one parameter.

learn more… | top users | synonyms

-1
votes
1answer
85 views

FPT algorithm equivalent definitions [closed]

On this page, the definition of a Fixed-Parameter Tractable algorithm is given, followed by the very classical example, Vertex Cover. But how the complexity given for Vertex Cover, $O(kn+1.274^k)$ ...
12
votes
1answer
248 views

Gentle introduction to the algorithmic aspects of tree-depth

Treewidth and pathwidth are popular parameters, measuring the closeness of a graph to a tree or a path, respectively. Indeed, it seems treewidth is so popular it is featured in many papers, books, and ...
0
votes
1answer
93 views

Natural maximization problems in FPT

Is there a natural (and hopefully well-known) maximization problem that is known to be in FPT? For instance, Vertex Cover is in FPT, but it's a minimization problem. I'm looking for natural ...
7
votes
2answers
254 views

ETH: k-SAT vs. SAT?

Let SAT$_v$ be the language of those instances of SAT that contain variables $[v] = \{0,1,\dots,v-1\}$, let $k$-SAT be the language of those instances of SAT in which every clause has at most $k$ ...
5
votes
1answer
180 views

Easy decision hard counting Parametrized

It is known that counting perfect matchings in a bipartite graph is #P-complete. On the other hand, finding a perfect matching belongs in P. Is there a problem, that exhibits the same behavior in ...
7
votes
0answers
226 views

complexity of Sokoban with a small number of boxes

(I asked a very concise version of this one month ago on cs.stackexchange, and although it got edited, it was not (otherwise) responded to.) In this post, for positive integer values $k$, ...
7
votes
1answer
79 views

Problem with a group as complexity parameter?

I am currently studying a complexity problem related to symmetries, and am considering a study of the parameterized complexity of the problem. In theory, any part of the input can be fixed as a ...
8
votes
2answers
423 views

Implications of a problem being in XP when parameterized by diameter

Let $X$ be an NP-complete graph problem. Suppose $X$ is solvable in polynomial time on graphs of bounded diameter. In other words, $X$ parameterized by diameter is in XP. (Recall a problem is in XP if ...
2
votes
0answers
53 views

Parameterized Complexity of Minimum Type Selection

Consider the following problem that I call »Minimum Type Selection«: Input: $k$ sets of bit vectors, each of length $n$ and a number $l$. Question: Is it possible to pick exactly one bit vector from ...
7
votes
0answers
116 views

Is 4-colors precoloring extension for planar graphs fixed parameter tractable?

Given a planar graph $G=(V,E)$, there exists a quadratic algorithms for 4-coloring $G$ (and $G$ is surely 4-colorable). Assume you are given a set of $k$ constraints of the form "$v_i \text{ is ...
10
votes
2answers
250 views

Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?

Following the equivalent questions regarding NP-Completeness (see the weight question and the directed question), I was wondering how parameterized problems are affected by these attributes. ...
7
votes
1answer
156 views

Parameterized complexity of Exact Cover

Consider the following $\mathrm{ExactCover}$ problem: Given a collection $\mathcal{S}$ of subsets of a universe set $U$ and an integer $K$, find whether there exists a subcollection $\mathcal{S}^* ...
11
votes
0answers
158 views

Algorithmic advantages of pathwidth over treewidth

Treewidth plays an important role in FPT algorithms, in part because many problems are FPT parameterized by treewidth. A related, more restricted, notion is that of pathwidth. If a graph has pathwidth ...
0
votes
1answer
104 views

Graph theory: definiton of the crown of a graph

I'm currently reading "Invitation to Fixed-Parameter Algorithms" by Rolf Niedermayer. Page 69 gives the following definition of the crown of a graph, which I do not quite understand: A crown of a ...
4
votes
0answers
111 views

FPT algorithm for mixed integer program

It is known that every integer linear program parameterized by the number of variables is FPT (fixed parameter tractable). Is every mixed integer program parameterized by the number of integer ...
13
votes
2answers
261 views

Natural complete problems in higher levels of the $\mathsf{W}$-hierarchy

The $\mathsf{W}$-hierarchy is a hierarchy of complexity classes $\mathsf{W}[t]$ in parameterized complexity, see the Complexity Zoo for definitions. An alternative definition defines $\mathsf{W}[t]$ ...
7
votes
2answers
133 views

Is it known whether counting $q$-dimensional $p$-matching is $\#W[1]$-Hard?

The $q$-Dimensional $p$-Matching is defined as follows: Given disjoint universes $U_1,\ldots,U_q$, think of an element in $U_1\times\ldots\times U_q$ as a set that contains exactly one element from ...
1
vote
1answer
135 views

Node-weighted steiner problem with few terminals

Consider the node-weighted steiner problem: Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$. Output: a minimum weight ...
4
votes
0answers
162 views

Stronger reductions in parameterized complexity

An FPT-reduction between parameterized problems $P$ and $Q$ is a pair of functions $f$ and $p$, such that every instance $x$ of $P$ with parameter $k$ is mapped to an instance $f(x,k)$ of $Q$ with ...
2
votes
0answers
162 views

Multidimensional Knapsack W[1]-hard when parameterized by dimension

Under Multidimensional knapsack STRONGLY NP-complete it was discussed that the Multidimensional Knapsack problem is strongly NP-hard. Within this discussion the question whether the problem is ...
2
votes
0answers
130 views

Fixed-parameter tractability of SCS: finding the missing proof(s)

I am interested in two "super-objects" problems from computational biology. The first problem, dubbed Shortest Common Supersequence ($SCSy$), takes a family of sequences $s_1,\ldots,s_k$, and seeks a ...
4
votes
1answer
109 views

parameterized algorithms for geometric set cover

Are there any parametrized algorithms $W$-hardness results known for the computational problem Geometric Set Cover? It is known that set cover problem is $W[2]$ hard when parametrized by the solution ...
5
votes
0answers
105 views

Is minimum weight simple cycles through specified vertics fixed parameter tractable?

The problem formulation is as follows: Input: Undirected graph $G=(V,E)$, a set of vertices $S\subseteq |V|$, a weight function $w:E\to \mathbb{R}$ and a threshold $T\in \mathbb{R}$. ...
4
votes
1answer
248 views

Vertex disjoint simple paths of length k

A lot of effort has been invested in finding simple k-paths, as well as in finding vertex disjoint paths. Is there any known parametrized algorithm that given a graph $G=(V,E)$, decides whether there ...
21
votes
3answers
862 views

Using Kolmogorov complexity as input “size”

Say we have a computational problem, e.g. 3-SAT, that has a set of problem instances (possible inputs) $S$. Normally in the analysis of algorithms or computational complexity theory, we have some ...
4
votes
1answer
286 views

Crown Rule Reduction In Parameterized Complexity - Vertex Cover - Notion Question

I am reading the paper "Kernelizations for Parameterized Counting Problems", and had a question regarding some of the notation in the paper ...
12
votes
1answer
113 views

Clique-width expressions with logarithmic depth

When we are given a tree decomposition of a graph $G$ with width $w$, there are several ways in which we can make it "nice". In particular, it is known that it is possible to transform it into a tree ...
10
votes
2answers
258 views

W[1]-hard problems on bounded degree graphs

Do you know problems which are W[1]-hard even for bounded degree graphs? Metric Dimension is hard on graphs with degree at most 3, but it is W[2]-hard. Red-Blue Nonblocker used to be W[1]-hard on ...
4
votes
1answer
211 views

On Random Self-reducible properties

Permanent is random self-reducible. $\mathsf{SAT}$ is not random self-reducible since otherwise the polynomial hierarchy collapses to $\mathsf{\Sigma_3}$. 1) Is $k$-sum random self-reducible? That ...
11
votes
3answers
515 views

Exact Algorithms for Dominating set

Given a graph, $G = (V, E)$, I want to find an optimal $r$-domination for $G$. That is, I want a subset $S$ of $V$ such that all vertices in $G$ are at a distance of at most $r$ from some vertex in ...
10
votes
5answers
868 views

Books/Lecture Notes on Parametrized Complexity

I would like to learn about Parametrized Complexity (both on the algorithmic side and on the hardness side). What books/lecture notes can I read on this subject?
9
votes
1answer
241 views

Hitting sets with a subfamily

Let $F$ be a family of $d$-element subsets of a finite universe $U$ of objects. A family $H$ of $k$-element subsets of $U$, with $1 \le k < d$, is a $(k,d)$-hitting-set of $F$ if for each $V \in F$ ...
13
votes
2answers
408 views

Edit distance with move operations

Motivation: A coauthor edits a manuscript and I would like to see a clear summary of the edits. All "diff"-like tools tend to be useless if you are both moving text around (e.g., re-organising the ...
9
votes
1answer
309 views

Parametrized Complexity of Counting Bicliques

In a previous question Parametrized Algorithm for Finding Bicliques, I inquired if there were fast parametrized algorithms for finding a $k\times k$-biclique in an $n$ vertex graph and learnt that it ...
15
votes
4answers
679 views

Parametrized Algorithm for Finding Bicliques

Given an $n$ vertex undirected graph, what is the best known runtime bound for finding a subgraph which is a $k\times k$-biclique? Are there faster parametrized algorithms than the ...
5
votes
0answers
152 views

Can we achieve a better kernel for the Vertex Cover problem on planar graphs?

We have known how to get a $2k$ kernel for the Vertex Cover problem for thirty years, and it is not expected to be improved assuming UGC. My question is, can we do better for planar graphs? It is ...
4
votes
1answer
198 views

Is conversion of PRAM to parameter number of processors trivial

In section 2 of chapter 4 of Kumar the idea of scaling down is discussed. It is mentioned that the naive method (emulating by assignment) can scale the complexity of the problem more then just ...
2
votes
1answer
175 views

Complement problems are not in the same class in parametrized complexity hierarchy? If not in $P$

By "complement problems", I mean the two problems' objective functions are complement. For example, the vertex cover and its complement independent set in this sense. For a graph $G(V,E)$, their ...
11
votes
1answer
361 views

Monotone circuit complexity of computing functions on sparse inputs

The weight $|x|$ of a binary string $x\in\{0,1\}^n$ is the number of ones in the string. What happens if we are interested in computing a monotone function on inputs with few ones? We know that ...
17
votes
1answer
368 views

FPT vs W[P] - Parameterized Complexity

In parametrized complexity, $\mathsf{FPT} \subseteq \mathsf{W}[1]$ $\subseteq \mathsf{W}[2]$ $\subseteq \ldots \subseteq \mathsf{W}[P]$. It is conjectured that each of the containments is proper. If ...
5
votes
2answers
299 views

A variant of maximum matching: disjunctive constraints on the endpoints' degrees of edges in matching

The question is asked first at here. It described what the problem is and a trival greedy algorithm. Also the accepted answer gave a proof of its NP-completeness. Problem: Given a graph $G(V,E)$, ...
3
votes
1answer
374 views

measures for a DAG (directed acyclic graph)?

Recently, I want to devise some kernelization (in the framework of parameterized complexity) for problem on DAG. So, find a proper parameter is essential. Well, is there a measure for the importance ...
12
votes
1answer
242 views

Any results on binary boolean CSP beyond the fixed-parameter tractability of almost 2SAT problem?

Let $\varphi$ be a 2CNF formula and $k$ a nonnegative integer. It is proved in this paper that the problem of deciding whether one can delete at most $k$ clauses to make $\varphi$ satisfable, is ...
17
votes
2answers
442 views

Parameterized complexity of graph intersection number

What if anything is known about the parameterized complexity of computing the intersection number of a graph (the smallest number of cliques needed to cover all its edges)? It has long been known to ...
13
votes
5answers
578 views

Hardness of FPT problems

Vertex Cover can be easily reduced to Independent Set and vice versa. However, in the context of parameterized complexity, Independent set is harder than Vertex Cover. A kernel with $2k$ vertices ...
15
votes
3answers
349 views

Any references for techniques in FPT reductions?

As everyone knows, Garey and Johnson's famous book (and many others) provides an excellent reference for reduction technique in classical setting. Are there any surveys or books on the topic of ...
5
votes
1answer
297 views

What is the parameterized complexity of following model checking problem?

Input: Graph $G$ and formula $\varphi_1(\vec x),\varphi_2(\vec x)$ Parameter: $tw(G)+|\varphi_1|+|\varphi_2|$ Problem: Decide if $|\varphi_1(G)|=|\varphi_2(G)|$ where $tw(G)$ is the treewidth ...
10
votes
5answers
521 views

Instance of FPT-reductions that is not a polynomial-time reduction

In parametrized complexity people use fixed-parameter-tractable (FPT) reduction to prove W[t]-hardness. Theoretically a FPT-reduction is not a polynomial-time reduction, since it can run exponentially ...
38
votes
2answers
948 views

Is there a sensible notion of an approximation algorithm for an undecidable problem?

Certain problems are known to be undecidable, but it is nevertheless possible to make some progress on solving them. For example, the halting problem is undecidable, but practical progress can be ...
11
votes
1answer
274 views

Do “outer-bounded-genus” graphs have constant treewidth?

Let $k\in\mathbb{N}$ and denote by $G_k$ the set of all graphs that can be embedded on a surface of genus $k$ such that all vertices are situated on the outer face. For instance, $G_0$ is the set of ...