Understanding the Complexity of Induced Subgraph Isomorphisms

DOI10.1007/978-3-540-70575-8_48MaRDI QIDQ3521949zbMATH OpenOpenAlexFDO

Authors Yijia Chen, Marc Thurley, Mark Weyer

Publication date 28 August 2008

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70575-8_48

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Induced subgraph isomorphism: are some patterns substantially easier than others?
• Isomorphism on subgraph-closed graph classes: a complexity dichotomy and intermediate graph classes
• Induced subgraph isomorphism: are some patterns substantially easier than others?
• Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
• Induced subgraph isomorphism on interval and proper interval graphs

Cited in

(25)

• Computing the number of induced copies of a fixed graph in a bounded degree graph
• The parameterised complexity of counting connected subgraphs and graph motifs
• Counting edge-injective homomorphisms and matchings on restricted graph classes
• Constructing NP-intermediate problems by blowing holes with parameters of various properties
• The parameterized space complexity of embedding along a path
• Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
• Induced subgraph isomorphism on interval and proper interval graphs
• Simulation relations for pattern matching in directed graphs
• Counting problems in parameterized complexity
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Counting connected subgraphs with maximum-degree-aware sieving
• Boolean tensor decomposition for conjunctive queries with negation
• Parameterized Graph Cleaning Problems
• Parameterised and fine-grained subgraph counting, modulo 2
• Counting Small Induced Subgraphs with Hereditary Properties
• Parameterized Counting and Cayley Graph Expanders
• A color-avoiding approach to subgraph counting in bounded expansion classes
• The complexity of pattern counting in directed graphs, parameterised by the outdegree
• Counting subgraphs in somewhere dense graphs
• Detecting and counting small subgraphs, and evaluating a parameterized Tutte polynomial: lower bounds via toroidal grids and Cayley graph expanders
• The parameterized complexity of k-edge induced subgraphs
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Induced subgraph isomorphism: are some patterns substantially easier than others?
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• Parameterized graph cleaning problems

This page was built for publication: Understanding the Complexity of Induced Subgraph Isomorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3521949)