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)

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

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)