Understanding the Complexity of Induced Subgraph Isomorphisms

DOI10.1007/978-3-540-70575-8_48zbMath1153.68387OpenAlexW127859554MaRDI QIDQ3521949

Marc Thurley, Yijia Chen, 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)

Related Items

Simulation relations for pattern matching in directed graphs, Induced subgraph isomorphism: are some patterns substantially easier than others?, The challenges of unbounded treewidth in parameterised subgraph counting 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, Unnamed Item, Unnamed Item, 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, Parameterized graph cleaning problems, Unnamed Item, Unnamed Item, The parameterized complexity of \(k\)-edge induced subgraphs, Counting edge-injective homomorphisms and matchings on restricted graph classes, Counting induced subgraphs: a topological approach to \#W[1-hardness], Constructing NP-intermediate problems by blowing holes with parameters of various properties