2026-08-21T18:02:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27427 2026-08-21T14:42:39Z ddc:004 open_access

Generating Minimal Redundant and Maximal Irredundant Sets in Incidence Graphs Castelo, Emanuel Chalopin, Jérémie Defrain, Oscar Vilmin, Simon Enumeration algorithms maximal irredundant sets minimal redundant sets incidence graphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emanuel Castelo and Jérémie Chalopin and Oscar Defrain and Simon Vilmin 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.46 urn:nbn:de:0030-drops-274277 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.46 eng https://creativecommons.org/licenses/by/4.0/legalcode