TDI Matrices

1. Given an $m\times n$ $0-1$ matrix $A$ and an $m$-dimensional vector $b$, decide whether the system $Ax\le b$ 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 $0-1$ special case of the well-known problem of TDI system recognition. Let $P:={Ax\le b, x\ge 0}$ . Let $A(u)$ be the matrix whose rows are the normal vectors of facets of $P$ containing u, each row is integer and the gcd of its entries is $1$.

There are several known relations between TDI and unimodular systems. As Serkan Hosten pointed out, `nondegenerate' TDI matrices are exactly those in which $A(u)$ is an $n\times n$ matrix having determinant $1$ for every vertex $u$.

The following problem involves unimodularity in perfectness test:

INPUT: $m\times n$ 0-1 matrix A and an $m$-dimensional positive vector $b$,

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 $A$ 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.