1 problem

0 votes0 replies0 views
SETH-based lower-bound conjecture for Induced Matching on graphs of bounded pathwidth
Let $(G,\ell)$ be an instance of textsc{Induced Matching}, together with a path decomposition of $G$ of width $\operatorname{pw}$ . The Strong Exponential Time Hypothesis (SETH) ass…
Conjectureopeninduced-matching parameterized-complexity pathwidtharXiv posted 2 days ago

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