Tight Complexity Results for General Factor Problems Parameterized by Treewidth and Cutwidth

We prove that this algorithm is essentially optimal for all cases that are not trivial or polynomial time solvable for the decision, minimization, or maximization versions. Our lower bounds show that such an improvement is not possible even for the restricted problem where all vertices share a common list $B$. We show that for every fixed $B$ where the problem is NP-hard, our $O^*{(\max B+1)^{tw}}$ algorithm cannot be significantly improved assuming the Strong Exponential Time Hypothesis (SETH). We extend this bound to the counting version of the problem for arbitrary, non-trivial sets $B$ assuming #SETH.

We also investigate the parameterization of the problem by cutwidth. Unlike for treewidth, having larger sets does not appear to make the problem harder: we give a $O^*{2^{cutw}}$ algorithm and provide a matching lower bound for the NP-hard cases.

--------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.