TR-2008-15

Recognizing conic TDI systems is hard

Júlia Pap



Abstract

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:

@techreport{egres-08-15,
AUTHOR = {Pap, J{\'u}lia},
TITLE = {Recognizing conic TDI systems is hard},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2008},
NUMBER = {TR-2008-15}
}


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