Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
Pages 24 - 35
Abstract
The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the number of variables, from one where every assignment fails to satisfy an ε fraction of constraints for some absolute constant ε > 0. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under Gap-ETH, a very strong assumption with an inherent gap. In this work, we prove PIH under the Exponential Time Hypothesis (ETH). This is the first proof of PIH from a gap-free assumption. Our proof is self-contained and elementary. We identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a “parallel PCP of proximity” based on the Walsh-Hadamard code.
References
[1]
Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase. 2023. Parameterized Approximation Schemes for Clustering with General Norm Objectives. FOCS.
[2]
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. 2020. Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms. SIAM J. Comput., 49, 4 (2020), https://doi.org/10.1137/18M1171321
[3]
Benny Applebaum. 2017. Exponentially-hard gap-csp and local PRG via local hardcore functions. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 836–847.
[4]
Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk. 1997. The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations. J. Comput. Syst. Sci., 54, 2 (1997), 317–331. https://doi.org/10.1006/JCSS.1997.1472
[5]
Sanjeev Arora and Boaz Barak. 2009. Computational Complexity - A Modern Approach. Cambridge University Press. isbn:978-0-521-42426-4 http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264
[6]
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. 1998. Proof Verification and the Hardness of Approximation Problems. J. ACM, 45, 3 (1998), 501–555. https://doi.org/10.1145/278298.278306
[7]
Sanjeev Arora and Shmuel Safra. 1998. Probabilistic Checking of Proofs: A New Characterization of NP. J. ACM, 45, 1 (1998), 70–122. https://doi.org/10.1145/273865.273901
[8]
Mihir Bellare, Oded Goldreich, and Madhu Sudan. 1998. Free Bits, PCPs, and Nonapproximability-Towards Tight Results. SIAM J. Comput., 27, 3 (1998), 804–915.
[9]
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. 2006. Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM J. Comput., 36, 4 (2006), 889–974. https://doi.org/10.1137/S0097539705446810
[10]
Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, and João Ribeiro. 2023. Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all ℓ _p Norms. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, Barna Saha and Rocco A. Servedio (Eds.). ACM, 553–566. https://doi.org/10.1145/3564246.3585214
[11]
Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, and Dániel Marx. 2021. Parameterized Intractability of Even Set and Shortest Vector Problem. J. ACM, 68, 3 (2021), 16:1–16:40. https://doi.org/10.1145/3444942
[12]
Manuel Blum, Michael Luby, and Ronitt Rubinfeld. 1993. Self-testing/correcting with applications to numerical problems. J. Comput. System Sci., 47, 3 (1993), 549–595.
[13]
Boris Bukh, Karthik C. S., and Bhargav Narayanan. 2021. Applications of Random Algebraic Constructions to Hardness of Approximation. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022. IEEE, 237–244. https://doi.org/10.1109/FOCS52979.2021.00032
[14]
Jaroslaw Byrka, Thomas W. Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. 2017. An Improved Approximation for k-Median and Positive Correlation in Budgeted Optimization. ACM Trans. Algorithms, 13, 2 (2017), 23:1–23:31. https://doi.org/10.1145/2981561
[15]
Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. 2009. The Complexity of Satisfiability of Small Depth Circuits. In Parameterized and Exact Computation, Jianer Chen and Fedor V. Fomin (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 75–85. isbn:978-3-642-11269-0
[16]
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. 2017. From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, Chris Umans (Ed.). IEEE Computer Society, 743–754. https://doi.org/10.1109/FOCS.2017.74
[17]
Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys. 2002. A Constant-Factor Approximation Algorithm for the k-Median Problem. J. Comput. Syst. Sci., 65, 1 (2002), 129–149. https://doi.org/10.1006/jcss.2002.1882
[18]
Yijia Chen, Yi Feng, Bundit Laekhanukit, and Yanlin Liu. 2023. Simple Combinatorial Construction of the k^o(1)-Lower Bound for Approximating the Parameterized k-Clique. CoRR, abs/2304.07516 (2023), https://doi.org/10.48550/arXiv.2304.07516 arXiv:2304.07516.
[19]
Yijia Chen and Martin Grohe. 2007. An isomorphism between subexponential and parameterized complexity theory. SIAM J. Comput., 37, 4 (2007), 1228–1258.
[20]
Yijia Chen and Bingkai Lin. 2019. The Constant Inapproximability of the Parameterized Dominating Set Problem. SIAM J. Comput., 48, 2 (2019), 513–533. https://doi.org/10.1137/17M1127211
[21]
Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. 2019. Tight FPT Approximations for k-Median and k-Means. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.) (LIPIcs, Vol. 132). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 42:1–42:14. https://doi.org/10.4230/LIPIcs.ICALP.2019.42
[22]
Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Ken-ichi Kawarabayashi. 2005. Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings. IEEE Computer Society, 637–646. https://doi.org/10.1109/SFCS.2005.14
[23]
Irit Dinur. 2007. The PCP theorem by gap amplification. J. ACM, 54, 3 (2007), 12.
[24]
Irit Dinur. 2016. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electron. Colloquium Comput. Complex., 23 (2016), 128.
[25]
Irit Dinur, Elena Grigorescu, Swastik Kopparty, and Madhu Sudan. 2008. Decodability of group homomorphisms beyond the Johnson bound. In Proceedings of the fortieth annual ACM symposium on Theory of computing. 275–284.
[26]
Irit Dinur and Pasin Manurangsi. 2018. ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, Anna R. Karlin (Ed.) (LIPIcs, Vol. 94). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 36:1–36:20. https://doi.org/10.4230/LIPICS.ITCS.2018.36
[27]
Irit Dinur and Omer Reingold. 2006. Assignment testers: Towards a combinatorial proof of the PCP theorem. SIAM J. Comput., 36, 4 (2006), 975–1024.
[28]
Rodney G. Downey and Michael R. Fellows. 1995. Fixed-Parameter Tractability and Completeness I: Basic Results. SIAM J. Comput., 24, 4 (1995), 873–921. https://doi.org/10.1137/S0097539792228228
[29]
Rodney G Downey and Michael R Fellows. 1995. Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science, 141, 1-2 (1995), 109–131.
[30]
Uriel Feige. 1998. A threshold of olnn for approximating set cover. Journal of the ACM (JACM), 45, 4 (1998), 634–652.
[31]
Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. 1996. Interactive proofs and the hardness of approximating cliques. Journal of the ACM (JACM), 43, 2 (1996), 268–292.
[32]
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, and Pasin Manurangsi. 2020. A survey on approximation in parameterized complexity: Hardness and algorithms. Algorithms, 13, 6 (2020), 146.
[33]
Michael R Fellows. 2003. Blow-ups, win/win’s, and crown rules: Some new directions in FPT. In Graph-Theoretic Concepts in Computer Science: 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers 29. 1–12.
[34]
Jörg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer.
[35]
Jörg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer. isbn:978-3-540-29952-3 https://doi.org/10.1007/3-540-29953-X
[36]
Parikshit Gopalan, Venkatesan Guruswami, and Prasad Raghavendra. 2011. List Decoding Tensor Products and Interleaved Codes. SIAM J. Comput., 40, 5 (2011), 1432–1462.
[37]
Anupam Gupta, Euiwoong Lee, and Jason Li. 2018. Faster exact and approximate algorithms for k-cut. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). 113–123.
[38]
Anupam Gupta, Euiwoong Lee, and Jason Li. 2018. An FPT algorithm beating 2-approximation for k-cut. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. 2821–2837.
[39]
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, and Kewen Wu. 2023. Parameterized Inapproximability Hypothesis under ETH. arxiv:2311.16587.
[40]
Venkatesan Guruswami, Jakub Opršal, and Sai Sandeep. 2020. Revisiting Alphabet Reduction in Dinur’s PCP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), Jarosł aw Byrka and Raghu Meka (Eds.) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 176). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany. 34:1–34:14. isbn:978-3-95977-164-1 issn:1868-8969 https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.34
[41]
Venkatesan Guruswami, Xuandi Ren, and Sai Sandeep. 2023. Baby PIH: Parameterized Inapproximability of Min CSP. arXiv preprint arXiv:2310.16344.
[42]
Russell Impagliazzo and Ramamohan Paturi. 2001. On the Complexity of k-SAT. J. Comput. System Sci., 62 (2001), 367–375.
[43]
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which problems have strongly exponential complexity? J. Comput. System Sci., 63, 4 (2001), 512–530.
[44]
Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. 2004. A local search approximation algorithm for k-means clustering. Comput. Geom., 28, 2-3 (2004), 89–112. https://doi.org/10.1016/j.comgeo.2004.03.003
[45]
CS Karthik and Subhash Khot. 2022. Almost polynomial factor inapproximability for parameterized k-clique. In 37th Computational Complexity Conference (CCC 2022). 234.
[46]
Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi. 2019. On the Parameterized Complexity of Approximating Dominating Set. J. ACM, 66, 5 (2019), 33:1–33:38. https://doi.org/10.1145/3325116
[47]
Karthik C. S. and Inbal Livni Navon. 2021. On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes. In 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, Hung Viet Le and Valerie King (Eds.). SIAM, 210–223. https://doi.org/10.1137/1.9781611976496.24
[48]
Ken-ichi Kawarabayashi and Bingkai Lin. 2020. A nearly 5/3-approximation FPT Algorithm for Min-k-Cut. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. 990–999.
[49]
Euiwoong Lee. 2019. Partitioning a graph into small pieces with applications to path transversal. Math. Program., 177, 1-2 (2019), 1–19. https://doi.org/10.1007/s10107-018-1255-7
[50]
Shi Li and Ola Svensson. 2016. Approximating k-Median via Pseudo-Approximation. SIAM J. Comput., 45, 2 (2016), 530–547. https://doi.org/10.1137/130938645
[51]
Bingkai Lin. 2018. The parameterized complexity of the k-biclique problem. Journal of the ACM (JACM), 65, 5 (2018), 1–23.
[52]
Bingkai Lin. 2019. A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.) (LIPIcs, Vol. 132). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 81:1–81:15. https://doi.org/10.4230/LIPIcs.ICALP.2019.81
[53]
Bingkai Lin. 2021. Constant approximating k-clique is W[1]-hard. In STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, Samir Khuller and Virginia Vassilevska Williams (Eds.). ACM, 1749–1756. https://doi.org/10.1145/3406325.3451016
[54]
Bingkai Lin, Xuandi Ren, Yican Sun, and Xiuhan Wang. 2022. On Lower Bounds of Approximating Parameterized k-Clique. In 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff (Eds.) (LIPIcs, Vol. 229). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 90:1–90:18. https://doi.org/10.4230/LIPIcs.ICALP.2022.90
[55]
Bingkai Lin, Xuandi Ren, Yican Sun, and Xiuhan Wang. 2023. Constant Approximating Parameterized k-SETCOVER is W[2]-hard. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, Nikhil Bansal and Viswanath Nagarajan (Eds.). SIAM, 3305–3316. https://doi.org/10.1137/1.9781611977554.ch126
[56]
Bingkai Lin, Xuandi Ren, Yican Sun, and Xiuhan Wang. 2023. Improved Hardness of Approximating k-Clique under ETH. FOCS.
[57]
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. 2020. Parameterized Complexity and Approximability of Directed Odd Cycle Transversal. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, Shuchi Chawla (Ed.). SIAM, 2181–2200.
[58]
Daniel Lokshtanov, Saket Saurabh, and Vaishali Surianarayanan. 2020. A Parameterized Approximation Scheme for Min k-Cut. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, Sandy Irani (Ed.). IEEE, 798–809.
[59]
Pasin Manurangsi. 2019. A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation. In 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8-9, 2019, San Diego, CA, USA, Jeremy T. Fineman and Michael Mitzenmacher (Eds.) (OASIcs, Vol. 69). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 15:1–15:21. https://doi.org/10.4230/OASIcs.SOSA.2019.15
[60]
Pasin Manurangsi. 2020. Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. 62–81.
[61]
Dániel Marx. 2008. Parameterized Complexity and Approximation Algorithms. Comput. J., 51, 1 (2008), 60–78. https://doi.org/10.1093/comjnl/bxm048
[62]
Naoto Ohsaka. 2022. On the Parameterized Intractability of Determinant Maximization. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022).
[63]
Piotr Skowron and Piotr Faliszewski. 2017. Chamberlin-Courant Rule with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time. J. Artif. Intell. Res., 60 (2017), 687–716. https://doi.org/10.1613/jair.5628
[64]
C. Tovey. 1984. A simplified NP-complete satisfiability problem. Discret. Appl. Math., 8 (1984), 85–89.
[65]
Andreas Wiese. 2018. Fixed-Parameter Approximation Schemes for Weighted Flowtime. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA, Eric Blais, Klaus Jansen, José D. P. Rolim, and David Steurer (Eds.) (LIPIcs, Vol. 116). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 28:1–28:19. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.28
[66]
Michał Wł odarczyk. 2020. Parameterized Inapproximability for Steiner Orientation by Gap Amplification. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).
Index Terms
- Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
Recommendations
The exponential time hypothesis and the parameterized clique problem
IPEC'12: Proceedings of the 7th international conference on Parameterized and Exact ComputationIn parameterized complexity there are three natural definitions of fixed-parameter tractability called strongly uniform, weakly uniform and nonuniform fpt. Similarly, there are three notions of subexponential time, yielding three flavours of the ...
On parameterized exponential time complexity
In this paper we study the notion of parameterized exponential time complexity. We show that a parameterized problem can be solved in parameterized 2^o^(^f^(^k^)^)p(n) time if and only if it is solvable in time O(2^@d^f^(^k^)q(n)) for any constant @d>0, ...
Complexity of SAT problems, clone theory and the exponential time hypothesis
SODA '13: Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithmsThe construction of exact exponential-time algorithms for NP-complete problems has for some time been a very active research area. Unfortunately, there is a lack of general methods for studying and comparing the time complexity of algorithms for such ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2024
2049 pages
ISBN:9798400703836
DOI:10.1145/3618260
- General Chairs:
- Bojan Mohar,
- Igor Shinkar,
- Program Chair:
- Ryan O'Donnell
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 June 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- NSF (National Science Foundation)
- Simons Institute for the Theory of Computing, University of California Berkeley
- Alfred P. Sloan Foundation
Conference
STOC '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 403Total Downloads
- Downloads (Last 12 months)403
- Downloads (Last 6 weeks)112
Reflects downloads up to 22 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in