{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreignnvheoqhh72mjqdutykc22iqc5daqf7vy7642xmxjry5cuagogi",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mfj46c3mwkw2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.18362v1",
  "publishedAt": "2026-02-23T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Emanuel Castelo",
    "Jérémie Chalopin",
    "Oscar Defrain",
    "Simon Vilmin"
  ],
  "textContent": "**Authors:** Emanuel Castelo, Jérémie Chalopin, Oscar Defrain, Simon Vilmin\n\nIt 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 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, and that it is tractable on $(C_3,C_5,C_6,C_8)$-free graphs, a class of graphs incomparable to strongly orderable graphs, and which also generalizes chordal bipartite graphs.",
  "title": "Generating minimal redundant and maximal irredundant sets in incidence graphs"
}