Duration: 01/01/2025–31/12/2028 (48 months)

Description

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, the goal is to obtain algorithms running in a time which is polynomial in the sizes of the input plus the output. Within the frame of algorithmic enumeration, these algorithms are said to be running in polynomial total time. See here for more details.

Despite decades of intensive study, the complexity status of Trans-Enum remains unsettled. To date, the best known algorithm runs in total quasi-polynomial time. Whether the problem can be solved in polynomial total 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 total 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)\cdot \mathrm{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.

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.

Consortium

• BERGOUGNOUX Benjamin (MCF AMU)
• CHEPOI Victor (PR AMU)
• CREIGNOU Nadia (PR AMU)
• DEFRAIN Oscar (MCF AMU, coordinator)
• MC INERNEY Fionn (researcher telefonica)
• OLIVE Frédéric (MCF AMU)
• VILMIN Simon (MCF AMU)

Institutions

• LIS (ACRO)
• AMU

Events

• Kickoff meeting (25/03/2025)

Publications

1. Emanuel Castelo, Oscar Defrain, and Guilherme C. M. Gomes. Enumerating minimal dominating sets and variants in chordal bipartite graphs. CoRR abs/2502.14611 (2025) arXiv
   

Initial works

1. Benjamin Bergougnoux, Oscar Defrain, and Fionn Mc Inerney. Enumerating minimal solution sets for metric graph problems. Algorithmica, 1–24 (2025) arXiv DOI
   
2. Nadia Creignou, Oscar Defrain, Frédéric Olive, and Simon Vilmin. On the enumeration of signatures of XOR-CNF’s. CoRR abs/2402.18537 (2024) arXiv
   
3. Valentin Bartier, Oscar Defrain, and Fionn Mc Inerney. Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension. IWOCA 2024: 111-125 arXiv