License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2021.2
URN: urn:nbn:de:0030-drops-153851
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15385/
Agrawal, Akanksha ;
Allumalla, Ravi Kiran ;
Dhanekula, Varun Teja
Refuting FPT Algorithms for Some Parameterized Problems Under Gap-ETH
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.
BibTeX - Entry
@InProceedings{agrawal_et_al:LIPIcs.IPEC.2021.2,
author = {Agrawal, Akanksha and Allumalla, Ravi Kiran and Dhanekula, Varun Teja},
title = {{Refuting FPT Algorithms for Some Parameterized Problems Under Gap-ETH}},
booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
pages = {2:1--2:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-216-7},
ISSN = {1868-8969},
year = {2021},
volume = {214},
editor = {Golovach, Petr A. and Zehavi, Meirav},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15385},
URN = {urn:nbn:de:0030-drops-153851},
doi = {10.4230/LIPIcs.IPEC.2021.2},
annote = {Keywords: Token Jumping, Bipartite Graphs, Fixed Parameter Intractability, Half Graphs, Gap-Exponential Time Hypothesis}
}
|
Keywords: |
|
Token Jumping, Bipartite Graphs, Fixed Parameter Intractability, Half Graphs, Gap-Exponential Time Hypothesis |
|
Collection: |
|
16th International Symposium on Parameterized and Exact Computation (IPEC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
22.11.2021 |
