Florian Kurpicz
Presentation at IWOCA 2014

On Maximum Common Subgraph Problems in Series-Parallel Graphs

This week, I presented our work on maximum common subgraph problems in series-parallel graphs at IWOCA 2014 (link is dead), which are the result of my master's thesis. The slides are available as handout and heavily animated. The paper is availbale from here (DOI) and here (arXiv).

Slides in Handout Mode

Slide image IWOCA_Presentation-01.jpg
Slide image IWOCA_Presentation-02.jpg
Slide image IWOCA_Presentation-03.jpg
Slide image IWOCA_Presentation-04.jpg
Slide image IWOCA_Presentation-05.jpg
Slide image IWOCA_Presentation-06.jpg
Slide image IWOCA_Presentation-07.jpg
Slide image IWOCA_Presentation-08.jpg
Slide image IWOCA_Presentation-09.jpg
Slide image IWOCA_Presentation-10.jpg
Slide image IWOCA_Presentation-11.jpg
Slide image IWOCA_Presentation-12.jpg
Slide image IWOCA_Presentation-13.jpg
Slide image IWOCA_Presentation-14.jpg
Slide image IWOCA_Presentation-15.jpg
Slide image IWOCA_Presentation-16.jpg
Slide image IWOCA_Presentation-17.jpg

Abstract

The complexity of the maximum common connected subgraph problem in partial k-trees is still not fully understood. Polynomial-time solutions are known for degree-bounded outerplanar graphs, a subclass of the partial 2-trees. On the contrary, the problem is known to be NP-hard in vertex-labeled partial 11-trees of bounded degree. We consider series-parallel graphs, i.e., partial 2-trees. We show that the problem remains NP-hard in biconnected series-parallel graphs with all but one vertex of degree bounded by three. A positive complexity result is presented for a related problem of high practical relevance which asks for a maximum common connected subgraph that preserves blocks and bridges of the input graphs. We present a polynomial time algorithm for this problem in series-parallel graphs, which utilizes a combination of BC- and SP-tree data structures to decompose both graphs.