SETH-based lower-bound conjecture for Induced Matching on graphs of bounded pathwidth

Let (G,)(G,\ell) be an instance of \textsc{Induced Matching}, together with a path decomposition of GG of width pw\operatorname{pw}. The Strong Exponential Time Hypothesis (SETH) asserts that, for every ϵ>0\epsilon>0, no algorithm solves all such instances in time (3ϵ)pwnO(1)(3-\epsilon)^{\operatorname{pw}}\cdot n^{\mathcal{O}(1)}. SETH-based lower-bound conjecture. Unless the Strong Exponential Time Hypothesis is false, there does not exist a constant ϵ>0\epsilon>0 and an algorithm that, given an instance (G,)(G,\ell) together with a path decomposition of GG of width pw\operatorname{pw}, solves \textsc{Induced Matching} in (3ϵ)pwnO(1)(3-\epsilon)^{\operatorname{pw}}\cdot n^{\mathcal{O}(1)} time. This conjectured lower bound would establish that the base 33 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.