Baby pih: Parameterized inapproximability of min csp
V Guruswami, X Ren, S Sandeep - arXiv preprint arXiv:2310.16344, 2023 - arxiv.org
The Parameterized Inapproximability Hypothesis (PIH) is the analog of the PCP theorem in
the world of parameterized complexity. It asserts that no FPT algorithm can distinguish a …
the world of parameterized complexity. It asserts that no FPT algorithm can distinguish a …
[PDF][PDF] Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter
tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the …
tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the …
Optimally repurposing existing algorithms to obtain exponential-time approximations
The goal of this paper is to understand how exponential-time approximation algorithms can
be obtained from existing polynomial-time approximation algorithms, existing parameterized …
be obtained from existing polynomial-time approximation algorithms, existing parameterized …
Simple Combinatorial Construction of the -Lower Bound for Approximating the Parameterized -Clique
Y Chen, Y Feng, B Laekhanukit, Y Liu - arXiv preprint arXiv:2304.07516, 2023 - arxiv.org
In the parameterized $ k $-clique problem, or $ k $-Clique for short, we are given a graph $
G $ and a parameter $ k\ge 1$. The goal is to decide whether there exist $ k $ vertices in $ G …
G $ and a parameter $ k\ge 1$. The goal is to decide whether there exist $ k $ vertices in $ G …
Parameterized Inapproximability Hypothesis under ETH
The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter
tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the …
tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the …
Parameterized Complexity of Equality MinCSP
G Osipov, M Wahlström - arXiv preprint arXiv:2305.11131, 2023 - arxiv.org
We study the parameterized complexity of MinCSP for so-called equality languages, ie, for
finite languages over an infinite domain such as $\mathbb {N} $, where the relations are …
finite languages over an infinite domain such as $\mathbb {N} $, where the relations are …
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
Abstract Parameterized Inapproximability Hypothesis (PIH) is a central question in the field
of parameterized complexity. PIH asserts that given as input a 2-CSP on k variables and …
of parameterized complexity. PIH asserts that given as input a 2-CSP on k variables and …
Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH
S Li, B Lin, Y Liu - arXiv preprint arXiv:2402.09825, 2024 - arxiv.org
In this paper we present a new gap-creating randomized self-reduction for parameterized
Maximum Likelihood Decoding problem over $\mathbb {F} _p $($ k $-MLD $ _p $). The …
Maximum Likelihood Decoding problem over $\mathbb {F} _p $($ k $-MLD $ _p $). The …
Constant Approximating Disjoint Paths on Acyclic Digraphs is W [1]-hard
M Włodarczyk - arXiv preprint arXiv:2409.03596, 2024 - arxiv.org
In the Disjoint Paths problem, one is given a graph with a set of $ k $ vertex pairs $(s_i, t_i) $
and the task is to connect each $ s_i $ to $ t_i $ with a path, so that the $ k $ paths are …
and the task is to connect each $ s_i $ to $ t_i $ with a path, so that the $ k $ paths are …
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
E Lee, P Manurangsi - arXiv preprint arXiv:2407.08917, 2024 - arxiv.org
Parameterized Inapproximability Hypothesis (PIH) is a central question in the field of
parameterized complexity. PIH asserts that given as input a 2-CSP on $ k $ variables and …
parameterized complexity. PIH asserts that given as input a 2-CSP on $ k $ variables and …