Faster and Enhanced InclusionMinimal Cograph Completion. We design two incremental algorithms for computing an inclusionminimal completion of an arbitrary graph into a cograph. The first one is able to do so while providing an additional property which is crucial in practice to obtain inclusionminimal completions using as few edges as possible : it is able to compute a minimumcardinality completion of the neighbourhood of the new vertex introduced at each incremental step. It runs in O(nmu0027) time, where mu0027 is the number of edges in the completed graph. This matches the complexity of the algorithm in Lokshtanov, Mancini and Papadopoulos 2010 and positively answers one of their open questions. Our second algorithm improves the complexity of inclusionminimal completion to O(nmlog2 n) when the additional property above is not required. Moreover, we prove that many very sparse graphs, having only O(n) edges, require Omega(n2) edges in any of their cograph completions. For these graphs, which include many of those encountered in applications, the improvement we obtain on the complexity scales as O(nlog2 n).

Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling. We devise a method to enumerate the inclusionwise minimal hitting sets of a hypergraph. The algorithm has delay O( mk*1 , n2) on nvertex, medge hypergraphs, where k* is the rank of the transversal hypergraph, i.e., the cardinality of the largest minimal solution. In particular, on classes of hypergraphs for which k* is bounded, the delay is polynomial. The algorithm uses space linear in the input size only. The enumeration methods solves the extension problem for minimal hitting sets as a subroutine. We show that this problem, parameterised by the cardinality of the set which is to be extended, is one of the first natural W3complete problems. We give an algorithm for the subroutine that is optimal under the assumption that W2 neq mathrmFPT or the exponential time hypothesis (ETH), respectively. Despite the hardness of the extension problem, we provide empirical evidence indicating that the enumeration outperforms its theoretical worstcase guarantee on hypergraphs arising in the profiling of relational databases, namely, in the detection of unique column combinations. Our analysis suggest that these hypergraphs exhibit structure that allows the subroutine to be fast on average.