Characterization and recognition of generalized clique-Helly graphs |
| |
Authors: | Mitre C. Dourado,Fá bio Protti,Jayme L. Szwarcfiter |
| |
Affiliation: | a COPPE, Sistemas, Brazil b IM and NCE, Caixa Postal 2324, 20001-970 Universidade Federal do Rio de Janeiro Rio de Janeiro, RJ, Brazil |
| |
Abstract: | Let p?1 and q?0 be integers. A family of sets F is (p,q)-intersecting when every subfamily F′⊆F formed by p or less members has total intersection of cardinality at least q. A family of sets F is (p,q)-Helly when every (p,q)-intersecting subfamily F′⊆F has total intersection of cardinality at least q. A graph G is a (p,q)-clique-Helly graph when its family of (maximal) cliques is (p,q)-Helly. According to this terminology, the usual Helly property and the clique-Helly graphs correspond to the case p=2,q=1. In this work we present a characterization for (p,q)-clique-Helly graphs. For fixed p,q, this characterization leads to a polynomial-time recognition algorithm. When p or q is not fixed, it is shown that the recognition of (p,q)-clique-Helly graphs is NP-hard. |
| |
Keywords: | Clique-Helly graphs Helly property Intersecting sets |
本文献已被 ScienceDirect 等数据库收录! |
|