When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.35
URN: urn:nbn:de:0030-drops-176876
URL: https://drops.dagstuhl.de/opus/volltexte/2023/17687/
 Go to the corresponding LIPIcs Volume Portal

### Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions

 pdf-format:

### 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 fine-grained complexity. Our framework is based on cross-compositions 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 length-n 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 non-intersecting axis-parallel 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 edge-weighted graph with n vertices, is there a triangle whose sum of edge-weights is negative? Here l is the order of a maximum connected component.
- Triangle Collection: Given a vertex-colored 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 n-vertex edge-weighted digraph, vertices s and t, and k ∈ ℕ, has the second longest s-t-path 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 Fine-Grained Cross-Compositions}},
booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
pages =	{35:1--35:19},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-266-2},
ISSN =	{1868-8969},
year =	{2023},
volume =	{254},
editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},