论文标题
关于超图，集团和双石的广义螺旋特性
On the generalized Helly property of hypergraphs, cliques, and bicliques
论文作者
论文摘要
一家家族是$（p，q）$ - 如果每个非空的亚家族的$ p $或更少的套件在其总交集中至少都有$ q $元素，则相交。一个套装的家族具有$（P，Q）$ - Helly Property，如果每个非空地$（P，Q）$ - 相交的亚家族的基数总数至少为$ Q $。 $（2,1）$ - Helly Property是通常的Helly物业。 HyperGraph为$（P，Q）$ - Helly如果其边缘家族具有$（P，Q）$ - Helly Property和Hereditary $（P，Q）$ - Helly如果其每个Subhypergraphs都有$（P，Q）$ - Helly Property。图形为$（p，q）$ - 集团 - 如果其最大集团的家族具有$（p，q）$ - Helly Property and Hereditary $（P，Q）$ - 如果其诱导的子分类为$（P，Q）$ - $ - $ - $ - $ - 列表。 $（p，q）$ - biclique-helly和遗传性$（p，q）$ - biclique-helly图的类别类似地定义。我们证明了遗传性$（P，Q）$ - Helly Hypergraphs的几个特征，其中包括最少的禁止部分subhypergraphs。我们给出了改进的时间，以识别$（P，Q）$ - Helly HyperGraphs对于每个固定$ Q $，并表明遗传$（P，Q）$ - Helly HyperGraphs可以在多项式时间内解决$ P $和$ Q $，但如果固定的（如果固定$ p $）为$ p $，则如果$ q-pume，则如果$ p $是输入的一部分，则可以解决。此外，我们将$（p，q）$ - clique-helly图概括为$ p $ -clique-helly图的表征，在扩展方面，给出了遗传性$（P，Q）$ - clique-Helly图的不同特征，包括禁止诱导的子分类。我们为识别$（p，q）$ - clique-helly图的时间限制提供了改进，并证明了遗传性$（p，q）$的识别问题 - clique-helly图形是$ p $和$ q $的多项式时间，但如果$ p $固定，但如果$ p $或$ q $ $ q $是输入的一部分，则是固定的。最后，我们提供不同的特征，提供识别算法，并证明（遗传）$（p，q）$ - biclique-helly图的硬度结果。
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)$-the 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. We prove several characterizations of hereditary $(p,q)$-Helly hypergraphs, including one by minimal forbidden partial subhypergraphs. 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 but co-NP-complete if $p$ is part of the input. In addition, we generalize to $(p,q)$-clique-Helly graphs the characterization of $p$-clique-Helly graphs in terms of expansions 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 but NP-hard if $p$ or $q$ is part of the input. Finally, we provide different characterizations, give recognition algorithms, and prove hardness results for (hereditary) $(p,q)$-biclique-Helly graphs.
