Intersecting and dense restrictions of clutters in polynomial time
成果类型：
Article
署名作者：
Drees, Martin
署名单位：
University of Bonn
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-023-02034-3
发表日期：
2024
页码：
461-477
关键词：
摘要：
A clutter is a family of sets, called members, such that no member contains another. It is called intersecting if every two members intersect, but not all members have a common element. Dense clutters additionally do not have a fractional packing of value 2. We are looking at certain substructures of clutters, namely minors and restrictions. For a family of clutters we introduce a general sufficient condition such that for every clutter we can decide whether the clutter has a restriction in that set in polynomial time. It is known that the sets of intersecting and dense clutters satisfy this condition. For intersecting clutters we generalize the statement to k-wise intersecting clutters using a much simpler proof. We also give a simplified proof that a dense clutter with no proper dense minor is either a delta or the blocker of an extended odd hole. This simplification reduces the running time of the algorithm for finding a delta or the blocker of an extended odd hole minor from previously O(n(4)) to O(n(3)) filter oracle calls.