Recognizing conic TDI systems is hard

Júlia Pap


In this note we prove that the problem of deciding whether or not a set of integer vectors forms a Hilbert basis is co-NP-complete. Equivalently, deciding whether a conic linear system is totally dual integral (TDI) or not, is co-NP-complete. These are true even if the vectors in the set or respectively the coefficient vectors of the inequalities are $0-1$ vectors having at most three ones.

Bibtex entry:

AUTHOR = {Pap, J{\'u}lia},
TITLE = {Recognizing conic TDI systems is hard},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2008},
NUMBER = {TR-2008-15}

Last modification: 29.12.2020. Please email your comments to Tamás Király!