8 Search Results for "Ren, Xuandi"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.34
On the Hardness of Approximating Distances of Quantum Codes

Authors: Elena Grigorescu, Vatsal Jha, and Eric Samperton

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
The problem of computing distances of error-correcting codes is fundamental in both the classical and quantum settings. While hardness for the classical version of these problems has been known for some time (in both the exact and approximate settings), it was only recently that Kapshikar and Kundu showed these problems are also hard in the quantum setting. As our first main result, we reprove this using arguably simpler arguments based on hypergraph product codes. In particular, we get a direct reduction to CSS codes, the most commonly used type of quantum code, from the minimum distance problem for classical linear codes. Our second set of results considers the distance of a graph state, which is a key parameter for quantum codes obtained via the codeword stabilized formalism. We show that it is NP-hard to compute/approximate the distance of a graph state when the adjacency matrix of the graph is the input. In fact, we show this is true even if we only consider X-type errors of a graph state. Our techniques moreover imply an interesting classical consequence: the hardness of computing or approximating the distance of classical codes with rate equal to 1/2. One of the main motivations of the present work is a question raised by Kapshikar and Kundu concerning the NP-hardness of approximation when there is an additive error proportional to a quantum code’s length. We show that no such hardness can hold for hypergraph product codes. These observations suggest the possibility of a new kind of square root barrier.
Cite as

Elena Grigorescu, Vatsal Jha, and Eric Samperton. On the Hardness of Approximating Distances of Quantum Codes. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 34:1-34:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grigorescu_et_al:LIPIcs.FSTTCS.2025.34,
  author =	{Grigorescu, Elena and Jha, Vatsal and Samperton, Eric},
  title =	{{On the Hardness of Approximating Distances of Quantum Codes}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{34:1--34:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.34},
  URN =		{urn:nbn:de:0030-drops-251152},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.34},
  annote =	{Keywords: quantum codes, minimum distance problem, NP-hardness, graph state distance}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.98
Fine-Grained Classification of Detecting Dominating Patterns

Authors: Jonathan Dransfeld, Marvin Künnemann, and Mirza Redzic

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider the following generalization of dominating sets: Let G be a host graph and P be a pattern graph P. A dominating P-pattern in G is a subset S of vertices in G that (1) forms a dominating set in G and (2) induces a subgraph isomorphic to P. The graph theory literature studies the properties of dominating P-patterns for various patterns P, including cliques, matchings, independent sets, cycles and paths. Previous work (Kunnemann, Redzic 2024) obtains algorithms and conditional lower bounds for detecting dominating P-patterns particularly for P being a k-clique, a k-independent set and a k-matching. Their results give conditionally tight lower bounds if k is sufficiently large (where the bound depends the matrix multiplication exponent ω). We ask: Can we obtain a classification of the fine-grained complexity for all patterns P? Indeed, we define a graph parameter ρ(P) such that if ω = 2, then (n^ρ(P) m^{(|V(P)|-ρ(P))/2})^{1±o(1)} is the optimal running time assuming the Orthogonal Vectors Hypothesis, for all patterns P except the triangle K₃. Here, the host graph G has n vertices and m = Θ(n^α) edges, where 1 ≤ α ≤ 2. The parameter ρ(P) is closely related (but sometimes different) to a parameter δ(P) = max_{S ⊆ V(P)} |S|-|N(S)| studied in (Alon 1981) to tightly quantify the maximum number of occurrences of induced subgraphs isomorphic to P. Our results stand in contrast to the lack of a full fine-grained classification of detecting an arbitrary (not necessarily dominating) induced P-pattern.
Cite as

Jonathan Dransfeld, Marvin Künnemann, and Mirza Redzic. Fine-Grained Classification of Detecting Dominating Patterns. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 98:1-98:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dransfeld_et_al:LIPIcs.ESA.2025.98,
  author =	{Dransfeld, Jonathan and K\"{u}nnemann, Marvin and Redzic, Mirza},
  title =	{{Fine-Grained Classification of Detecting Dominating Patterns}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{98:1--98:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.98},
  URN =		{urn:nbn:de:0030-drops-245679},
  doi =		{10.4230/LIPIcs.ESA.2025.98},
  annote =	{Keywords: fine-grained complexity theory, domination in graphs, subgraph isomorphism, classification theorem, parameterized algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.88
Parameterized Approximability for Modular Linear Equations

Authors: Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, and Magnus Wahlström

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider the Min-r-Lin(ℤ_m) problem: given a system S of length-r linear equations modulo m, find Z ⊆ S of minimum cardinality such that S-Z is satisfiable. The problem is NP-hard and UGC-hard to approximate in polynomial time within any constant factor even when r = m = 2. We focus on parameterized approximation with solution size as the parameter. Dabrowski, Jonsson, Ordyniak, Osipov and Wahlström [SODA-2023] showed that Min-r-Lin(ℤ_m) is in FPT if m is prime (i.e. ℤ_m is a field), and it is W[1]-hard if m is not a prime power. We show that Min-r-Lin(ℤ_{pⁿ}) is FPT-approximable within a factor of 2 for every prime p and integer n ≥ 2. This implies that Min-2-Lin(ℤ_m), m ∈ ℤ^+, is FPT-approximable within a factor of 2ω(m) where ω(m) counts the number of distinct prime divisors of m. The high-level idea behind the algorithm is to solve tighter and tighter relaxations of the problem, decreasing the set of possible values for the variables at each step. When working over ℤ_{pⁿ} and viewing the values in base-p, one can roughly think of a relaxation as fixing the number of trailing zeros and the least significant nonzero digits of the values assigned to the variables. To solve the relaxed problem, we construct a certain graph where solutions can be identified with a particular collection of cuts. The relaxation may hide obstructions that will only become visible in the next iteration of the algorithm, which makes it difficult to find optimal solutions. To deal with this, we use a strategy based on shadow removal [Marx & Razgon, STOC-2011] to compute solutions that (1) cost at most twice as much as the optimum and (2) allow us to reduce the set of values for all variables simultaneously. We complement the algorithmic result with two lower bounds, ruling out constant-factor FPT-approximation for Min-3-Lin(R) over any nontrivial ring R and for Min-2-Lin(R) over some finite commutative rings R.
Cite as

Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, and Magnus Wahlström. Parameterized Approximability for Modular Linear Equations. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 88:1-88:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dabrowski_et_al:LIPIcs.ESA.2025.88,
  author =	{Dabrowski, Konrad K. and Jonsson, Peter and Ordyniak, Sebastian and Osipov, George and Wahlstr\"{o}m, Magnus},
  title =	{{Parameterized Approximability for Modular Linear Equations}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{88:1--88:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.88},
  URN =		{urn:nbn:de:0030-drops-245562},
  doi =		{10.4230/LIPIcs.ESA.2025.88},
  annote =	{Keywords: parameterized complexity, approximation algorithms, linear equations}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.39
Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems

Authors: Barış Can Esmer and Ariel Kulik

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In this paper, we present Sampling with a Black Box, a unified framework for the design of parameterized approximation algorithms for vertex deletion problems (e.g., Vertex Cover, Feedback Vertex Set, etc.). The framework relies on two components: - A Sampling Step. A polynomial-time randomized algorithm that, given a graph G, returns a random vertex v such that the optimum of G⧵ {v} is smaller by 1 than the optimum of G, with some prescribed probability q. We show that such algorithms exist for multiple vertex deletion problems. - A Black Box algorithm which is either an exact parameterized algorithm, a polynomial-time approximation algorithm, or a parameterized-approximation algorithm. The framework combines these two components together. The sampling step is applied iteratively to remove vertices from the input graph, and then the solution is extended using the black box algorithm. The process is repeated sufficiently many times so that the target approximation ratio is attained with a constant probability. We use the technique to derive parameterized approximation algorithms for several vertex deletion problems, including Feedback Vertex Set, d-Hitting Set and 𝓁-Path Vertex Cover. In particular, for every approximation ratio 1 < β < 2, we attain a parameterized β-approximation for Feedback Vertex Set, which is faster than the parameterized β-approximation of [Jana, Lokshtanov, Mandal, Rai and Saurabh, MFCS 23']. Furthermore, our algorithms are always faster than the algorithms attained using Fidelity Preserving Transformations [Fellows, Kulik, Rosamond, and Shachnai, JCSS 18'].
Cite as

Barış Can Esmer and Ariel Kulik. Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{canesmer_et_al:LIPIcs.ICALP.2025.39,
  author =	{Can Esmer, Bar{\i}\c{s} and Kulik, Ariel},
  title =	{{Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{39:1--39:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.39},
  URN =		{urn:nbn:de:0030-drops-234165},
  doi =		{10.4230/LIPIcs.ICALP.2025.39},
  annote =	{Keywords: Parameterized Approximation Algorithms, Random Sampling}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.65
On Average Baby PIH and Its Applications

Authors: Yuwei Liu, Yijia Chen, Shuangle Li, Bingkai Lin, and Xin Zheng

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
The Parameterized Inapproximability Hypothesis (PIH) asserts that no FPT algorithm can decide whether a given 2CSP instance parameterized by the number of variables is satisfiable, or at most a constant fraction of its constraints can be satisfied simultaneously. In a recent breakthrough, Guruswami, Lin, Ren, Sun, and Wu (STOC 2024) proved the PIH under the Exponential Time Hypothesis (ETH). However, it remains a major open problem whether the PIH can be established assuming only W[1]≠FPT. Towards this goal, Guruswami, Ren, and Sandeep (CCC 2024) showed a weaker version of the PIH called the Baby PIH under W[1]≠FPT. In addition, they proposed one more intermediate assumption known as the Average Baby PIH, which might lead to further progress on the PIH. As the main contribution of this paper, we prove that the Average Baby PIH holds assuming W[1]≠FPT. Given a 2CSP instance where the number of its variables is the parameter, the Average Baby PIH states that no FPT algorithm can decide whether (i) it is satisfiable or (ii) any multi-assignment that satisfies all constraints must assign each variable more than r values on average for any fixed constant r > 1. So there is a gap between (i) and (ii) on the average number of values that are assigned to a variable, i.e., 1 vs. r. If this gap occurs in each variable instead of on average, we get the original Baby PIH. So central to our paper is an FPT self-reduction for 2CSP instances that turns the above gap for each variable into a gap on average. By the known W[1]-hardness for the Baby PIH, this proves that the Average Baby PIH holds under W[1] ≠ FPT. As applications, we obtain (i) for the first time, the W[1]-hardness of constant approximating k-ExactCover, and (ii) a tight relationship between running time lower bounds in the Average Baby PIH and approximating the parameterized Nearest Codeword Problem (k-NCP).
Cite as

Yuwei Liu, Yijia Chen, Shuangle Li, Bingkai Lin, and Xin Zheng. On Average Baby PIH and Its Applications. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 65:1-65:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.STACS.2025.65,
  author =	{Liu, Yuwei and Chen, Yijia and Li, Shuangle and Lin, Bingkai and Zheng, Xin},
  title =	{{On Average Baby PIH and Its Applications}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{65:1--65:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.65},
  URN =		{urn:nbn:de:0030-drops-228900},
  doi =		{10.4230/LIPIcs.STACS.2025.65},
  annote =	{Keywords: Average Baby PIH, Parameterized Inapproximability, Constraint Satisfaction Problem, Exact Set Cover, W\lbrack1\rbrack-hardness}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2024.6
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP

Authors: Karthik C. S., Euiwoong Lee, and Pasin Manurangsi

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

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 alphabet size n, it is 𝖶[1]-hard parameterized by k to distinguish if the input is perfectly satisfiable or if every assignment to the input violates 1% of the constraints. An important implication of PIH is that it yields the tight parameterized inapproximability of the k-maxcoverage problem. In the k-maxcoverage problem, we are given as input a set system, a threshold τ > 0, and a parameter k and the goal is to determine if there exist k sets in the input whose union is at least τ fraction of the entire universe. PIH is known to imply that it is 𝖶[1]-hard parameterized by k to distinguish if there are k input sets whose union is at least τ fraction of the universe or if the union of every k input sets is not much larger than τ⋅ (1-1/e) fraction of the universe. In this work we present a gap preserving FPT reduction (in the reverse direction) from the k-maxcoverage problem to the aforementioned 2-CSP problem, thus showing that the assertion that approximating the k-maxcoverage problem to some constant factor is 𝖶[1]-hard implies PIH. In addition, we present a gap preserving FPT reduction from the k-median problem (in general metrics) to the k-maxcoverage problem, further highlighting the power of gap preserving FPT reductions over classical gap preserving polynomial time reductions.
Cite as

Karthik C. S., Euiwoong Lee, and Pasin Manurangsi. On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{karthikc.s._et_al:LIPIcs.IPEC.2024.6,
  author =	{Karthik C. S. and Lee, Euiwoong and Manurangsi, Pasin},
  title =	{{On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.6},
  URN =		{urn:nbn:de:0030-drops-222322},
  doi =		{10.4230/LIPIcs.IPEC.2024.6},
  annote =	{Keywords: Parameterized complexity, Hardness of Approximation, Parameterized Inapproximability Hypothesis, max coverage, k-median}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.27
Baby PIH: Parameterized Inapproximability of Min CSP

Authors: Venkatesan Guruswami, Xuandi Ren, and Sai Sandeep

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
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 satisfiable 2CSP instance from one which is only (1-ε)-satisfiable (where the parameter is the number of variables) for some constant 0 < ε < 1. We consider a minimization version of CSPs (Min-CSP), where one may assign r values to each variable, and the goal is to ensure that every constraint is satisfied by some choice among the r × r pairs of values assigned to its variables (call such a CSP instance r-list-satisfiable). We prove the following strong parameterized inapproximability for Min CSP: For every r ≥ 1, it is W[1]-hard to tell if a 2CSP instance is satisfiable or is not even r-list-satisfiable. We refer to this statement as "Baby PIH", following the recently proved Baby PCP Theorem (Barto and Kozik, 2021). Our proof adapts the combinatorial arguments underlying the Baby PCP theorem, overcoming some basic obstacles that arise in the parameterized setting. Furthermore, our reduction runs in time polynomially bounded in both the number of variables and the alphabet size, and thus implies the Baby PCP theorem as well.
Cite as

Venkatesan Guruswami, Xuandi Ren, and Sai Sandeep. Baby PIH: Parameterized Inapproximability of Min CSP. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{guruswami_et_al:LIPIcs.CCC.2024.27,
  author =	{Guruswami, Venkatesan and Ren, Xuandi and Sandeep, Sai},
  title =	{{Baby PIH: Parameterized Inapproximability of Min CSP}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.27},
  URN =		{urn:nbn:de:0030-drops-204237},
  doi =		{10.4230/LIPIcs.CCC.2024.27},
  annote =	{Keywords: Parameterized Inapproximability Hypothesis, Constraint Satisfaction Problems}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.90
On Lower Bounds of Approximating Parameterized k-Clique

Authors: Bingkai Lin, Xuandi Ren, Yican Sun, and Xiuhan Wang

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Given a simple graph G and an integer k, the goal of the k-Clique problem is to decide if G contains a complete subgraph of size k. We say an algorithm approximates k-Clique within a factor g(k) if it can find a clique of size at least k/g(k) when G is guaranteed to have a k-clique. Recently, it was shown that approximating k-Clique within a constant factor is W[1]-hard [Bingkai Lin, 2021]. We study the approximation of k-Clique under the Exponential Time Hypothesis (ETH). The reduction of [Bingkai Lin, 2021] already implies an n^Ω(√[6]{log k})-time lower bound under ETH. We improve this lower bound to n^Ω(log k). Using the gap-amplification technique by expander graphs, we also prove that there is no k^o(1) factor FPT-approximation algorithm for k-Clique under ETH. We also suggest a new way to prove the Parameterized Inapproximability Hypothesis (PIH) under ETH. We show that if there is no n^O(k/(log k))-time algorithm to approximate k-Clique within a constant factor, then PIH is true.
Cite as

Bingkai Lin, Xuandi Ren, Yican Sun, and Xiuhan Wang. On Lower Bounds of Approximating Parameterized k-Clique. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 90:1-90:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lin_et_al:LIPIcs.ICALP.2022.90,
  author =	{Lin, Bingkai and Ren, Xuandi and Sun, Yican and Wang, Xiuhan},
  title =	{{On Lower Bounds of Approximating Parameterized k-Clique}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{90:1--90:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.90},
  URN =		{urn:nbn:de:0030-drops-164317},
  doi =		{10.4230/LIPIcs.ICALP.2022.90},
  annote =	{Keywords: parameterized complexity, k-clique, hardness of approximation}
}
  • Refine by Type
  • 8 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 5 2025
  • 2 2024
  • 1 2022

  • Refine by Author
  • 2 Lin, Bingkai
  • 2 Ren, Xuandi
  • 1 Can Esmer, Barış
  • 1 Chen, Yijia
  • 1 Dabrowski, Konrad K.
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Problems, reductions and completeness
  • 4 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Error-correcting codes
  • 1 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 2 Parameterized Inapproximability Hypothesis
  • 2 parameterized complexity
  • 1 Average Baby PIH
  • 1 Constraint Satisfaction Problem
  • 1 Constraint Satisfaction Problems
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact