Article ID Journal Published Year Pages File Type
10332152 Information Processing Letters 2005 4 Pages PDF
Abstract
In this work we consider the problem of determining whether a hypergraph has the p-Helly property, when the considered subfamilies are limited by a size k. That is, whether every partial hypergraph with at most k edges is p-Helly. Further, we study the related problem applied to the cliques of a graph. In all cases, depending on the values of p and k, either we show that the problem can be solved in polynomial time, or we describe a NP-hardness proof.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,