On neighborhood-Helly graphs
A family F of subsets of some set is intersecting when sets of F pairwise intersect. The family F is Helly when every intersecting subfamily of it contains a common element. In this paper we examine the families of vertex neighborhoods of a graph, with the aim of determining whether or not they are...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_0166218X_v216_n_p191_Groshaus |
| Aporte de: |
| id |
todo:paper_0166218X_v216_n_p191_Groshaus |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_0166218X_v216_n_p191_Groshaus2023-10-03T15:03:44Z On neighborhood-Helly graphs Groshaus, M. Lin, M.C. Szwarcfiter, J.L. Complexity Extensions Helly property NP-hardness Characterization Polynomial approximation Complexity Extensions Forbidden induced subgraphs Helly properties Induced subgraphs NP-hardness Polynomial-time Recognition algorithm Fluorine A family F of subsets of some set is intersecting when sets of F pairwise intersect. The family F is Helly when every intersecting subfamily of it contains a common element. In this paper we examine the families of vertex neighborhoods of a graph, with the aim of determining whether or not they are Helly, and also whether or nor they are hereditary Helly, that is, each of the induced subgraphs of the graph is Helly. We examine the cases where the neighborhoods are all open, or all closed, or mixed, that is, some open and some closed. For mixed neighborhoods there are two different kinds of choice of the neighborhood of each vertex to be considered: fixed or arbitrary choice. By fixed mixed neighborhood, we mean that the choice, open or closed, for the neighborhood of a vertex is known in advance, that is part of the input. On the other hand, an arbitrary choice implies that the choice can be made along the process. For the cases of open, closed and fixed mixed neighborhoods, we describe characterizations, both for the neighborhoods to be Helly and hereditary Helly. The characterizations are of two types: based on the concept of extensions, or, for the hereditary cases, by forbidden induced subgraphs. Polynomial time recognition algorithms follow directly from the characterizations. In contrast, for arbitrary mixed neighborhoods, we prove that it is NP-complete to decide whether the family of neighborhoods is Helly or hereditary Helly. © 2016 Elsevier B.V. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0166218X_v216_n_p191_Groshaus |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Complexity Extensions Helly property NP-hardness Characterization Polynomial approximation Complexity Extensions Forbidden induced subgraphs Helly properties Induced subgraphs NP-hardness Polynomial-time Recognition algorithm Fluorine |
| spellingShingle |
Complexity Extensions Helly property NP-hardness Characterization Polynomial approximation Complexity Extensions Forbidden induced subgraphs Helly properties Induced subgraphs NP-hardness Polynomial-time Recognition algorithm Fluorine Groshaus, M. Lin, M.C. Szwarcfiter, J.L. On neighborhood-Helly graphs |
| topic_facet |
Complexity Extensions Helly property NP-hardness Characterization Polynomial approximation Complexity Extensions Forbidden induced subgraphs Helly properties Induced subgraphs NP-hardness Polynomial-time Recognition algorithm Fluorine |
| description |
A family F of subsets of some set is intersecting when sets of F pairwise intersect. The family F is Helly when every intersecting subfamily of it contains a common element. In this paper we examine the families of vertex neighborhoods of a graph, with the aim of determining whether or not they are Helly, and also whether or nor they are hereditary Helly, that is, each of the induced subgraphs of the graph is Helly. We examine the cases where the neighborhoods are all open, or all closed, or mixed, that is, some open and some closed. For mixed neighborhoods there are two different kinds of choice of the neighborhood of each vertex to be considered: fixed or arbitrary choice. By fixed mixed neighborhood, we mean that the choice, open or closed, for the neighborhood of a vertex is known in advance, that is part of the input. On the other hand, an arbitrary choice implies that the choice can be made along the process. For the cases of open, closed and fixed mixed neighborhoods, we describe characterizations, both for the neighborhoods to be Helly and hereditary Helly. The characterizations are of two types: based on the concept of extensions, or, for the hereditary cases, by forbidden induced subgraphs. Polynomial time recognition algorithms follow directly from the characterizations. In contrast, for arbitrary mixed neighborhoods, we prove that it is NP-complete to decide whether the family of neighborhoods is Helly or hereditary Helly. © 2016 Elsevier B.V. |
| format |
JOUR |
| author |
Groshaus, M. Lin, M.C. Szwarcfiter, J.L. |
| author_facet |
Groshaus, M. Lin, M.C. Szwarcfiter, J.L. |
| author_sort |
Groshaus, M. |
| title |
On neighborhood-Helly graphs |
| title_short |
On neighborhood-Helly graphs |
| title_full |
On neighborhood-Helly graphs |
| title_fullStr |
On neighborhood-Helly graphs |
| title_full_unstemmed |
On neighborhood-Helly graphs |
| title_sort |
on neighborhood-helly graphs |
| url |
http://hdl.handle.net/20.500.12110/paper_0166218X_v216_n_p191_Groshaus |
| work_keys_str_mv |
AT groshausm onneighborhoodhellygraphs AT linmc onneighborhoodhellygraphs AT szwarcfiterjl onneighborhoodhellygraphs |
| _version_ |
1807324475299987456 |