1. Given an matrix and an -dimensional vector , decide whether the system is totally dual integral (TDI), that is, is there an integer dual solution for every objective function for which the dual optimum exists.
This is the special case of the well-known problem of TDI system recognition. Let . Let be the matrix whose rows are the normal vectors of facets of containing u, each row is integer and the gcd of its entries is .
There are several known relations between TDI and unimodular systems. As Serkan Hosten pointed out, `nondegenerate' TDI matrices are exactly those in which is an matrix having determinant for every vertex .
The following problem involves unimodularity in perfectness test:
INPUT: 0-1 matrix A and an -dimensional positive vector ,
QUESTION: Is the matrix A(u) for every vertex u of P a square matrix of determinant 1 ?
2. Can this problem be solved in polynomial time ?
For reducing the test for the perfectness of matrix to this problem define b with a 'lexicographic perturbation' from the all 1 objective function.
Contributed by András Sebo
Back to the main index for Perfect Graphs.