Algorithms and Lower Bounds for Finding Exact-Weight Subgraphs of Bounded Treewidth (Bachelor thesis)

The conditional lower bounds are shown via a reduction from hyperclique. We achieve this by encoding some percentage of the hyperclique instance in the edges of the host graph, while encoding the rest in the weights. By setting the percentage that is stored in the edges to either of the extremes, we also show conditional lower bounds for the unweighted variant of the problem, as well as for Subset Sum.

On the algorithmic side, we first analyze the unweighted variant and use so-called k-wise matrix products to unify existing algorithms with a single technique, while still matching their running times. We then expand the algorithms to the weighted variant, improving on the best-known naive dynamic programming algorithm.

We also show similar results for the case of bounded pathwidth, with slight algorithmic improvements for both the weighted and the unweighted case. In this setting, we also show still further improvements for the node-weighted case.

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.