It has been proved by Boros and Makino that there is no output-polynomial-time algorithm enumerating the minimal redundant sets or the maximal irredundant sets of a hypergraph, unless P = NP. The same question was left open for graphs, with only a few tractable cases known to date. In this paper, we focus on graph classes that capture incidence relations such as bipartite, co-bipartite, and split graphs, motivated by their strong relation with hypergraphs. Concerning maximal irredundant sets, we show that the problem on co-bipartite graphs is as hard as in general graphs and tractable in split and strongly orderable graphs, the latter being a generalization of chordal bipartite graphs. As for minimal redundant sets enumeration, we first show that the problem is intractable in split and co-bipartite graphs, answering the aforementioned open question. Then, we show that it is tractable on (C₃,C₅,C₆,C₈)-free graphs, a class of graphs incomparable to strongly orderable graphs, and which also generalizes chordal bipartite graphs. Our positive results rely on the structural properties of these graph classes and thus cannot be easily extended to bipartite graphs, for which the question remains open for both problems.

In the Isometric Path Partition problem, the input is a graph G with n vertices and an integer k, and the objective is to determine whether the vertices of G can be partitioned into k vertex-disjoint shortest paths. We investigate the parameterized complexity of the problem when parameterized by the treewidth (tw) of the input graph, arguably one of the most widely studied parameters. Courcelle’s theorem [Information & Computation, 1990] shows that graph problems that are expressible as MSO formulas of constant size admit FPT algorithms parameterized by the treewidth of the input graph. This encompasses many natural graph problems. However, many metric-based graph problems, where the solution is defined using some metric-based property of the graph (often the distance) are not expressible as MSO formulas of constant size. These types of problems, Isometric Path Partition being one of them, require individual attention and often draw the boundary for the success story of parameterization by treewidth. We show that Isometric Path Partition is W[1]-hard when parameterized by treewidth (in fact, even pathwidth (pw)), answering the question by Dumas et al. [SIDMA, 2024], Fernau et al. [TCS, 2025], and confirming the aforementioned tendency. We complement this hardness result by designing a tailored dynamic programming algorithm running in n^{O(tw)} time. This dynamic programming approach also results in an algorithm running in time diam^{O(tw²)} ⋅ n^{O(1)}, where diam is the diameter of the graph. It is known that Isometric Path Partition remains NP-hard on graphs of diameter 2; hence, the combination of both parameters is necessary to obtain a tractable algorithm. Note that the dependency on treewidth is unusually high, as most problems that are FPT for treewidth admit algorithms running in time 2^{O(tw)}⋅ n^{O(1)} or 2^{O(tw log (tw))}⋅ n^{O(1)}. However, we rule out the possibility of a significantly faster algorithm, showing that Isometric Path Partition does not admit an algorithm running in time diam^{o(pw²/(log³(pw)))} ⋅ n^{O(1)}, assuming the Randomized-ETH.

International audience

Enumerating minimal dominating sets with polynomial delay in bipartite graphs is a long-standing open problem. To date, even the subcase of chordal bipartite graphs is open, with the best known algorithm due to Golovach, Heggernes, Kanté, Kratsch, Sæther, and Villanger running in incremental-polynomial time. We improve on this result by providing a polynomial delay and space algorithm enumerating minimal dominating sets in chordal bipartite graphs. Additionally, we show that the total and connected variants admit polynomial and incremental-polynomial delay algorithms, respectively, within the same class. This provides an alternative proof of a result by Golovach et al. for total dominating sets, and answers an open question for the connected variant. Finally, we give evidence that the techniques used in this paper cannot be generalized to bipartite graphs for (total) minimal dominating sets, unless P = NP, and show that enumerating minimal connected dominating sets in bipartite graphs is harder than enumerating minimal transversals in general hypergraphs.

Given a CNF formula $φ$ with clauses $C_1, \dots, C_m$ over a set of variables $V$, a truth assignment $\mathbf{a} : V \to \{0, 1\}$ generates a binary sequence $σ_φ(\mathbf{a})=(C_1(\mathbf{a}), \ldots, C_m(\mathbf{a}))$, called a signature of $φ$, where $C_i(\mathbf{a})=1$ if clause $C_i$ evaluates to 1 under assignment $\mathbf{a}$, and $C_i(\mathbf{a})=0$ otherwise. Signatures and their associated generation problems have given rise to new yet promising research questions in algorithmic enumeration. In a recent paper, Bérczi et al. interestingly proved that generating signatures of a CNF is tractable despite the fact that verifying a solution is hard. They also showed the hardness of finding maximal signatures of an arbitrary CNF due to the intractability of satisfiability in general. Their contribution leaves open the problem of efficiently generating maximal signatures for tractable classes of CNFs, i.e., those for which satisfiability can be solved in polynomial time. Stepping into that direction, we completely characterize the complexity of generating all, minimal, and maximal signatures for XOR-CNFs.

The goal of local certification is to locally convince the vertices of a graph $G$ that $G$ satisfies a given property. A prover assigns short certificates to the vertices of the graph, then the vertices are allowed to check their certificates and the certificates of their neighbors, and based only on this local view, they must decide whether $G$ satisfies the given property. If the graph indeed satisfies the property, all vertices must accept the instance, and otherwise at least one vertex must reject the instance (for any possible assignment of certificates). The goal is to minimize the size of the certificates. In this paper we study the local certification of geometric and topological graph classes. While it is known that in $n$-vertex graphs, planarity can be certified locally with certificates of size $O(\log n)$, we show that several closely related graph classes require certificates of size $Ω(n)$. This includes penny graphs, unit-distance graphs, (induced) subgraphs of the square grid, 1-planar graphs, and unit-square graphs. These bounds are tight up to a constant factor and give the first known examples of hereditary (and even monotone) graph classes for which the certificates must have linear size. For unit-disk graphs we obtain a lower bound of $Ω(n^{1-δ})$ for any $δ>0$ on the size of the certificates, and an upper bound of $O(n \log n)$. The lower bounds are obtained by proving rigidity properties of the considered graphs, which might be of independent interest.

We describe a procedure for the generation of functional digraphs up to isomorphism; these are digraphs with uniform outdegree 1, also called mapping patterns, finite endofunctions, or finite discrete-time dynamical systems . This procedure is based on a reverse search algorithm for the generation of connected functional digraphs, which is then applied as a subroutine for the generation of arbitrary ones. Both algorithms output solutions with O ( n 2 ) delay and require linear space with respect to the number n of vertices.

At IPEC 2020, Bergougnoux, Bonnet, Brettell, and Kwon (Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth, IPEC 2020, LIPIcs vol. 180, pp. 3:1-3:17) showed that a number of problems related to the classic Feedback Vertex Set (FVS) problem do not admit a 2^{o(k log k)} ⋅ n^{𝒪(1)}-time algorithm on graphs of treewidth at most k, assuming the Exponential Time Hypothesis. This contrasts with the 3^{k} ⋅ k^{𝒪(1)} ⋅ n-time algorithm for FVS using the Cut&Count technique. During their live talk at IPEC 2020, Bergougnoux et al. posed a number of open questions, which we answer in this work. - Subset Even Cycle Transversal, Subset Odd Cycle Transversal, Subset Feedback Vertex Set can be solved in time 2^{𝒪(k log k)} ⋅ n in graphs of treewidth at most k. This matches a lower bound for Even Cycle Transversal of Bergougnoux et al. and improves the polynomial factor in some of their upper bounds. - Subset Feedback Vertex Set and Node Multiway Cut can be solved in time 2^{𝒪(k log k)} ⋅ n, if the input graph is given as a cliquewidth expression of size n and width k. - Odd Cycle Transversal can be solved in time 4^k ⋅ k^{𝒪(1)} ⋅ n if the input graph is given as a cliquewidth expression of size n and width k. Furthermore, the existence of a constant ε > 0 and an algorithm performing this task in time (4-ε)^k ⋅ n^{𝒪(1)} would contradict the Strong Exponential Time Hypothesis. A common theme of the first two algorithmic results is to represent connectivity properties of the current graph in a state of a dynamic programming algorithm as an auxiliary forest with 𝒪(k) nodes. This results in a 2^{𝒪(k log k)} bound on the number of states for one node of the tree decomposition or cliquewidth expression and allows to compare two states in k^{𝒪(1)} time, resulting in linear time dependency on the size of the graph or the input cliquewidth expression.

It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this article we investigate this problem in graph classes defined by forbidding an induced subgraph. In particular, we provide output-polynomial time algorithms for K t -free graphs and for several related graph classes. This answers a question of Kanté et al. about enumeration in bipartite graphs.

In [M. M. Kanté, V. Limouzy, A. Mary, and L. Nourine. On the enumeration of minimal dominating sets and related notions. SIAM Journal on Discrete Mathematics, 28(4):1916–1929, 2014.] the authors give an O(n+m) delay algorithm based on neighborhood inclusions for the enumeration of minimal dominating sets in split and P_6-free chordal graphs. In this paper, we investigate generalizations of this technique to P_k-free chordal graphs for larger integers k. In particular, we give O(n+m) and O(n^3 * m) delays algorithms in the classes of P_7-free and P_8-free chordal graphs. As for P_k-free chordal graphs for k >= 9, we give evidence that such a technique is inefficient as a key step of the algorithm, namely the irredundant extension problem, becomes NP-complete.

It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we prove that this is the case in triangle-free graphs. This answers a question of Kanté et al. Additionally, we show that deciding if a set of vertices of a bipartite graph can be completed into a minimal dominating set is a NP-complete problem.