The complexity of recognizing linear systems with certain integrality properties
The complexity of recognizing linear systems with certain integrality properties
复制标题
DOI：
10.1007/s10107-007-0103-y
复制
发表时间：
2008-04
影响因子：
2.7
通讯作者：
G. Ding;Li Feng;Wenan Zang
中科院分区：
文献类型：
--
作者：
G. Ding;Li Feng;Wenan Zang
取一个0 - 1矩阵，每列正好有两个1，取全一向量。我们证明了判定线性系统(1)是否定义了一个积分多面体，(2)是否为完全对偶积分（TDI），以及(3)盒-完全对偶积分（box-TDI）是否都是共np完全的问题，从而证实了Edmonds和Giles（1984）关于识别TDI系统的np -硬度猜想。
LetAbe a 0 − 1 matrix with precisely two 1’s in each column and let1be the all-one vector. We show that the problems of deciding whether the linear system(1) defines an integral polyhedron,(2) is totally dual integral (TDI), and(3) box-totally dual integral (box-TDI)are all co-NP-complete, thereby confirming the conjecture on NP-hardness of recognizing TDI systems made by Edmonds and Giles in 1984.