12 Search Results for "Lin, Bingkai"

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.47
Hardness and Fixed Parameter Tractability for Pinwheel Scheduling Problems

Authors: Yusuke Kobayashi and Bingkai Lin

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
In the Pinwheel Packing problem, we are given a set of recurring tasks, each associated with a positive integer a_i for task i. The objective is to select one task to perform each day such that every task i is performed at least once within every a_i consecutive days. The exact computational complexity of this problem, where ∑ 1/a_i = 1, has remained an open question for more than 30 years; in particular, it is still unknown whether the problem is NP-hard. The first contribution of this paper is to show that Pinwheel Packing cannot be solved in polynomial time under a standard complexity assumption, improving upon the hardness result shown by Jacobs and Longo. Additionally, we present fixed-parameter algorithms for variants of Pinwheel Packing, parameterized by the number of tasks.
Cite as

Yusuke Kobayashi and Bingkai Lin. Hardness and Fixed Parameter Tractability for Pinwheel Scheduling Problems. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.ISAAC.2025.47,
  author =	{Kobayashi, Yusuke and Lin, Bingkai},
  title =	{{Hardness and Fixed Parameter Tractability for Pinwheel Scheduling Problems}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{47:1--47:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.47},
  URN =		{urn:nbn:de:0030-drops-249558},
  doi =		{10.4230/LIPIcs.ISAAC.2025.47},
  annote =	{Keywords: Pinwheel Scheduling, Polynomial-time Solvability, Packing and Covering, Fixed Parameter Algorithms}
}
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
DOI: 10.4230/LIPIcs.MFCS.2025.65
Parameterized Spanning Tree Congestion

Authors: Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, and Daniel Vaz

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
In this paper we study the Spanning Tree Congestion problem, where we are given an undirected graph G = (V,E) and are asked to find a spanning tree T of minimum maximum congestion. Here, the congestion of an edge e ∈ T is the number of edges uv ∈ E such that the (unique) path from u to v in T traverses e. We consider this well-studied NP-hard problem from the point of view of (structural) parameterized complexity and obtain the following results: - We resolve a natural open problem by showing that Spanning Tree Congestion is not FPT parameterized by treewidth (under standard assumptions). More strongly, we present a generic reduction which applies to (almost) any parameter of the form "vertex-deletion distance to class 𝒞", thus obtaining W[1]-hardness for more restricted parameters, including tree-depth plus feedback vertex set, or incomparable to treewidth, such as twin cover. Via a slight tweak of the same reduction we also show that the problem is NP-complete on graphs of modular-width 4. - Even though it is known that Spanning Tree Congestion remains NP-hard on instances with only one vertex of unbounded degree, it is currently open whether the problem remains hard on bounded-degree graphs. We resolve this question by showing NP-hardness on graphs of maximum degree 8. - Complementing the problem’s W[1]-hardness for treewidth, we formulate an algorithm that runs in time roughly {(k+w)}^{𝒪(w)}, where k is the desired congestion and w the treewidth, improving a previous argument for parameter k+w that was based on Courcelle’s theorem. This explicit algorithm pays off in two ways: it allows us to obtain an FPT approximation scheme for parameter treewidth, that is, a (1+ε)-approximation running in time roughly {(w/ε)}^{𝒪(w)}; and it leads to an exact FPT algorithm for parameter clique-width+k via a Win/Win argument. - Finally, motivated by the problem’s hardness for most standard structural parameters, we present FPT algorithms for several more restricted cases, namely, for the parameters vertex-deletion distance to clique; vertex integrity; and feedback edge set, in the latter case also achieving a single-exponential running time dependence on the parameter.
Cite as

Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, and Daniel Vaz. Parameterized Spanning Tree Congestion. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 65:1-65:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lampis_et_al:LIPIcs.MFCS.2025.65,
  author =	{Lampis, Michael and Mitsou, Valia and Nemery, Edouard and Otachi, Yota and Vasilakis, Manolis and Vaz, Daniel},
  title =	{{Parameterized Spanning Tree Congestion}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{65:1--65:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.65},
  URN =		{urn:nbn:de:0030-drops-241724},
  doi =		{10.4230/LIPIcs.MFCS.2025.65},
  annote =	{Keywords: Parameterized Complexity, Treewidth, Graph Width Parameters}
}
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.107
Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH

Authors: Shuangle Li, Bingkai Lin, and Yuwei Liu

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In this paper we present a new gap-creating randomized self-reduction for the parameterized Maximum Likelihood Decoding problem over 𝔽_p (k-MLD_p). The reduction takes a k-MLD_p instance with k⋅ n d-dimensional vectors as input, runs in O(d2^{O(k)}n^{1.01}) time for some computable function f, outputs a (3/2-ε)-Gap-k'-MLD_p instance for any ε > 0, where k' = O(k²log k). Using this reduction, we show that assuming the randomized Exponential Time Hypothesis (ETH), no algorithms can approximate k-MLD_p (and therefore its dual problem k-NCP_p) within factor (3/2-ε) in f(k)⋅ n^{o(√{k/log k})} time for any ε > 0. We then use reduction by Bhattacharyya, Ghoshal, Karthik and Manurangsi (ICALP 2018) to amplify the (3/2-ε)-gap to any constant. As a result, we show that assuming ETH, no algorithms can approximate k-NCP_p and k-MDP_p within γ-factor in f(k)⋅ n^{o(k^{ε_γ})} time for some constant ε_γ > 0. Combining with the gap-preserving reduction by Bennett, Cheraghchi, Guruswami and Ribeiro (STOC 2023), we also obtain similar lower bounds for k-MDP_p, k-CVP_p and k-SVP_p. These results improve upon the previous f(k)⋅ n^{Ω(poly log k)} lower bounds for these problems under ETH using reductions by Bhattacharyya et al. (J.ACM 2021) and Bennett et al. (STOC 2023).
Cite as

Shuangle Li, Bingkai Lin, and Yuwei Liu. Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 107:1-107:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ICALP.2024.107,
  author =	{Li, Shuangle and Lin, Bingkai and Liu, Yuwei},
  title =	{{Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{107:1--107:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.107},
  URN =		{urn:nbn:de:0030-drops-202500},
  doi =		{10.4230/LIPIcs.ICALP.2024.107},
  annote =	{Keywords: Nearest Codeword Problem, Hardness of Approximations, Fine-grained Complexity, Parameterized Complexity, Minimum Distance Problem, Shortest Vector Problem}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.19
FPT Approximation Using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set

Authors: Huairui Chu and Bingkai Lin

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
Treewidth is a useful tool in designing graph algorithms. Although many NP-hard graph problems can be solved in linear time when the input graphs have small treewidth, there are problems which remain hard on graphs of bounded treewidth. In this paper, we consider three vertex selection problems that are W[1]-hard when parameterized by the treewidth of the input graph, namely the capacitated vertex cover problem, the target set selection problem and the vector dominating set problem. We provide two new methods to obtain FPT approximation algorithms for these problems. For the capacitated vertex cover problem and the vector dominating set problem, we obtain (1+o(1))-approximation FPT algorithms. For the target set selection problem, we give an FPT algorithm providing a tradeoff between its running time and the approximation ratio.
Cite as

Huairui Chu and Bingkai Lin. FPT Approximation Using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chu_et_al:LIPIcs.ISAAC.2023.19,
  author =	{Chu, Huairui and Lin, Bingkai},
  title =	{{FPT Approximation Using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{19:1--19:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.19},
  URN =		{urn:nbn:de:0030-drops-193216},
  doi =		{10.4230/LIPIcs.ISAAC.2023.19},
  annote =	{Keywords: FPT approximation algorithm, Treewidth, Capacitated vertex cover, Target set selection, Vector dominating set}
}
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}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.81
A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem

Authors: Bingkai Lin

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Given an n-vertex bipartite graph I=(S,U,E), the goal of set cover problem is to find a minimum sized subset of S such that every vertex in U is adjacent to some vertex of this subset. It is NP-hard to approximate set cover to within a (1-o(1))ln n factor [I. Dinur and D. Steurer, 2014]. If we use the size of the optimum solution k as the parameter, then it can be solved in n^{k+o(1)} time [Eisenbrand and Grandoni, 2004]. A natural question is: can we approximate set cover to within an o(ln n) factor in n^{k-epsilon} time? In a recent breakthrough result[Karthik et al., 2018], Karthik, Laekhanukit and Manurangsi showed that assuming the Strong Exponential Time Hypothesis (SETH), for any computable function f, no f(k)* n^{k-epsilon}-time algorithm can approximate set cover to a factor below (log n)^{1/poly(k,e(epsilon))} for some function e. This paper presents a simple gap-producing reduction which, given a set cover instance I=(S,U,E) and two integers k<h <=(1-o(1))sqrt[k]{log |S|/log log |S|}, outputs a new set cover instance I'=(S,U',E') with |U'|=|U|^{h^k}|S|^{O(1)} in |U|^{h^k}* |S|^{O(1)} time such that - if I has a k-sized solution, then so does I'; - if I has no k-sized solution, then every solution of I' must contain at least h vertices. Setting h=(1-o(1))sqrt[k]{log |S|/log log |S|}, we show that assuming SETH, for any computable function f, no f(k)* n^{k-epsilon}-time algorithm can distinguish between a set cover instance with k-sized solution and one whose minimum solution size is at least (1-o(1))* sqrt[k]((log n)/(log log n)). This improves the result in [Karthik et al., 2018].
Cite as

Bingkai Lin. A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 81:1-81:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{lin:LIPIcs.ICALP.2019.81,
  author =	{Lin, Bingkai},
  title =	{{A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{81:1--81:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.81},
  URN =		{urn:nbn:de:0030-drops-106573},
  doi =		{10.4230/LIPIcs.ICALP.2019.81},
  annote =	{Keywords: set cover, FPT inapproximability, gap-producing reduction, (n, k)-universal set}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.84
Short Proofs Are Hard to Find

Authors: Ian Mertz, Toniann Pitassi, and Yuanhao Wei

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We obtain a streamlined proof of an important result by Alekhnovich and Razborov [Michael Alekhnovich and Alexander A. Razborov, 2008], showing that it is hard to automatize both tree-like and general Resolution. Under a different assumption than [Michael Alekhnovich and Alexander A. Razborov, 2008], our simplified proof gives improved bounds: we show under ETH that these proof systems are not automatizable in time n^f(n), whenever f(n) = o(log^{1/7 - epsilon} log n) for any epsilon > 0. Previously non-automatizability was only known for f(n) = O(1). Our proof also extends fairly straightforwardly to prove similar hardness results for PCR and Res(r).
Cite as

Ian Mertz, Toniann Pitassi, and Yuanhao Wei. Short Proofs Are Hard to Find. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 84:1-84:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mertz_et_al:LIPIcs.ICALP.2019.84,
  author =	{Mertz, Ian and Pitassi, Toniann and Wei, Yuanhao},
  title =	{{Short Proofs Are Hard to Find}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{84:1--84:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.84},
  URN =		{urn:nbn:de:0030-drops-106605},
  doi =		{10.4230/LIPIcs.ICALP.2019.84},
  annote =	{Keywords: automatizability, Resolution, SAT solvers, proof complexity}
}
  • Refine by Type
  • 12 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 6 2025
  • 2 2024
  • 1 2023
  • 1 2022
  • 2 2019

  • Refine by Author
  • 6 Lin, Bingkai
  • 2 Li, Shuangle
  • 2 Liu, Yuwei
  • 1 Can Esmer, Barış
  • 1 Chen, Yijia
  • Show More...

  • Refine by Series/Journal
  • 12 LIPIcs

  • Refine by Classification
  • 6 Theory of computation → Parameterized complexity and exact algorithms
  • 6 Theory of computation → Problems, reductions and completeness
  • 1 Hardware → Theorem proving and SAT solving
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Computational complexity and cryptography
  • Show More...

  • Refine by Keyword
  • 2 Parameterized Complexity
  • 2 Treewidth
  • 2 parameterized complexity
  • 1 (n
  • 1 Average Baby PIH
  • 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