Skip to main content

Questions tagged [parameterized-complexity]

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

Filter by
Sorted by
Tagged with
1 vote
0 answers
156 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, ...
Turbo's user avatar
  • 13k
2 votes
1 answer
121 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 ...
Sugyani's user avatar
  • 23
7 votes
0 answers
114 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: ...
rus9384's user avatar
  • 355
0 votes
0 answers
32 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,...
Hanchun Yuan's user avatar
1 vote
1 answer
59 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 ...
Naysh's user avatar
  • 686
1 vote
0 answers
60 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 ...
Hanchun Yuan's user avatar
5 votes
0 answers
63 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) ...
xtyner's user avatar
  • 81
1 vote
0 answers
58 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 ...
Naysh's user avatar
  • 686
6 votes
1 answer
144 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 ...
Michael Lampis's user avatar
0 votes
0 answers
78 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-...
Balchandar Reddy's user avatar
-1 votes
1 answer
127 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 ...
Balchandar Reddy's user avatar
0 votes
0 answers
95 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 ...
Balchandar Reddy's user avatar
0 votes
1 answer
195 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 ...
Noel Arteche's user avatar
5 votes
2 answers
246 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 ...
Noel Arteche's user avatar
0 votes
0 answers
84 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 ...
BBK's user avatar
  • 103
1 vote
1 answer
191 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 ...
Naysh's user avatar
  • 686
3 votes
1 answer
164 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 ...
Karagounis Z's user avatar
2 votes
0 answers
56 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, ...
advocateofnone's user avatar
3 votes
2 answers
157 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 ...
Yaroslav Bulatov's user avatar
4 votes
0 answers
206 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$ ...
Naysh's user avatar
  • 686
3 votes
0 answers
89 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$ ...
Inuyasha Yagami's user avatar
0 votes
0 answers
68 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'\...
user avatar
17 votes
0 answers
603 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 ...
Austin Buchanan's user avatar
8 votes
1 answer
367 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=\...
Giorgio Camerani's user avatar
2 votes
1 answer
83 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 ...
Blanco's user avatar
  • 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, ...
Felipe's user avatar
  • 301
7 votes
1 answer
172 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 ...
Haden Hooyeon Lee's user avatar
2 votes
1 answer
145 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)...
Haden Hooyeon Lee's user avatar
2 votes
0 answers
100 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 ...
Hennich's user avatar
  • 121
7 votes
0 answers
170 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 ...
LeechLattice's user avatar
4 votes
0 answers
113 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 ...
Springberg's user avatar
4 votes
0 answers
106 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 ...
Turbo's user avatar
  • 13k
3 votes
0 answers
317 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-...
VS.'s user avatar
  • 539
1 vote
0 answers
89 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 ...
Samuel Barr's user avatar
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 ...
R B's user avatar
  • 9,458
4 votes
0 answers
216 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)$ ...
newbie's user avatar
  • 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 ...
old's user avatar
  • 420
13 votes
1 answer
810 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 ...
Florent Foucaud's user avatar
3 votes
1 answer
273 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{...
Michael Wehar's user avatar
5 votes
2 answers
609 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}\}$. ...
Springberg's user avatar
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 ...
einpoklum's user avatar
  • 173
2 votes
1 answer
390 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 ...
Turbo's user avatar
  • 13k
10 votes
1 answer
188 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 ...
András Salamon's user avatar
8 votes
0 answers
829 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 ...
Manuel Lafond's user avatar
8 votes
0 answers
296 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$? ...
Michael Wehar's user avatar
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 ...
Michael Wehar's user avatar
13 votes
0 answers
219 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 ...
user avatar
9 votes
0 answers
164 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 ...
Michael Wehar's user avatar
-2 votes
2 answers
143 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 ...
maxdan94's user avatar
  • 563
5 votes
1 answer
244 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|)}$ ...
ivmihajlin's user avatar