Abstract
In this article we study a wellknown problem, called Bipartite Token Jumping and notsowell known problem(s), which we call, Half (Induced) Subgraph, and show that under GapETH, 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 ksized 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_{j1} by replacing a vertex in I_{j1} by a vertex in V(G) ⧵ I_{j1}. We show that, assuming GapETH, 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 GapETH. 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 GapETH, 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 GapETH. 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 GapETH}},
booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
pages = {2:12:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772167},
ISSN = {18688969},
year = {2021},
volume = {214},
editor = {Golovach, Petr A. and Zehavi, Meirav},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15385},
URN = {urn:nbn:de:0030drops153851},
doi = {10.4230/LIPIcs.IPEC.2021.2},
annote = {Keywords: Token Jumping, Bipartite Graphs, Fixed Parameter Intractability, Half Graphs, GapExponential Time Hypothesis}
}
Keywords: 

Token Jumping, Bipartite Graphs, Fixed Parameter Intractability, Half Graphs, GapExponential Time Hypothesis 
Collection: 

16th International Symposium on Parameterized and Exact Computation (IPEC 2021) 
Issue Date: 

2021 
Date of publication: 

22.11.2021 