Questions tagged [parameterized-complexity]
The study of the computational complexity of problems with respect to more than one parameter.
115 questions
1
vote
0
answers
166
views
Relation between $k$-sum failure and $P=NP$
If $P=NP$ then $W[1]=FPT$ holds. Hence $k$-sum conjecture fails at a finite $k$. What can we say about the time complexity of $SAT$ and the lowest $k$ at which $k$-sum conjecture fails?
In particular, ...
- 13.3k
2
votes
1
answer
207
views
Enumerating all Vertex Covers of Size at most $k$
I am looking into the problem to generate all possible vertex covers (including both minimal vertex covers and non-minimal vertex covers) of size at most $k$? Is there any algorithm that can achieve ...
- 23
7
votes
0
answers
116
views
Parameterized complexity of factoring
When multiplying integer numbers $A$ and $B$, one can use a 0-1 matrix to represent one of the multiplication steps. For example, given numbers (written in binary) $A=1101$ and $B=1011$ the matrix is:
...
- 355
0
votes
0
answers
39
views
What't the relationship between subexp and polynomial kenrel?
In parameterized algorithms, we know there is a problem that
has a subexponential parameterized algorithm (subexp for short) and a polynomial kernel (e.g., split edge deletion problem);
has no subexp,...
- 11
1
vote
1
answer
69
views
What is known about the complexity of Network Diversion?
In the Network Diversion problem, we are given an undirected graph $G$ on $n$ vertices, with specified nodes $s$ and $t$ and specified edge $e$, and a positive integer $k$, and are tasked with ...
- 696
1
vote
0
answers
68
views
Why the $K_{d,d}$-free set cover problem is easier?
In parameterized complexity, $k$-set cover is W[2]-hard. The definition of $k$-set cover is as follows:
Input: A ground set $U$ and a family of sets $\cal{F}$;
Parameter: $k$;
Output: Whether there ...
- 11
5
votes
0
answers
71
views
W[t]-containment of partial covering problems
I would like to know more about the W[t]-containment of partial covering problems. Especially, I am interested in the question whether Partial Set Cover (Problem Definition at the end of the question) ...
- 81
1
vote
0
answers
68
views
What are the fastest known parameterized algorithms for Grid Tiling?
Let $k$ and $n$ denote positive integers.
In the $k$-GridTiling problem, for every pair of indices $(i,j)\in \{1, \dots, k\}^2$ we get a subset $S_{ij}\subseteq \{1, \dots, n\}^2$ of pairs of the ...
- 696
6
votes
1
answer
157
views
Complexity of induced Steiner Tree problem
Consider the following problem: we are given an undirected graph $G=(V,E)$ and three terminal vertices $t_1,t_2,t_3\in V$. We are asked whether there exists a set of vertices $S\subseteq V$ such that ...
- 3,722
0
votes
0
answers
112
views
Existence of W[1]-Hard construction from multiple hard problems
I am a research scholar working on parameterized complexity. Currently, I am exploring ways to prove the hardness of a problem by providing W[1]-Hard constructions. A problem is known to be fixed-...
-1
votes
1
answer
140
views
Parameters: Twin cover and Vertex cover
I am a research scholar, currently working on parameterized algorithms. I am working on a problem and have been exploring various parameters for which the problem remains unsolved. I have read the ...
0
votes
0
answers
100
views
Tractability with respect to multiple parameters
I am working on the decision version of an NP-complete problem. The problem is known to be fixed parameter tractable(FPT) with respect to the solution size $k$ as the parameter.
If I consider another ...
0
votes
1
answer
227
views
Parameterized complexity of Hitting Set with slightly bigger parameter
The Hitting Set problem, when parameterized by the size $k$ of the hitting set, is W[2]-hard. Is it also W[2]-hard when parameterized by $k$ plus the number of subsets in the instance?
I explain in a ...
- 1,049
5
votes
2
answers
265
views
Treewidth relations between Boolean formulas and Tseitin encodings
Suppose you have a propositional formula $\varphi$ in CNF. You want to efficiently obtain an equisatisfiable CNF formula encoding $\neg \varphi$. You use the usual Tseitin encoding with auxiliary ...
- 1,049
0
votes
0
answers
91
views
Parameterized Complexity of Vertex Multicut
Let $G$ be an undirected graph, $\{(s_1,t_1),\dots,(s_k,t_k)\}$ a collection of pairs of vertices, and $p$ an integer. The Vertex Multicut problem asks if there is a set $S$ of at most $p$ vertices ...
- 103
1
vote
1
answer
192
views
Nontrivial Algorithms for Coloring (Parameterized by Pathwidth)
Let $k$ be a positive integer. In the $k$-coloring problem, we are given a graph $G$ on $n$ nodes, and want to determine if there is a way to assign a color to each vertex of $G$ such that no two ...
- 696
3
votes
1
answer
168
views
Parameterized algorithm when the parameter is not known in advance?
In the setting of parameterized algorithms, we are typically given the problem instance as well as the value of the parameter.
However, it seems like in applications the value of the parameter should ...
- 649
2
votes
0
answers
58
views
Existing results around approximation of minimum 2-edge connected Steiner subgraph
Problem $1$: minimum 2-edge connected subgraph
We are given a $2$-edge connected undirected graph $G(V,E)$, and we are asked to find a $\textit{spanning}$ subgraph $H$, with minimum number of edges, ...
- 141
3
votes
2
answers
177
views
Parameterized complexity of tree/branch decomposition
I'm looking for an up to date reference for parameterized complexity of tree and branch decompositions. IE, complexity of finding tree/branch decomposition of optimal width in terms of relevant graph ...
- 4,731
4
votes
0
answers
229
views
Fastest Known Algorithm for $k$-Dimensional Matching and $k$-Exact Cover
Given a $k$-uniform hypergraph $G$ (i.e., each edge of $G$ contains precisely $k$ vertices) on $n$ vertices, the $k$-Exact Cover problem is the task of deciding if there exists $n/k$ edges in $G$ ...
- 696
3
votes
0
answers
93
views
Exact FPT Algorithm for Continuous Euclidean $k$-Means
The continuous Euclidean $k$-means problem is defined as follows:
Given a set $X$ of $n$ points in $d$ dimensional Euclidean space $\mathbb{R}^{d}$. Given a parameter $k>0$, find a partitioning $P$ ...
- 1,551
0
votes
0
answers
78
views
Dynamic programming algorithm to find a colorful subset of disjoint sets
Suppose there is a set $F=\{X_1 ,...,X_m\}$, such that $\forall 1\leq
i\leq m: |X_i|=3.$ Suppose we color the elements of $\bigcup F$ in
$3k$ colors. We wish to know if there is a subset $F'\...
user62160
17
votes
0
answers
610
views
Linear-time algorithm to test if clique number equals degeneracy bound?
Given a connected simple graph $G=(V,E)$, let $d$ denote its degeneracy and let $\omega$ denote the size of a maximum clique.
A well-known bound on the clique number is $\omega\le d+1$, which is ...
- 1,166
8
votes
1
answer
374
views
On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$
It has been shown in [1] that $k\text{-SAT}$ has a $2^{o(n)}$ algorithm if and only if it has a $2^{o(m)}$ algorithm, $n$ being the number of variables and $m$ being the number of clauses.
Being $s_k=\...
- 6,912
2
votes
1
answer
85
views
Is the reduction from a parametrized proplem to the problem kernel just a kind of Karp reduction (polynomial-time reduction)?
The kernel of a parameterized problem $L$ is a reduction $(x,k) \mapsto (x',k')$ such that:
$(x,k) \in L \Leftrightarrow (x',k') \in L$
$|x'| \leq f(k)$ for some function $f$
$k' \leq g(k)$ for some ...
- 421
19
votes
1
answer
1k
views
Has parameterized complexity led to better algorithms?
I know that for the vertex cover problem, if we know that the parameter $k$ (which is the number of vertices in the solution) is small, then we can expect to solve it feasibly in practice. So far, ...
- 301
7
votes
1
answer
177
views
Reducing Parameterized Problems (whose solution size can be "large") to W[i]-complete problems (for fixed i)
Note: Originally, this question was asked via a comment in this question, but was asked to post a separate question. :)
I'm looking for any known reductions of the following:
Given a parameterized ...
2
votes
1
answer
161
views
Proving membership in W-hierarchy when problem is not parameterized by its solution size
I'm curious about the following general problem:
Suppose that we have a parameterized problem whose input is $x$ and parameter is $k$ (which is NOT the size of a solution but something about the input)...
2
votes
0
answers
103
views
Running time of Tarski Quantifier Elimination
I'm looking for some formula/expression in a citable resource, that gives the running time for Tarski's quantifier elimination.
In my search, I only found the statement "it's not elementary" on ...
- 121
7
votes
0
answers
174
views
Subgraph isomorphism on graph sequences
I'm looking for a subgraph isomorphism algorithm that takes advantage of properties of graph sequences.
Say $\{G_i\}_{i=1}^k$ is a sequence of graphs on vertex set $\{1 ... n\}$, and two consecutive ...
- 193
5
votes
0
answers
118
views
Open Problems About Nowhere-Dense Classes of Graphs
I'm writing a survey about nowhere-dense graphs. I would like to list some of the main open problems in the field. In particular I would like to list problems of the following form.
The problem has ...
- 696
4
votes
0
answers
107
views
$XP_{\text{uniform}}=FPT$ and update to $EPTAS$ section in complexity zoo?
Complexity zoo in https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas has the following:
$FPT = XPuniform\implies EPTAS = PTAS$.
Fundamentals of Parametrized complexity on page $534$ has
...
- 13.3k
3
votes
0
answers
319
views
Difficulty of graph coloring and independent set?
Given a graph on $n$ vertices it is strongly $NP$-complete to decide it is $3$-colorable while it is easy to decide it is $n$-colorable.
Is there a parsimonious reduction from SUBSET-SUM to GRAPH-3-...
- 549
1
vote
0
answers
90
views
What is the motivation behind W[P]?
I've been researching Parameterized Complexity Theory, and I've been puzzled by the definition of W[P]. Why is the number of non-deterministic steps bounded by $log|n|$? What is the intuition I should ...
- 129
9
votes
5
answers
1k
views
W[1]-hard problems with FPT time approximation algorithms
I'm looking for problems that are hard to solve in FPT time but has an approximation algorithm. That is, problems that are:
R1. W[1]-hard.
R2. Admit a (preferably constant) approximation algorithm ...
- 9,508
4
votes
0
answers
221
views
Find a pair of nodes with maximum sum of distances in k given trees
For k edge-weighted trees $T_1,T_2...T_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum_{i=1}^k d_i(x,y)$$ where $d_i(x,y)$ ...
- 235
10
votes
1
answer
1k
views
Is parameterized complexity going to be the future of complexity theory?
I am a research scholar who works in Algorithms and Complexity theory, I use parameterized complexity to some extent. To me it appears that researchers in parameterized complexity are very active (I ...
- 420
13
votes
1
answer
900
views
Parameterized complexity of inclusion of regular languages
I am interested in the classic problem REGULAR LANGUAGE INCLUSION. Given a regular expression $E$, we denote by $L(E)$ the regular language associated to it. (Regular expressions are on a fixed ...
- 2,153
3
votes
1
answer
298
views
Are there any parameterized problems in non-uniform FPT that are suspected (but not proven) to be in uniform-FPT?
Getting Started
Consider a parameterized problem $F$. We use $n$ to denote the input size and $k$ to denote the parameter. Consider the fixed levels of $F$ which we denote by $\{F_k\}_{k\in\mathbb{...
- 5,167
5
votes
2
answers
674
views
Maximum Treewidth of a Graph with $m$ Edges
What is the maximum treewidth of a graph with $m$ edges? In other
words, what is the correct growth for the following function?
$\alpha(m) = max\{\mathrm{treewidth}(G): G \mbox{ has $m$ edges}\}$.
...
- 696
1
vote
0
answers
66
views
Parametrically-relaxed Kolmogorov complexity
Consider the following problem:
Input: An integer $n$ and a subset $S \subseteq \{0...n-1\}$ in some representation.
Output: The encoding of some kind of automaton (say, a Turing machine) which ...
- 173
2
votes
1
answer
410
views
On $NP$ and $XP$ classes?
On page 33 venn diagram in http://tcs.rwth-aachen.de/~sanchez/slides/Raleigh2014.pdf it is implied that $XP\subseteq NP$.
Below this there is a statement which says $XP\not = NP$ unless $P=NP$.
Is ...
- 13.3k
10
votes
1
answer
190
views
Name for "uniformly polynomial" subclass of XP?
Suppose $L$ is a parameterized language with respect to some alphabet $\Sigma$.
The $k$-slice of $L$ is $L_k = L \cap \{(x,k) \mid x \in \Sigma^{*}\}$, the set of instances in $L$ which have parameter ...
- 19.2k
8
votes
0
answers
877
views
A list of XP-hard problems
The class $XP$ is the class of problems parameterized by $k$ that can be solved in time $n^{f(k)}$ for some function $f$ (each $k$ may require a different algorithm).
In their book on parameterized ...
- 322
8
votes
0
answers
301
views
Given a Boolean formula, does there exist a small circuit that computes a satisfying assignment?
The 3-SAT problem can be defined as follows:
3-SAT
Input: A 3-CNF formula $\phi$ of size $m$ with $n$ variables.
Question: Does there exist a variable assignment that satisfies $\phi$?
...
- 5,167
9
votes
0
answers
1k
views
What are the best known reductions from SAT to CNF-SAT?
Problems
Let SAT denote the following problem:
Given a boolean formula, does there exist a satisfying assignment?
Let CNF-SAT denote the following problem:
Given a ...
- 5,167
13
votes
0
answers
221
views
Parameterized Algorithm to Speed up Exact Exponential-time Algorithm
The connection between $c^kn^{O(1)}$ for $c<4$ and exact exponential-time algorithms beating brute-force $O(2^n)$ algorithms has been known for a long time. However, when $c\geq 4,$ there are not ...
user17918
9
votes
0
answers
171
views
Parameterized complexity of deciding if a string can be computed by circuits of size $k\log(n)$
In the following, we will describe what seems to be a parameterized version of the minimum circuit size problem (MCSP).
Before we get started, we need the following concepts:
For every natural ...
- 5,167
-2
votes
2
answers
144
views
Simplifying a parametrized complexity given that a parameter is in $o(n)$ [closed]
The complexity of my algorithm is in $O(\frac{p^p}{p!}(\frac{n}{p})^k)$ for any $p=o(n)$ and $k>1$.
How can I simplify this complexity while removing this $p$?
For instance, for $p=2$ the ...
- 563
5
votes
1
answer
260
views
Hardness of Subgraph isomorphism problem for sparse pattern graph
Subgraph isomorphism problem is a well studied problem: given graphs $G$ and $H$, one needs to answer if $H$ contains $G$ as a subgraph. It was proven that this problem requires $|H|^{\theta(|G|)}$ ...
- 901