Skip to main content Link Search Menu Expand Document (external link)

Efficient Algorithms for the Maximum Common Subgraph Problem in Partial 2-Trees

pdf

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.

BibTeX

@mastersthesis{Kurpicz2014,
  author    = {Florian Kurpicz},
  title     = {Efficient Algorithms for the Maximum Common Subgraph Problem in Partial 2-Trees},
  school    = {Technical University of Dortmund, Germany},
  year      = {2014}
}

PDF