On the generalized Helly property of hypergraphs, cliques, and bicliques

Revista con referato

Guardado en:
Detalles Bibliográficos
Autores principales: Costa Dourado, Mitre, Grippo, Luciano Norberto, Safe, Martin Darío
Formato: Artículo publishedVersion
Lenguaje:Inglés
Publicado: Elsevier Science 2026
Materias:
Forbidden induced Subgraphs
Forbidden partial subhypergraphs
Generalized Helly Property
Helly hypergraphs
Maximal cliques
Maximal Bicliques
Recognition algorithms
Matemáticas
Matemática Aplicada
Acceso en línea:http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2671
Aporte de:
Repositorio Institucional Digital de Acceso Abierto (UNGS) de Universidad Nacional de General Sarmiento
id I71-R177-UNGS-2671
record_format dspace
spelling I71-R177-UNGS-26712026-01-14T10:57:00Z On the generalized Helly property of hypergraphs, cliques, and bicliques Costa Dourado, Mitre Grippo, Luciano Norberto Safe, Martin Darío Forbidden induced Subgraphs Forbidden partial subhypergraphs Generalized Helly Property Helly hypergraphs Maximal cliques Maximal Bicliques Recognition algorithms Matemáticas Matemática Aplicada Revista con referato Fil: Grippo, Luciano Norberto. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Fil: Grippo, Luciano Norberto. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Fil: Costa Dourado, Mitre. Universidade Federal do Rio de Janeiro; Brasil. Fil: Safe, Martin Darío. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Bahía Blanca; Argentina. Fil: Safe, Martin Darío. Universidad Nacional del Sur. Departamento de Matemática; Argentina. 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. 2026-01-14T10:57:00Z 2026-01-14T10:57:00Z 2023 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion Costa Dourado, M., Grippo, L. N. y Safe, M. D. (2023). On the generalized Helly property of hypergraphs, cliques, and bicliques. Discrete Applied Mathematics, 330, 56-77. 0166-218X http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2671 eng https://doi.org/10.1016/j.dam.2023.01.006 info:eu-repo/semantics/restrictedAccess https://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier Science Discrete Applied Mathematics. May. 2023; 330: 56-77 https://www.sciencedirect.com/journal/discrete-applied-mathematics/vol/330/suppl/C
institution Universidad Nacional de General Sarmiento
institution_str I-71
repository_str R-177
collection Repositorio Institucional Digital de Acceso Abierto (UNGS)
language Inglés
orig_language_str_mv eng
topic Forbidden induced Subgraphs
Forbidden partial subhypergraphs
Generalized Helly Property
Helly hypergraphs
Maximal cliques
Maximal Bicliques
Recognition algorithms
Matemáticas
Matemática Aplicada
spellingShingle Forbidden induced Subgraphs
Forbidden partial subhypergraphs
Generalized Helly Property
Helly hypergraphs
Maximal cliques
Maximal Bicliques
Recognition algorithms
Matemáticas
Matemática Aplicada
Costa Dourado, Mitre
Grippo, Luciano Norberto
Safe, Martin Darío
On the generalized Helly property of hypergraphs, cliques, and bicliques
topic_facet Forbidden induced Subgraphs
Forbidden partial subhypergraphs
Generalized Helly Property
Helly hypergraphs
Maximal cliques
Maximal Bicliques
Recognition algorithms
Matemáticas
Matemática Aplicada
description Revista con referato
format Artículo
Artículo
publishedVersion
author Costa Dourado, Mitre
Grippo, Luciano Norberto
Safe, Martin Darío
author_facet Costa Dourado, Mitre
Grippo, Luciano Norberto
Safe, Martin Darío
author_sort Costa Dourado, Mitre
title On the generalized Helly property of hypergraphs, cliques, and bicliques
title_short On the generalized Helly property of hypergraphs, cliques, and bicliques
title_full On the generalized Helly property of hypergraphs, cliques, and bicliques
title_fullStr On the generalized Helly property of hypergraphs, cliques, and bicliques
title_full_unstemmed On the generalized Helly property of hypergraphs, cliques, and bicliques
title_sort on the generalized helly property of hypergraphs, cliques, and bicliques
publisher Elsevier Science
publishDate 2026
url http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2671
work_keys_str_mv AT costadouradomitre onthegeneralizedhellypropertyofhypergraphscliquesandbicliques
AT grippolucianonorberto onthegeneralizedhellypropertyofhypergraphscliquesandbicliques
AT safemartindario onthegeneralizedhellypropertyofhypergraphscliquesandbicliques
_version_ 1858615829979987968

Ejemplares similares