Artículo
On the generalized Helly property of hypergraphs, cliques, and bicliques
Fecha de publicación:
05/2023
Editorial:
Elsevier Science
Revista:
Discrete Applied Mathematics
ISSN:
0166-218X
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
A family of sets is (p,q)-intersecting if every nonempty subfamily of p or fewer sets has at least q elements in its total intersection. A family of sets has the (p,q)-Helly property if every nonempty (p,q)-intersecting subfamily has total intersection of cardinality at least q. The (2,1)-Helly property is the usual Helly property. A hypergraph is (p,q)-Helly if its edge family has the (p,q)-Helly property and hereditary (p,q)-Helly if each of its subhypergraphs has the (p,q)-Helly property. A graph is (p,q)-clique-Helly if the family of its maximal cliques has the (p,q)-Helly property and hereditary (p,q)-clique-Helly if each of its induced subgraphs is (p,q)-clique-Helly. The classes of (p,q)-biclique-Helly and hereditary (p,q)-biclique-Helly graphs are defined analogously. In this work, we prove several characterizations of hereditary (p,q)-Helly hypergraphs, including one by minimal forbidden partial subhypergraphs. On the algorithmic side, we give an improved time bound for the recognition of (p,q)-Helly hypergraphs for each fixed q and show that the recognition of hereditary (p,q)-Helly hypergraphs can be solved in polynomial time if p and q are fixed and co-NP-complete if p is part of the input. In addition, we generalize the characterization of p-clique-Helly graphs in terms of expansions to (p,q)-clique-Helly graphs and give different characterizations of hereditary (p,q)-clique-Helly graphs, including one by forbidden induced subgraphs. We give an improvement on the time bound for the recognition of (p,q)-clique-Helly graphs and prove that the recognition problem of hereditary (p,q)-clique-Helly graphs is polynomial-time solvable for p and q fixed and NP-hard if p or q is part of the input. Finally, we provide different characterizations, give recognition algorithms, and prove hardness results for (p,q)-biclique-Helly graphs and hereditary (p,q)-biclique-Helly graphs which are analogous to those for (p,q)-clique-Helly and hereditary (p,q)-clique-Helly graphs.
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(INMABB)
Articulos de INST.DE MATEMATICA BAHIA BLANCA (I)
Articulos de INST.DE MATEMATICA BAHIA BLANCA (I)
Articulos(SEDE CENTRAL)
Articulos de SEDE CENTRAL
Articulos de SEDE CENTRAL
Citación
Costa Dourado, Mitre; Grippo, Luciano Norberto; Safe, Martin Dario; On the generalized Helly property of hypergraphs, cliques, and bicliques; Elsevier Science; Discrete Applied Mathematics; 330; 5-2023; 56-77
Compartir
Altmétricas