Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions
share
We provide a general framework to exclude parameterized running times of the form O(ℓ^β+ 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(ℓ^γ/(γ-1) - ϵ + n^γ) for any 1<γ<2 and ϵ>0 for the following problems: - Longest Common Subsequence: Given two length-n strings and ℓ∈ℕ, is there a common subsequence of length ℓ? - Discrete Fréchet Distance: Given two lists of n points each and k∈ℕ, is the Fréchet distance of the lists at most k? Here ℓ is the maximum number of points which one list is ahead of the other list in an optimum traversal. Moreover, we exclude running times O(ℓ^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 ℓ 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 ℓ is the order of a maximum connected component. - 2nd Shortest Path: Given an n-vertex edge-weighted directed graph, two vertices s and t, and k ∈ℕ, has the second longest s-t-path length at most k? Here ℓ is the directed feedback vertex set. Except for 2nd Shortest Path all these running time bounds are tight, that is, algorithms with running time O(ℓ^γ/(γ-1) + n^γ ) for any 1 < γ < 2 and O(ℓ^2γ/(γ -1) + n^γ) for any 1 < γ < 3, respectively, are known.
READ FULL TEXT