Enumerating minimal dominating sets and variants in chordal bipartite graphs
Emanuel Castelo, Oscar Defrain, Guilherme C. M. Gomes · 2025
Read Enumerating minimal dominating sets and variants in chordal bipartite graphs by Emanuel Castelo, Oscar Defrain, Guilherme C. M. Gomes (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-14611.txt.
Introduction
Emanuel Castelo, Oscar Defrain, and Guilherme Gomes speed up the listing of minimal guard sets in a special graph family, in a 2025 paper. A dominating set is a group of nodes such that every node is in the group or next to one. Listing all minimal such sets fast, with steady gaps between outputs, is a long-open problem even for two-sided graphs.
For chordal bipartite graphs, whose cycles all carry chords, older methods only promised steadily growing total time. The new algorithm lists minimal dominating sets with true polynomial delay and modest memory. Two variants, total and connected sets, also get fast algorithms here. The authors further show their tricks cannot stretch to harder graph classes unchanged.
Catalog record
| CREATOR | Emanuel Castelo, Oscar Defrain, Guilherme C. M. Gomes |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-14611
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Enumerating minimal dominating sets and variants in chordal bipartite graphs Thanks: The second author is supported by the ANR project PARADUAL (ANR-24-CE48-0610-01). The last author is supported by the European Union, project PACKENUM, grant number 101109317. Views and opinions expressed are however those of the author only and do not necessarily reflect those of the European Union. Neither the European Union nor the granting authority can be held responsible for them. Emanuel Castelo, Oscar Defrain, Guilherme C. M. Gomes Abstract 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 𝖯 = 𝖭𝖯 \mathsf{P=NP} , and show that enumerating minimal connected dominating sets in bipartite graphs is harder than enumerating minimal transversals in general hypergraphs. Keywords: algorithmic enumeration, minimal dominating sets, connected dominating sets, total dominating sets, chordal bipartite graphs, sequential method, polynomial delay. 1 Introduction Hypergraphs are encountered in countless areas of computer science or discrete mathematics. Formally, they consist of a pair \mathcal{H}=(V(\mathcal{H}),E(\mathcal{H})) where V(\mathcal{H}) is a set of elements called vertices , and E(\mathcal{H}) is a family of subsets of V(\mathcal{H}) called hyperedges (or simply edges). Hypergraphs are known as graphs when their edges are of size precisely two. A transversal in a hypergraph \mathcal{H} is a set T\subseteq V(\mathcal{H}) which intersects every edge of \mathcal{H} . It is called minimal if it is inclusion-wise minimal, i.e., if none of its proper subsets is a transversal. The problem of enumerating the minimal transversals of a hypergraph, usually denoted by Trans-Enum , is one of the most important problems in algorithmic enumeration, for it has far-reaching implications in various areas of computer science such as logic, database theory, data profiling, or artificial intelligence [ KPS93 , EG95 , GMKT97 , BFL+22 ] ; we refer the reader to [ EG95 ] and the surveys [ EMG08 , GDVL17 ] for a comprehensive overview on the fundamental and practical aspects of this problem. In a typical enumeration problem such as Trans-Enum , a first observation to be made is that the number of solutions can be exponential in both n , the number of vertices, and m , the number of edges. Thus, asking for running times which are polynomial in n+m is meaningless. Rather, we are interested in algorithms performing in output-polynomial time, i.e., that run in a time which is polynomial in both the input size, and the output size. More strict notions of tractability can be required, such as incremental-polynomial times, and polynomial delay. We say that an algorithm runs in incremental-polynomial time if it produces the i^{\text{th}} solution in a time which is polynomial in the input size plus i . An algorithm is said to run with polynomial delay if the times before the first output, after the last output, and in between two consecutive outputs are bounded by a polynomial in the input size only. To date, the best-known algorithm solving Trans-Enum is due to Fredman and Khachiyan [ FK96 ] and runs in quasi-polynomial incremental time. Since then, output-polynomial time algorithms were obtained for several important classes, including those generalizing that of bounded degree [ EGM03 ] , or bounded edge size [ KBEG07 ] . Dominating sets are among the most studied objects in graphs. A dominating set in a graph G is a set D\subseteq V(G) such that every vertex is either in D , or adjacent to a vertex of D . Again, it is called minimal if it is inclusion-wise minimal. The problem of enumerating minimal dominating sets in graphs is denoted by Dom-Enum . Note that being a dominating set of G can be rephrased as being a transversal of each closed neighborhood of G , so, Dom-Enum is a special case of Trans-Enum with a linear number of hyperedges. The problem Dom-Enum has gained lots of interest since it has been shown, perhaps surprisingly, to be polynomially equivalent to Trans-Enum , even when restricted to cobipartite graphs [ KLMN14 ] . In particular, this work has initiated a fruitful line of research of characterizing which graph classes admit output-polynomial algorithms, in the hope of better understanding the underlying structure that makes Trans-Enum tractable. For example, polynomial-delay algorithms were obtained for various graph classes including chordal graphs [ KLM+15a ] (with linear delay on some subclasses [ KLMN14 , DN19 ] ), graphs of bounded degeneracy [ EGM03 ] , line graphs [ KLM+15b ] , graphs of bounded clique-width [ Cou09 ] , or graph classes related to permutation graphs and their generalizations [ KLMN12 , GHK+18 , BDMN20 ] . Incremental-polynomial time algorithms were obtained for graphs of bounded conformality [ KBEG07 ] , C_{\leq 6} -free graphs [ GHKV15 ] , chordal bipartite graphs [ GHK+16a ] , (C_{4},C_{5},\text{claw}) -free graphs [ KLMN12 ] , or graphs arising in geometrical contexts [ ERR19 , GHK+18 ] including unit-disks and unit-square graphs. Output-polynomial time algorithms are known for \log n -degenerate graphs [ EGM03 ] , or graphs of bounded clique number [ BDH+20 ] . In [ KLMN14 ] , the authors also include two natural variants of domination in their study: total and connected dominating sets. A total dominating set is a set D such that every vertex of G has a neighbor in D . In other words, elements of D cannot “dominate” themselves and need a neighbor in the set. A connected dominating set is a dominating set that induces a connected subgraph. Note that any connected dominating set is a total dominating set, as long as it has more than one element, making the intersection of these two notions irrelevant to study. Perhaps not surprisingly, the authors in [ KLMN14 ] show that the problems of enumerating minimal total and connected dominating sets, denoted TDom-Enum and CDom-Enum , respectively, are equivalent to Trans-Enum when restricted to split graphs. These equivalences on a relatively restricted graph class suggest that these variants of Dom-Enum are challenging, and may explain why they have received less attention in the literature. Regarding total dominating sets, a first observation is that they are transversals of open neighborhoods. This implies an incremental quasi-polynomial time algorithm for the problem using the results of Fredman and Khachiyan [ FK96 ] . However, few output-polynomial time algorithms are known for specific instances of TDom-Enum . Among them, we cite the class of chordal bipartite graphs, which admits a polynomial-delay algorithm for the problem [ GHK+16a ] Concerning connected dominating sets, it is not known whether the problem