Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions
| Autor: | Heeger, Klaus, Nichterlein, André, Niedermeier, Rolf |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: | |
| Popis: | 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. LIPIcs, Vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pages 35:1-35:19 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|