The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
0answers
95 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
135 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
127 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
98 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
76 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
227 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
811 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 ...
3
votes
2answers
256 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 ...
7
votes
0answers
47 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
167 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
162 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 ...
9
votes
3answers
440 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
4answers
718 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?
8
votes
1answer
229 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$ ...
12
votes
2answers
316 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
278 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
584 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
147 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 ...
3
votes
1answer
189 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 ...
1
vote
1answer
166 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
340 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 ...
12
votes
0answers
260 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
293 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
295 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
219 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 ...
16
votes
2answers
418 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 ...
12
votes
5answers
519 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
340 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
287 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
474 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 ...
36
votes
2answers
799 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
246 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 ...
16
votes
2answers
506 views

Hardness of parameterized CLIQUE?

Let $0\le p\le 1$ and consider the decision problem CLIQUE$_p$ Input: integer $s$, graph $G$ with $t$ vertices and $\lceil p\binom{t}{2} \rceil$ edges Question: does $G$ contain a clique on at ...
7
votes
3answers
295 views

Is parametrized maximum independent clauses problem in FPT?

Parametrized maximum independent clauses problem: Input : A r-CNFSAT formula F having n variables and m clauses, k Ques : Does there exists at least k clauses such that they are mutually independent ...
32
votes
2answers
876 views

Parameterized complexity of Hitting Set in finite VC-dimension

I'm interested in the parameterized complexity of what I'll call the d-Dimensional Hitting Set problem: given a range space (i.e. a set system / hypergraph) S = (X,R) having VC-dimension at most d and ...