On the complexity of various parameterizations of common induced subgraph isomorphism

DOI10.1016/j.tcs.2017.07.010zbMath1378.68055arXiv1412.1261OpenAlexW2971952735MaRDI QIDQ2405897

Florian Sikora, Faisal N. Abu-Khzam, Édouard Bonnet

Publication date: 28 September 2017

Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.1261

zbMATH Keywords

parameterized complexitykernelizationETH-based lower boundsinduced common isomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (4)

Streaming deletion problems parameterized by vertex cover ⋮ On the complexity of various parameterizations of common induced subgraph isomorphism ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Improved upper bounds for vertex cover
• Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• The parameterized complexity of the induced matching problem
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Which problems have strongly exponential complexity?
• The Turing way to parameterized complexity
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Cleaning interval graphs
• On the complexity of various parameterizations of common induced subgraph isomorphism
• Maximum common induced subgraph parameterized by vertex cover
• Fixed-Parameter Tractability, Definability, and Model-Checking
• Algorithmic Aspects of Dominator Colorings in Graphs
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Deciding First-Order Properties of Nowhere Dense Graphs
• Kernelization Lower Bounds by Cross-Composition

This page was built for publication: On the complexity of various parameterizations of common induced subgraph isomorphism