Heeger, Klaus ;
Nichterlein, André ;
Niedermeier, Rolf
Parameterized Lower Bounds for Problems in P via FineGrained CrossCompositions
Abstract
We provide a general framework to exclude parameterized running times of the form O(l^β + n^γ) for problems that have polynomial running time lower bounds under hypotheses from finegrained complexity. Our framework is based on crosscompositions from parameterized complexity. We (conditionally) exclude running times of the form O(l^{γ/(γ1)  ε} + n^γ) for any 1 < γ < 2 and ε > 0 for the following problems:
 Longest Common (Increasing) Subsequence: Given two lengthn strings over an alphabet Σ (over ℕ) and l ∈ ℕ, is there a common (increasing) subsequence of length l in both strings?
 Discrete Fréchet Distance: Given two lists of n points each and k ∈ N, is the Fréchet distance of the lists at most k? Here l is the maximum number of points which one list is ahead of the other list in an optimum traversal.
 Planar Motion Planning: Given a set of n nonintersecting axisparallel line segment obstacles in the plane and a line segment robot (called rod), can the rod be moved to a specified target without touching any obstacles? Here l is the maximum number of segments any segment has in its vicinity. Moreover, we exclude running times O(l^{2γ/(γ1)  ε} + n^γ) for any 1 < γ < 3 and ε > 0 for:
 Negative Triangle: Given an edgeweighted graph with n vertices, is there a triangle whose sum of edgeweights is negative? Here l is the order of a maximum connected component.
 Triangle Collection: Given a vertexcolored graph with n vertices, is there for each triple of colors a triangle whose vertices have these three colors? Here l is the order of a maximum connected component.
 2nd Shortest Path: Given an nvertex edgeweighted digraph, vertices s and t, and k ∈ ℕ, has the second longest stpath length at most k? Here l is the directed feedback vertex set number. Except for 2nd Shortest Path all these running time bounds are tight, that is, algorithms with running time O(l^{γ/(γ1)} + n^γ) for any 1 < γ < 2 and O(l^{2γ/(γ 1)} + n^γ) for any 1 < γ < 3, respectively, are known. Our running time lower bounds also imply lower bounds on kernelization algorithms for these problems.
BibTeX  Entry
@InProceedings{heeger_et_al:LIPIcs.STACS.2023.35,
author = {Heeger, Klaus and Nichterlein, Andr\'{e} and Niedermeier, Rolf},
title = {{Parameterized Lower Bounds for Problems in P via FineGrained CrossCompositions}},
booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
pages = {35:135:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772662},
ISSN = {18688969},
year = {2023},
volume = {254},
editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17687},
URN = {urn:nbn:de:0030drops176876},
doi = {10.4230/LIPIcs.STACS.2023.35},
annote = {Keywords: FPT in P, Kernelization, Decomposition}
}
03.03.2023
Keywords: 

FPT in P, Kernelization, Decomposition 
Seminar: 

40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Issue date: 

2023 
Date of publication: 

03.03.2023 