Total dual integrality (TDI-ness) is a major concept in attacking various combinatorial optimization problems. Here we develop several new min-max theorems and good characterizations in graph theory where the minimum cost extension is already NP-complete, implying that such problems cannot be described by TDI linear systems. The main device is a min-max theorem of Frank and Jord\'an on covering a supermodular function by digraphs.
Bibtex entry:
AUTHOR | = | {B{\'e}rczi, Krist{\'o}f and Frank, Andr{\'a}s}, |
TITLE | = | {Non-TDI graph-optimization with supermodular functions (extended abstract)}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2015}, |
NUMBER | = | {TR-2015-14} |