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.