Document Open Access Logo

Refuting FPT Algorithms for Some Parameterized Problems Under Gap-ETH

Authors Akanksha Agrawal , Ravi Kiran Allumalla, Varun Teja Dhanekula

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.2.pdf
  • Filesize: 0.8 MB
  • 12 pages

Document Identifiers

Author Details

Akanksha Agrawal
  • Indian Institute of Technology Madras, Chennai, India
Ravi Kiran Allumalla
  • Indian Institute of Technology Madras, Chennai, India
Varun Teja Dhanekula
  • Indian Institute of Technology Madras, Chennai, India

Cite AsGet BibTex

Akanksha Agrawal, Ravi Kiran Allumalla, and Varun Teja Dhanekula. Refuting FPT Algorithms for Some Parameterized Problems Under Gap-ETH. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.IPEC.2021.2

Abstract

In this article we study a well-known problem, called Bipartite Token Jumping and not-so-well known problem(s), which we call, Half (Induced-) Subgraph, and show that under Gap-ETH, these problems do not admit FPT algorithms. The problem Bipartite Token Jumping takes as input a bipartite graph G and two independent sets S,T in G, where |S| = |T| = k, and the objective is to test if there is a sequence of exactly k-sized independent sets ⟨ I₀, I₁,⋯, I_𝓁 ⟩ in G, such that: i) I₀ = S and I_𝓁 = T, and ii) for every j ∈ [𝓁], I_{j} is obtained from I_{j-1} by replacing a vertex in I_{j-1} by a vertex in V(G) ⧵ I_{j-1}. We show that, assuming Gap-ETH, Bipartite Token Jumping does not admit an FPT algorithm. We note that this result resolves one of the (two) open problems posed by Bartier et al. (ISAAC 2020), under Gap-ETH. Most of the known reductions related to Token Jumping exploit the property given by triangles (i.e., C₃s), to obtain the correctness, and our results refutes FPT algorithm for Bipartite Token Jumping, where the input graph cannot have any triangles. For an integer k ∈ ℕ, the half graph S_{k,k} is the graph with vertex set V(S_{k,k}) = A_k ∪ B_k, where A_k = {a₁,a₂,⋯, a_k} and B_k = {b₁,b₂,⋯, b_k}, and for i,j ∈ [k], {a_i,b_j} ∈ E(T_{k,k}) if and only if j ≥ i. We also study the Half (Induced-)Subgraph problem where we are given a graph G and an integer k, and the goal is to check if G contains S_{k,k} as an (induced-)subgraph. Again under Gap-ETH, we show that Half (Induced-)Subgraph does not admit an FPT algorithm, even when the input is a bipartite graph. We believe that the above problem (and its negative) result maybe of independent interest and could be useful obtaining new fixed parameter intractability results. There are very few reductions known in the literature which refute FPT algorithms for a parameterized problem based on assumptions like Gap-ETH. Thus our technique (and simple reductions) exhibits the potential of such conjectures in obtaining new (and possibly easier) proofs for refuting FPT algorithms for parameterized problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Token Jumping
  • Bipartite Graphs
  • Fixed Parameter Intractability
  • Half Graphs
  • Gap-Exponential Time Hypothesis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM, 42(4):844-856, 1995. Google Scholar
  2. Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, and Amer E. Mouawad. On girth and the parameterized complexity of token sliding and token jumping. In 31st International Symposium on Algorithms and Computation (ISAAC), volume 181, pages 44:1-44:17, 2020. Google Scholar
  3. Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, and Amer E. Mouawad. On girth and the parameterized complexity of token sliding and token jumping. Algorithmica, 83(9):2914-2951, 2021. Google Scholar
  4. Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., and Pasin Manurangsi. Parameterized intractability of even set and shortest vector problem from gap-eth. In 45th International Colloquium on Automata, Languages, and Programming (ICALP), volume 107, pages 17:1-17:15, 2018. Google Scholar
  5. Marthe Bonamy and Nicolas Bousquet. Token sliding on chordal graphs. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 127-139. Springer, 2017. Google Scholar
  6. Nicolas Bousquet, Arnaud Mary, and Aline Parreau. Token jumping in minor-closed classes. In International Symposium on Fundamentals of Computation Theory, pages 136-149. Springer, 2017. Google Scholar
  7. Andreas Brandstädt, Peter L Hammer, Vadim V Lozin, et al. Bisplit graphs. Discrete Mathematics, 299(1-3):11-32, 2005. Google Scholar
  8. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From gap-eth to fpt-inapproximability: Clique, dominating set, and more. In 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 743-754, 2017. Google Scholar
  9. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From gap-exponential time hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more. SIAM Journal on Computing, 49(4):772-810, 2020. Google Scholar
  10. Stephen A Cook. The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing (STOC), pages 151-158, 1971. Google Scholar
  11. Erik D Demaine, Martin L Demaine, Eli Fox-Epstein, Duc A Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, and Takeshi Yamada. Polynomial-time algorithm for sliding tokens on trees. In International Symposium on Algorithms and Computation, pages 389-400. Springer, 2014. Google Scholar
  12. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  13. Irit Dinur. Mildly exponential reduction from gap 3sat to polynomial-gap label-cover. ECCC, 23:128, 2016. Google Scholar
  14. Rodney G Downey and Michael R Fellows. Fixed-parameter intractability. In 1992 Seventh Annual Structure in Complexity Theory Conference, pages 36-37. IEEE Computer Society, 1992. Google Scholar
  15. Rodney G Downey and Michael R Fellows. Fundamentals of parameterized complexity, volume 4. Springer, 2013. Google Scholar
  16. Paul Erdös and András Hajnal. Chromatic number of finite and infinite graphs and hypergraphs. Discrete Mathematics, 53:281-285, 1985. Google Scholar
  17. Eli Fox-Epstein, Duc A Hoang, Yota Otachi, and Ryuhei Uehara. Sliding token on bipartite permutation graphs. In International Symposium on Algorithms and Computation, pages 237-247. Springer, 2015. Google Scholar
  18. John E Hopcroft and Richard M Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2(4):225-231, 1973. Google Scholar
  19. Takehiro Ito, Erik D Demaine, Nicholas JA Harvey, Christos H Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. Theoretical Computer Science, 412(12-14):1054-1065, 2011. Google Scholar
  20. Takehiro Ito, Marcin Kamiński, and Hirotaka Ono. Fixed-parameter tractability of token jumping on planar graphs. In International Symposium on Algorithms and Computation, pages 208-219. Springer, 2014. Google Scholar
  21. Takehiro Ito, Marcin Kaminski, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, and Katsuhisa Yamanaka. On the parameterized complexity for token jumping on graphs. In Theory and Applications of Models of Computation - 11th Annual Conference (TAMC), volume 8402, pages 341-351, 2014. Google Scholar
  22. Marcin Kamiński, Paul Medvedev, and Martin Milanič. Complexity of independent set reconfigurability problems. Theoretical computer science, 439:9-15, 2012. Google Scholar
  23. Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Springer, 1972. Google Scholar
  24. Dénes Kőnig. Graphok és alkalmazásuk a determinánsok és a halmazok elméletére. Mathematikai és Természettudományi Ertesito, 34:104-119, 1916. Google Scholar
  25. Subhash Khot and Venkatesh Raman. Parameterized complexity of finding subgraphs with hereditary properties. Theoretical Computer Science, 289(2):997-1008, 2002. Google Scholar
  26. Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, and Magnus Wahlström. Multi-budgeted directed cuts. In 13th International Symposium on Parameterized and Exact Computation (IPEC), volume 115, pages 18:1-18:14, 2018. Google Scholar
  27. Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai, and Venkatesh Raman. Kernel lower bounds using co-nondeterminism: Finding induced hereditary subgraphs. In Algorithm Theory - SWAT, volume 7357, pages 364-375, 2012. Google Scholar
  28. Bingkai Lin. The parameterized complexity of k-biclique. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 605-615, 2015. Google Scholar
  29. Bingkai Lin. The parameterized complexity of the k-biclique problem. Journal of the ACM (JACM), 65(5):1-23, 2018. Google Scholar
  30. Bingkai Lin and Yijia Chen. The parameterized complexity of k-edge induced subgraphs. In International Colloquium on Automata, Languages, and Programming, pages 641-652. Springer, 2012. Google Scholar
  31. Daniel Lokshtanov and Amer E Mouawad. The complexity of independent set reconfiguration on bipartite graphs. ACM Transactions on Algorithms (TALG), 15(1):1-19, 2018. Google Scholar
  32. Daniel Lokshtanov, Amer E Mouawad, Fahad Panolan, MS Ramanujan, and Saket Saurabh. Reconfiguration on sparse graphs. Journal of Computer and System Sciences, 95:122-131, 2018. Google Scholar
  33. Dániel Marx. Parameterized complexity and approximation algorithms. Computer Journal, 51(1):60-78, 2008. Google Scholar
  34. Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. In 36th Annual Symposium on Foundations of Computer Science (FOCS), pages 182-191, 1995. Google Scholar
  35. Naomi Nishimura. Introduction to reconfiguration. Algorithms, 11(4):52, 2018. Google Scholar
  36. Jeanette P Schmidt and Alan Siegel. The spatial complexity of oblivious k-probe hash functions. SIAM Journal on Computing, 19(5):775-786, 1990. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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