skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
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.  more » « less
Award ID(s):
2236669 2313372
PAR ID:
10574278
Author(s) / Creator(s):
; ;
Editor(s):
Bonnet, Édouard; Rzążewski, Paweł
Publisher / Repository:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Date Published:
Volume:
321
ISSN:
1868-8969
ISBN:
978-3-95977-353-9
Page Range / eLocation ID:
321-321
Subject(s) / Keyword(s):
Parameterized complexity Hardness of Approximation Parameterized Inapproximability Hypothesis max coverage k-median Theory of computation → Problems, reductions and completeness Theory of computation → W hierarchy
Format(s):
Medium: X Size: 18 pages; 903540 bytes Other: application/pdf
Size(s):
18 pages 903540 bytes
Right(s):
Creative Commons Attribution 4.0 International license; info:eu-repo/semantics/openAccess
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Santhanam, Rahul (Ed.)
    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. 
    more » « less
  2. ; (, ACM Transactions on Algorithms)
    The Unique Games Conjecture has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect completeness inherent in the Unique Games Conjecture. This work is motivated by the pursuit of a better understanding of the approximability of perfectly satisfiable instances of CSPs. We prove that an “almost Unique” version of Label Cover can be approximated within a constant factor on satisfiable instances. Our main conceptual contribution is the formulation of a (hypergraph) version of Label Cover that we call V Label Cover . Assuming a conjecture concerning the inapproximability of V Label Cover on perfectly satisfiable instances, we prove the following implications: • There is an absolute constant c 0 such that for k ≥ 3, given a satisfiable instance of Boolean k -CSP, it is hard to find an assignment satisfying more than c 0 k 2 /2 k fraction of the constraints. • Given a k -uniform hypergraph, k ≥ 2, for all ε > 0, it is hard to tell if it is q -strongly colorable or has no independent set with an ε fraction of vertices, where q =⌈ k +√ k -1/2⌉. • Given a k -uniform hypergraph, k ≥ 3, for all ε > 0, it is hard to tell if it is ( k -1)-rainbow colorable or has no independent set with an ε fraction of vertices. 
    more » « less
  3. ; ; ; ; ; (, Journal of information processing)
    We prove the computational intractability of rotating and placing n square tiles into a 1 × n array such that adjacent tiles are compatible—either equal edge colors, as in edge-matching puzzles, or matching tab/pocket shapes, as in jigsaw puzzles. Beyond basic NP-hardness, we prove that it is NP-hard even to approximately maximize the number of placed tiles (allowing blanks), while satisfying the compatibility constraint between nonblank tiles, within a factor of 0.9999999702. (On the other hand, there is an easy (1/2)-approximation.) This is the first (correct) proof of inapproximability for edge-matching and jigsaw puzzles. Along the way, we prove NP-hardness of distinguishing, for a directed graph on n nodes, between having a Hamiltonian path (length n − 1) and having at most 0.999999284 (n − 1) edges that form a vertex-disjoint union of paths. We use this gap hardness and gap-preserving reductions to establish similar gap hardness for 1 × n jigsaw and edge-matching puzzles. 
    more » « less
  4. ; ; ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Leroux, Jérôme; Lombardy, Sylvain; Peleg, David (Ed.)
    Feedback Vertex Set (FVS) is one of the most studied vertex deletion problems in the field of graph algorithms. In the decision version of the problem, given a graph G and an integer k, the question is whether there exists a set S of at most k vertices in G such that G-S is acyclic. It is one of the first few problems which were shown to be NP-complete, and has been extensively studied from the viewpoint of approximation and parameterized algorithms. The best-known polynomial time approximation algorithm for FVS is a 2-factor approximation, while the best known deterministic and randomized FPT algorithms run in time 𝒪^*(3.460^k) and 𝒪^*(2.7^k) respectively. In this paper, we contribute to the newly established area of parameterized approximation, by studying FVS in this paradigm. In particular, we combine the approaches of parameterized and approximation algorithms for the study of FVS, and achieve an approximation guarantee with a factor better than 2 in randomized FPT running time, that improves over the best known parameterized algorithm for FVS. We give three simple randomized (1+ε) approximation algorithms for FVS, running in times 𝒪^*(2^{εk}⋅ 2.7^{(1-ε)k}), 𝒪^*(({(4/(1+ε))^{(1+ε)}}⋅{(ε/3)^ε})^k), and 𝒪^*(4^{(1-ε)k}) respectively for every ε ∈ (0,1). Combining these three algorithms, we obtain a factor (1+ε) approximation algorithm for FVS, which has better running time than the best-known (randomized) FPT algorithm for every ε ∈ (0, 1). This is the first attempt to look at a parameterized approximation of FVS to the best of our knowledge. Our algorithms are very simple, and they rely on some well-known reduction rules used for arriving at FPT algorithms for FVS. 
    more » « less
  5. ; ; ; ; (, {STOC} '22: 54th Annual {ACM} {SIGACT} Symposium on Theory of Computing)
    Leonardi, Stefano; Gupta, Anupam (Ed.)
    We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on n variables taking values in {0,…,q−1}, we prove that improving over the trivial approximability by a factor of q requires Ω(n) space even on instances with O(n) constraints. We also identify a broad subclass of problems for which any improvement over the trivial approximability requires Ω(n) space. The key technical core is an optimal, q−(k−1)-inapproximability for the Max k-LIN-mod q problem, which is the Max CSP problem where every constraint is given by a system of k−1 linear equations mod q over k variables. Our work builds on and extends the breakthrough work of Kapralov and Krachun (Proc. STOC 2019) who showed a linear lower bound on any non-trivial approximation of the MaxCut problem in graphs. MaxCut corresponds roughly to the case of Max k-LIN-mod q with k=q=2. For general CSPs in the streaming setting, prior results only yielded Ω(√n) space bounds. In particular no linear space lower bound was known for an approximation factor less than 1/2 for any CSP. Extending the work of Kapralov and Krachun to Max k-LIN-mod q to k>2 and q>2 (while getting optimal hardness results) is the main technical contribution of this work. Each one of these extensions provides non-trivial technical challenges that we overcome in this work. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email