{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-20","reactions":{}}