License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.689
URN: urn:nbn:de:0030-drops-49513
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4951/
Go to the corresponding LIPIcs Volume Portal

Schweitzer, Pascal

Towards an Isomorphism Dichotomy for Hereditary Graph Classes

pdf-format:
51.pdf (0.5 MB)

Abstract

In this paper we resolve the complexity of the isomorphism problem on
all but finitely many of the graph classes characterized by two forbidden induced subgraphs. To this end we develop new techniques applicable for the structural and algorithmic analysis of graphs. First, we develop a methodology to show isomorphism completeness of the isomorphism problem on graph classes by providing a general framework unifying various reduction techniques. Second, we generalize the concept of the modular decomposition to colored graphs, allowing for non-standard decompositions. We show that, given a suitable decomposition functor, the graph isomorphism problem reduces to checking isomorphism of colored prime graphs. Third, we extend the techniques of bounded color valence and hypergraph isomorphism on hypergraphs of bounded color class size as follows. We say a colored graph has generalized color valence at most k if, after removing all vertices in color classes of size at most k, for each color class C every vertex has at most k neighbors in C or at most k non-neighbors in C. We show that isomorphism of graphs of bounded generalized color valence can be solved in polynomial time.

BibTeX - Entry

@InProceedings{schweitzer:LIPIcs:2015:4951,
  author =	{Pascal Schweitzer},
  title =	{{Towards an Isomorphism Dichotomy for Hereditary Graph Classes}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{689--702},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4951},
  URN =		{urn:nbn:de:0030-drops-49513},
  doi =		{10.4230/LIPIcs.STACS.2015.689},
  annote =	{Keywords: graph isomorphism, modular decomposition, bounded color valence, reductions, forbidden induced subgraphs}
}

Keywords: graph isomorphism, modular decomposition, bounded color valence, reductions, forbidden induced subgraphs
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI