Parameterized aspects of Dualization – PARADUAL

Hypergraph dualization appears in disguise in countless areas of computer science ranging from logic to database theory. Over the years, it has undoubtedly become one of the most important open problems in algorithmic enumeration. The generation version of the problem, Trans-Enum, takes as input a hypergraph and asks to find all its minimal transversals. As the number of such sets may be exponential in the size of the hypergraph, we aim for algorithms running in time polynomial in the sizes of the input plus the output. Within the frame of algorithmic enumeration, these algorithms are said to be running in output-polynomial time. Despite decades of intensive study, the complexity status of Trans-Enum remains unsettled. To date, the best known algorithm runs in output-quasi-polynomial time. Whether the problem can be solved in output-polynomial time is a fascinating and scientifically challenging question. In fact, several tractable instances of Trans-Enum have been identified through bounding carefully chosen parameters. Among them, degeneracy, dimension, or clique number, the latter arising from the equivalent context of graph domination. Each of these cases offers an algorithm for Trans-Enum with running time N^f(k), where f is a computable function, N is the sum of the sizes of the input and the output, and k is the parameter. Albeit output-polynomial for a fixed parameter, these algorithms are unusable in practice, even for instances for which the parameter at hand is relatively small. For practical instances, execution times of the form f(k)*poly(N) are much more desirable. These are said to be FPT in terms of parameterized complexity, and hint at a better tractability of the problem. One of the main objective of parameterized complexity is the study of problems and parameters admitting for such time bounds. To do so, many techniques have been obtained these last years leading to a fruitful line of research. On the other hand, execution times of that kind are sometimes impossible for some problems and parameters under standard assumptions. On that direction, parameterized complexity offers a wide range of techniques to obtain these lower bounds. In the project PARADUAL, we propose to investigate hypergraph dualization and related problems through the lens of parameterized complexity. With this approach, rather novel in algorithmic enumeration, we seek to obtain new tractable cases and efficient algorithms for the dualization.