Combinatorial optimization II
Org: Tamon Stephen (Simon Fraser University)
[PDF]

AHMAD ABDI, Carnegie Mellon University and London School of Economics
Intersecting families in Combinatorial Optimization  [PDF]

A clutter is {\it intersecting} if the members do not have a common element yet every two members intersect. Cornuejols, Guenin and Margot (2000) have conjectured that for clutters without an intersecting minor, total primal integrality and total dual integrality of the corresponding set covering linear system must be equivalent. In this talk, I will provide a polynomial characterization of clutters without an intersecting minor. I will also discuss a surprising complexity consequence of our techniques, and a connection to Woodall's Conjecture.

Joint work with Gerard Cornuejols and Dabeen Lee.

ANNE CONDON, University of British Columbia
Predicting Minimum Free Energy Structures of Multi-stranded Nucleic Acid Systems is APX--Hard  [PDF]

Given a set of DNA strands, what is the minimum free energy set of base pairs that they can form? This question is important in the field of DNA programming, since base pair interactions among multiple strands provide the means to build interesting systems with DNA, and determining structure is an important step in design and verification of such systems. We show that a simple version of this problem has no efficient approximation algorithm unless P=NP. Our hardness proof draws on coding theory and suggests new research problems in this area too. Joint work with Monir Hajiaghayi and Chris Thachuk.

TONY HUYNH, Universite libre de Bruxelles
Stable sets in graphs with no two disjoint odd cycles  [PDF]

Artmann, Weismantel and Zenklusen recently gave a strongly polynomial-time algorithm for bimodular integer programs. This implies in particular an efficient algorithm for finding maximum weight stable sets in graphs without two disjoint odd cycles. However, the AWZ algorithm does not give a polyhedral description of the stable set polytope of such graphs.

Using Lovász's characterization of graphs without two disjoint odd cycles, we construct compact extended formulations of the stable set polytopes of these graphs. We also conjecture that for each fixed $k$, maximum stable sets can be computed in polynomial-time for graphs with at most $k$ disjoint odd cycles.

DABEEN LEE, Carnegie Mellon University
Deltas, extended odd holes, and their blockers  [PDF]

Deltas, extended odd holes, and their blockers are fundamental classes of non-ideal clutters. We say that a clutter without a cover of cardinality one is dense if nonnegative weights can be assigned to the elements so that each member has its weight greater than half the sum of all weights. Deltas and the blockers of extended odd holes are examples of dense clutters. Lehman's width-length inequality implies that dense clutters are non-ideal. In this talk, we prove that every dense clutter contains a delta or the blocker of an extended odd hole as a minor.