Florian Kurpicz
Article Available in European Journal of Combinatorics

On Maximum Common Subgraph Problems in Series-Parallel Graphs

Our article "On Maximum Common Subgraph Problems in Series-Parallel Graphs" has been published in the European Journal of Combinatorics (Eur. J. Comb.). It extends our previous research on the problem, which we describe here. The article is available here (DOI).

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 other hand, 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 or less. 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.