Subgraph isomorphism on graph classes that exclude a substructure
From MaRDI portal
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 fixed-parameter tractable cases and randomized XP-time solvable cases parameterized by the size of the forbidden minor . We also show that by slightly generalizing the tractable cases, the problem becomes NP-complete. All unsettle cases are equivalent to or the disjoint union of two 's. 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.
Recommendations
- Subgraph isomorphism on graph classes that exclude a substructure
- Subgraph isomorphism in graph classes
- On isomorphic subgraphs
- Structure theorem and isomorphism test for graphs with excluded topological subgraphs
- Structure theorem and isomorphism test for graphs with excluded topological subgraphs
- scientific article; zbMATH DE number 4043266
- Isomorphism on subgraph-closed graph classes: a complexity dichotomy and intermediate graph classes
- scientific article; zbMATH DE number 1500686
- scientific article; zbMATH DE number 4152423
- Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
Cites work
- Algorithmic meta-theorems for restrictions of treewidth
- An application of simultaneous diophantine approximation in combinatorial optimization
- Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
- Color-coding
- Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
- Finding a chain graph in a bipartite permutation graph
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- scientific article; zbMATH DE number 6515825 (Why is no real title available?)
- scientific article; zbMATH DE number 4053662 (Why is no real title available?)
- scientific article; zbMATH DE number 139780 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3445275 (Why is no real title available?)
- Integer Programming with a Fixed Number of Variables
- List edge multicoloring in graphs with few cycles
- Matching is as easy as matrix inversion
- Minkowski's Convex Body Theorem and Integer Programming
- Modular decomposition and transitive orientation
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- Parameterized algorithms
- Planar subgraph isomorphism revisited
- Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- Sparsity. Graphs, structures, and algorithms
- Subexponential time algorithms for embedding H-minor free graphs
- Subgraph isomorphism for biconnected outerplanar graphs in cubic time
- Subgraph isomorphism in graph classes
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
- Subtree Isomorphism in O(n5/2)
- Surface split decompositions and subgraph isomorphism in graphs on surfaces
- The complexity of induced minors and related problems
- The complexity of subgraph isomorphism for classes of partial k-trees
- Tight lower bounds on graph embedding problems
Cited in
(16)- Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
- The subgraph isomorphism problem on a class of hyperedge replacement languages
- Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
- Structure theorem and isomorphism test for graphs with excluded topological subgraphs
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Subgraph isomorphism on graph classes that exclude a substructure
- Extended MSO model checking via small vertex integrity
- Dichotomies for tree minor containment with structural parameters
- Dichotomies for tree minor containment with structural parameters
- Maximum common induced subforests and minimum common induced superforests of a set of forests
- Complexity framework for forbidden subgraphs. IV: The Steiner forest problem
- Complexity framework for forbidden subgraphs. IV: The Steiner forest problem
- Complexity framework for forbidden subgraphs. I: The framework
- Fine-grained meta-theorems for vertex integrity
- Complexity framework for forbidden subgraphs. II: Edge subdivision and the ``H-graphs
- Linear layouts revisited: stacks, queues, and exact algorithms
This page was built for publication: Subgraph isomorphism on graph classes that exclude a substructure
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5919029)
