Generating minimal redundant and maximal irredundant sets in incidence graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912916053164032 |
|---|---|
| author | Castelo, Emanuel Chalopin, Jérémie Defrain, Oscar Vilmin, Simon |
| author_facet | Castelo, Emanuel Chalopin, Jérémie Defrain, Oscar Vilmin, Simon |
| contents | 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 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_18362 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Generating minimal redundant and maximal irredundant sets in incidence graphs Castelo, Emanuel Chalopin, Jérémie Defrain, Oscar Vilmin, Simon Combinatorics Discrete Mathematics Data Structures and Algorithms 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 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 |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.18362 |