Testing idealness of 0,1 matrices

Ahmad Abdi, London School of Economics. Part of the Algebra, Logic, and Algorithms Seminar Series.

A 0,1 matrix M is *ideal* if the set covering polyhedron {x ≥ 0 : Mx ≥ 1} is integral.  Ding, Feng, and Zang (2008) showed that testing idealness is co-NP-complete.  This was a rather surprising turn of events because, in the context of set packing polytopes, testing perfection belongs to P, which follows from the work of Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković (2005).

In the language of clutters, the hardness result states that testing clutter idealness is co-NP-complete.  The bottleneck is that given a clutter, finding an odd hole minor is an NP-hard problem.  In yet another surprising turn of events, we essentially prove that finding the blocker of an odd hole as a minor belongs to P.  Our result suggests that testing clutter idealness should become easy once the blocker is added to the input!

In this talk, I will survey the history of the problem, and talk about the new findings, which are based on the following papers:

Abdi, Cornuejols, Lee:  "Intersecting restrictions in clutters."  Combinatorica, to appear.

Abdi and Lee:  "Deltas, extended odd holes and their blockers."  JCTb (2019).