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

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

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

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

hypergraphNP-completenessfixed-parameter tractabilityminimum \(\mathcal{F}\)-overlay problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) 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)

Cites Work

• Fundamentals of parameterized complexity
• On the approximability and hardness of minimum topic connected overlay and its special instances
• The clustering matroid and the optimal clustering tree
• On complexity of subset interconnection designs
• Blocks of Hypergraphs
• Minimum Tree Supports for Hypergraphs and Low-Concurrency Euler Diagrams
• Polynomial-Time Data Reduction for the Subset Interconnection Design Problem
• Hypergraph planarity and the complexity of drawing venn diagrams
• Matroids and Subset Interconnection Design
• Inferring Social Networks from Outbreaks
• Constructing scalable overlays for pub-sub with many topics
• Algorithms and Implementation for Interconnection Graph Problem

This page was built for publication: Complexity dichotomies for the \textsc{Minimum} \(\mathcal{F}\)-\textsc{Overlay} problem