Title: Complexity Dichotomies for the Minimum F-Overlay Problem,
Abstract: For a (possibly infinite) fixed family of graphs F, we say that a graph G
overlays F on a hypergraph H if V(H) is equal to V(G) and the subgraph of G
induced by every hyperedge of H contains some member of F as a spanning
subgraph.While it is easy to see that the complete graph on |V(H)| overlays F
on a hypergraph H whenever the problem admits a solution, the Minimum F-Overlay
problem asks for such a graph with the minimum number of edges.This problem
allows to generalize some natural problems which may arise in practice. For
instance, if the family F contains all connected graphs, then Minimum F-Overlay
corresponds to the Minimum Connectivity Inference problem (also known as Subset
Interconnection Design problem) introduced for the low-resolution
reconstruction of macro-molecular assembly in structural biology, or for the
design of networks.Our main contribution is a strong dichotomy result regarding
the polynomial vs. NP-hard status with respect to the considered family F.
Roughly speaking, we show that the easy cases one can think of (e.g. when
edgeless graphs of the right sizes are in F, or if F contains only cliques) are
the only families giving rise to a polynomial problem: all others are
NP-complete.We then investigate the parameterized complexity of the problem and
give similar sufficient conditions on F that give rise to W[1]-hard, W[2]-hard
or FPT problems when the parameter is the size of the solution.This yields an
FPT/W[1]-hard dichotomy for a relaxed problem, where every hyperedge of H must
contain some member of F as a (non necessarily spanning) subgraph.