Subgraph isomorphism on graph classes that exclude a substructure

Hans L. Bodlaender, Tesshu Hanaka, Yoshio Okamoto, Yota Otachi, Tom C. van der Zanden

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

We study Subgraph Isomorphism on graph classes defined by a fixed forbidden graph. Although there are several ways for forbidding a graph, we observe that it is reasonable to focus on the minor relation since other well-known relations lead to either trivial or equivalent problems. When the forbidden minor is connected, we present a near dichotomy of the complexity of Subgraph Isomorphism with respect to the forbidden minor, where the only unsettled case is the path of five vertices. We then also consider the general case of possibly disconnected forbidden minors. We show in particular that: the problem is fixed-parameter tractable parameterized by the size of the forbidden minor H when H is a linear forest such that at most one component has four vertices and all other components have three or less vertices; and it is NP-complete if H contains four or more components with at least five vertices each. As a byproduct, we show that Subgraph Isomorphism is fixed-parameter tractable parameterized by vertex integrity. Using similar techniques, we also observe that Subgraph Isomorphism is fixed-parameter tractable parameterized by neighborhood diversity.

Original languageEnglish
Title of host publicationAlgorithms and Complexity - 11th International Conference, CIAC 2019, Proceedings
EditorsPinar Heggernes
Place of PublicationCham
PublisherSpringer
Pages87-98
Number of pages12
ISBN (Electronic)978-3-030-17402-6
ISBN (Print)978-3-030-17401-9
DOIs
Publication statusPublished - 6 Apr 2019
Event11th International Conference on Algorithms and Complexity, CIAC 2019 - Rome, Italy
Duration: 27 May 201929 May 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11485 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Conference on Algorithms and Complexity, CIAC 2019
CountryItaly
CityRome
Period27/05/1929/05/19

Keywords

  • Minor free graphs
  • Parameterized complexity
  • Subgraph isomorphism

Fingerprint Dive into the research topics of 'Subgraph isomorphism on graph classes that exclude a substructure'. Together they form a unique fingerprint.

Cite this