On the complexity of various parameterizations of common induced subgraph isomorphism

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

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

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 complexity; kernelization; ETH-based lower bounds; induced common isomorphism

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)