SETH-based lower-bound conjecture for Induced Matching on graphs of bounded pathwidth
SETH-based lower-bound conjecture for Induced Matching on graphs of bounded pathwidth
Let be an instance of \textsc{Induced Matching}, together with a path decomposition of of width . The Strong Exponential Time Hypothesis (SETH) asserts that, for every , no algorithm solves all such instances in time . SETH-based lower-bound conjecture. Unless the Strong Exponential Time Hypothesis is false, there does not exist a constant and an algorithm that, given an instance together with a path decomposition of of width , solves \textsc{Induced Matching} in time. This conjectured lower bound would establish that the base in parameterized algorithms for \textsc{Induced Matching} under pathwidth cannot be improved, assuming SETH.
Sources & referencesView supporting material
Primary source
Juhi Chaudhary and Meirav Zehavi, “P-matchings Parameterized by Treewidth”, arXiv:2307.09333 (2023).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.