Complexity dichotomies for the \textsc{Minimum} \(\mathcal{F}\)-\textsc{Overlay} problem

DOI10.1016/j.jda.2018.11.010zbMath1410.68161MaRDI QIDQ1711667

Frédéric Havet, Rémi Watrigant, Ignasi Sau, Nathann Cohen, Dorian Mazauric

Publication date: 18 January 2019

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2018.11.010

zbMATH Keywords

hypergraph; NP-completeness; fixed-parameter tractability; minimum \(\mathcal{F}\)-overlay problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C65: Hypergraphs

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.)