Conformal Hypergraphs: Duality and Implications for the Upper Clique Transversal Problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916240958685184 |
|---|---|
| author | Boros, Endre Gurvich, Vladimir Milanič, Martin Uno, Yushi |
| author_facet | Boros, Endre Gurvich, Vladimir Milanič, Martin Uno, Yushi |
| contents | Given a hypergraph $\mathcal{H}$, the dual hypergraph of $\mathcal{H}$ is the hypergraph of all minimal transversals of $\mathcal{H}$. The dual hypergraph is always Sperner, that is, no hyperedge contains another. A special case of Sperner hypergraphs are the conformal Sperner hypergraphs, which correspond to the families of maximal cliques of graphs. All these notions play an important role in many fields of mathematics and computer science, including combinatorics, algebra, database theory, etc. In this paper we study conformality of dual hypergraphs and prove several results related to the problem of recognizing this property. In particular, we show that the problem is in co-NP and can be solved in polynomial time for hypergraphs of bounded dimension. In the special case of dimension $3$, we reduce the problem to $2$-Satisfiability. Our approach has an implication in algorithmic graph theory: we obtain a polynomial-time algorithm for recognizing graphs in which all minimal transversals of maximal cliques have size at most $k$, for any fixed $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_00098 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Conformal Hypergraphs: Duality and Implications for the Upper Clique Transversal Problem Boros, Endre Gurvich, Vladimir Milanič, Martin Uno, Yushi Combinatorics Computational Complexity Discrete Mathematics Data Structures and Algorithms 05C65, 05D15, 05C69 (Primary), 05C85, 68R10, 05-08 (Secondary) Given a hypergraph $\mathcal{H}$, the dual hypergraph of $\mathcal{H}$ is the hypergraph of all minimal transversals of $\mathcal{H}$. The dual hypergraph is always Sperner, that is, no hyperedge contains another. A special case of Sperner hypergraphs are the conformal Sperner hypergraphs, which correspond to the families of maximal cliques of graphs. All these notions play an important role in many fields of mathematics and computer science, including combinatorics, algebra, database theory, etc. In this paper we study conformality of dual hypergraphs and prove several results related to the problem of recognizing this property. In particular, we show that the problem is in co-NP and can be solved in polynomial time for hypergraphs of bounded dimension. In the special case of dimension $3$, we reduce the problem to $2$-Satisfiability. Our approach has an implication in algorithmic graph theory: we obtain a polynomial-time algorithm for recognizing graphs in which all minimal transversals of maximal cliques have size at most $k$, for any fixed $k$. |
| title | Conformal Hypergraphs: Duality and Implications for the Upper Clique Transversal Problem |
| topic | Combinatorics Computational Complexity Discrete Mathematics Data Structures and Algorithms 05C65, 05D15, 05C69 (Primary), 05C85, 68R10, 05-08 (Secondary) |
| url | https://arxiv.org/abs/2309.00098 |