Id: arxiv/2602.18362 Url: https://arxiv.org/abs/2602.18362 Tags: math.CO, cs.DM, cs.DS Score: 0 Title: Generating minimal redundant and maximal irredundant sets in incidence graphs Domain: math.CO Source: arxiv Authors: Emanuel Castelo, Jérémie Chalopin, Oscar Defrain, Simon Vilmin Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-20 Page: https://delphi.science/r/arxiv/2602.18362 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. 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…