Campus Event Calendar

Event Entry

What and Who

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

Jasper Slusallek
Fachrichtung Informatik - Saarbrücken
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Tuesday, 23 June 2020
30 Minutes
E1 4


The Subgraph Isomorphism problem is of considerable importance in computer science. We examine the problem when the pattern graph is of bounded treewidth, as occurs in a variety of applications. Of particular interest to us is a weighted variant where the solution subgraph must be of total weight zero. Allowing the largest absolute weight to appear in the running time, we design new algorithms and show essentially matching lower bounds.

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 for the password.


Karl Bringmann
+49 681 9325 1005
--email hidden
passcode not visible
logged in users only

Karl Bringmann, 06/21/2020 20:25
Karl Bringmann, 06/11/2020 09:34
Karl Bringmann, 06/10/2020 20:41
Karl Bringmann, 06/10/2020 20:39 -- Created document.