A Characterization of Perfect {0, ±1}-Matrices

Kazutoshi Ando Institute of Policy and Planning Sciences University of Tsukuba Tsukuba, Ibaraki 305, Japan

March 12, 1997

Abstract The concept of perfect {0, ±1}-matrix was introduced recently as a generalization of perfect {0, 1}-matrices. A {0, ±1}-matrix A is called perfect if the associated generalized set-packing polytope

P (A) = {x | 0 ≤ x ≤ 1, Ax ≤ 1 − n(A)}

is integral, where n(A) denote the vector which r-th component is the number of negative components in the r-th row of A. Several characterizations for perfect {0, ±1}-matrices are already known. Here, we associate a bidirected graph for a {0, ±1}-matrix in an obvious way and give a simple characterization of perfect {0, ±1}-matrices in terms of bidirected graphs.

1. Introduction

Let A be a {0, ±1}-matrix of size m × n. The generalized set-packing polytope P (A) associated with A is defined as

P (A) = {x | x ∈ R^{n}, 0 ≤ x ≤ 1, Ax ≤ 1 − n(A)},  (1.1)

where for any scalar γ ∈ R we denote by γ the vector of dimension m which component are all γ and n(A) denotes the vector which r-th component is the number of negative components in the r-th row of A. A {0, ±1}-matrix is called perfect if its associated generalized set-packing polytope P (A) is integral. The concept of perfectness was introduced by Conforti, Cornuèjols and de Francesco [6]. Perfect matrices encompass a large variety of classes of {0, ±1}-matrices related to integral polyhedra such as totally unimodular matrices and balanced {0, ±1}-matrices ([15]; see also [5]).

Recent years, perfect {0, ±1}-matrices have received considerable attention and several authors gave characterizations of perfectness. Conforti, Cornuéjols and de Francesco [6] and Guenin [9] characterized perfectness in terms of associated {0, 1}- matrices. Boros and Čepek [2] gave a characterization is in terms of an associated undirected graph.

Let us recall a characterization of perfect {0, 1}-matrices. For a {0, 1}-matrix with m rows and n columns, we associate a graph G_{A} which has the vertex set as the set of column indices V = {1, ⋯, n} and has an edge {v, w} if and only if there is a row a_{r} = (α_{r1}, ⋯, α_{rn}) of A such that a_{r} covers {v, w}, i.e., we have α_{rv} = α_{rw} = 1. A graph G is called perfect if for any induced subgraph G′ the clique number ω(G′) of G′ (the maximum size of a clique of G′) is equal to the chromatic number χ(G′) of G′ (the minimum number of pairwise disjoint stable sets of G′) (see, e.g., [13]).

Theorem 1.1 (Chvátal [4], Fulkerson [8], Lovász [13]): A {0, 1}-matrix A is perfect if and only if

(i) The associated graph G_{A} is perfect, and
(ii) Each maximal clique of G_{A} appears as a row of A.
□

The purpose of this paper is to give a complete analogue of Theorem 1.1, where we associate a bidirected graph ([7]; see also [12]) for each {0, ±1}-matrix and characterize the perfectness in terms of the bidirected graph. (Boros and Čepek’s characterization [2] has similar flavor as Theorem 1.1. However, they associate with a {0, ±1}-matrix an undirected graph, which construction seems less obvious.)

A bidirected graph G = (V, A) is defined as a pair of a finite set V called vertex set and a finite set A called arc set, where for arc a ∈ A either a has two tails v and w, a has two heads v and w, or a has one tail v and one head w. (Later, we will give another pricise definition of bidirected graph.) For any {0, ±1}-matrix A of size m × n, we associate a bidirected graph G_{A} = (V, A), where V = {1, ⋯, n} and the arc set A is defined as follows:

(i) there is an arc a ∈ A which has two tails v and w if and only if there is a
row a_{r} of A such that α_{rv} = α_{rw} = 1.
(ii) there is an arc a ∈ A which has two heads v and w if and only if there is a
row a_{r} of A such that α_{rv} = α_{rw} = −1.
(iii) there is an arc a ∈ A which has one tail v and one head w if and only if
there is row a_{r} of A such that α_{rv} = −α_{rw} = 1.

A crucial step for proving the analogue of Theorem 1.1 is the characterizations of perfect bidirected graph obtained recent years ([10], [14]). This corresponds to the polyhedral characterization of perfect graphs of Chvátal [4] in the proof of Theorem 1.1. The rest of the proof of our result is not so immediate as in the case for {0, 1}-matrices. Another important step is the reduction of {0, ±1}-matrices used by Boros and Čepek [2]. However, for our purpose, the reduction of Boros and Čepek [2] is not enough. We must further reduce {0, ±1}-matrices.

Our characterization has the following features as was the case for Theorem 1.1:

(i) The associated bidirected graph is naturally defined; and (ii) Our characterization gives an insight to structures of integral generalized set-packing polytopes. Also, our characterization, if specialized to {0, 1}-matrices, is easily seen to yield Theorem 1.1.

The remaining sections of this paper are organized as follows. In Section 2 we review the concept of bidirected graph and the characterizations of bidirected graphs. In Section 3 we describe the reduction of {0, ±1}-matrices obtained in [2] (see also [3]). Finally, in Section 4 we describe a further reduction step for {0, ±1}- matices and prove the main theorem characterizing perfect {0, ±1}-matrices.

2. Perfect Bidirected Graphs

In this section we review concepts and results concerned with bidirected graphs. Characterizations of perfect bidirected graphs of Sewell [14] and of Ikebe and Tamura [10] are of particular importance.

2.1. Bidirected graphs

A bidirected graph G = (V, B; ∂) consists of a finite set V called the vertex set and a finite set B called the arc set, and ∂: B → Z^{V}, where for each b ∈ B there exists two vertices v and w such that we have either

(i) ∂b = χ_{v} + χ_{w} (b has two tails v and w),
(ii) ∂b = −χ_{v} − χ_{w} (b has two heads v and w), or
(iii) ∂b = χ_{v} − χ_{w} (b has one tail v and one head w),

where χ_{w} ∈ R^{V} is defined as

χ_{w}(v) = \{ \begin{matrix}1 & if v = w \\ 0 & otherwise \end{matrix} (v ∈ V),  (2.1)

for any w ∈ V. Throughout this paper, we assume v ≠ w for (iii). If b = ±v ± w, we say b is incident to v (and w) and if the coefficient of v is positive (respectively, negative), b is said to be positively (respectively, negatively) incident to v. Two arcs b_{1} and b_{2} are called oppositely incident to v if b_{1} and b_{2} are incident to a common vertex v but with opposite signs.

We associate polytope P (G) with a bidirected graph G = (V, B; ∂) defined as

P (G) = {x | x ∈ R^{V} , 0 ≤ x ≤ 1, ∀b ∈ B: ⟨∂b, x⟩ ≤ 1 − n(∂b)},  (2.2)

where ⟨·, ·⟩ denotes the canonical inner product and for any z ∈ {0, ±1}^{V} we denote by n(z) the number of −1’s in z. An integral vector in P (G) is called a solution of G. Let P_{I}(G) be the convex hull of the solutions of G.

For a finite set V let us denote by 3^{V} the set of ordered pair of disjoint subsets of V, i.e., 3^{V} = {(X, Y) | X, Y ⊆ V, X ∩ Y = ∅}. Each element (X, Y) of 3^{V} naturally corresponds to a {0, ±1}-vector χ_{(X,Y)} defined as

χ_{(X,Y)}(v) = \{ \begin{matrix}1 & if v ∈ X \\ −1 & if v ∈ Y \\ 0 & otherwise \end{matrix} (v ∈ V)  (2.3)

and conversely. Vector χ_{(X,Y)} is called the characteristic vector of (X, Y). We also call each element in 3^{V} a signed subset of V.

For any two signed subsets (X_{1}, Y_{1}), (X_{2}, Y_{2}) ∈ 3^{V}, if X_{1} ⊆ X_{2} and Y_{1} ⊆ Y_{2}, we write (X_{1}, Y_{1}) ⊑ (X_{2}, Y_{2}).

For a {0, ±1}-matrix A of size m × n we associate a bidirected graph G_{A} as follows. G_{A} has the vertex set as the set of columns V = {1, ⋯, n} and there is an arc b of G_{A} if and only if there is a row a_{r} of A such that a_{r} covers ∂b, i.e., ∂b ⊑ a_{r}. We call G_{A} the quadratic covering (bidirected) graph of {0, ±1}-matrix A (see [3]).

Let P_{I}(A) be the integer hull of P (A), i.e., the convex hull of the integral vectors in P (A).

Proposition 2.1 ([3]): Let A be a {0, ±1}-matrix and G_{A} its quadratic covering graph. Then we have

P (A) ⊆ P (G_{A}),  (2.4)
P_{I}(A) = P_{I}(G_{A}).  (2.5)
□

Note that we may have a strict inclusion in (2.4), e.g., P (G_{A}) is always nonempty (since \frac{1}{2} ∈ P (G_{A})) while P (A) can be empty.

For a bidirected graph G an alternate sequence of arcs and vertices

P = (v_{0}, b_{1}, v_{1}, ⋯, b_{l}, v_{l})  (2.6)

of G is called a path of G if

(i) b_{1} is incident to v_{0} and b_{l} is incident to v_{l}.
(ii) b_{i} and b_{i+1} oppositely incident to v_{i} for i = 1, ⋯, l − 1.

A path is called cycle if v_{0} = v_{l}. A bidirected graph is called acyclic if it contains no cycle.

A bidirected graph G is called transitively closed if for any two arcs b_{1} and b_{2} oppositely incident to a vertex v there exists an arc b_{3} of G such that ∂b_{3} = ∂b_{1}+∂b_{2}.

The transitive closure of G = (V, B; ∂) is the minimal transitively closed bidirected graph G^{∗} = (V, B^{∗}, ∂^{∗}) with B ⊆ B^{∗} and ∂ being the restriction of ∂^{∗}. It is obvious that the set of solutions of G coincides with the set of solutions of G^{∗}, and hence,

Proposition 2.2: For any bidirected graph G we have

P_{I}(G) = P_{I}(G^{∗})  (2.7)
□

2.2. Perfect bidirected graphs

We call an acyclic and transitively closed bidirected graph closed bidirected graph for short.

For a closed bidirected graph G, a signed subset (X, Y) ∈ 3^{V} is called a biclique ([11]) if for each distinct v, w ∈ X ∪ Y there is an arc b of G such that ∂b = ±v ± w and ⟨∂b, (X, Y)⟩ = 2. The bicliques ({v}, ∅), (∅, {v}) (v ∈ V) are called trivial. A biclique of G is strong ([11]) if there is no vertex v ∈ V − (X ∪ Y) of G such that

(i) for each w ∈ X there exists an arc b of G such that ∂b = χ_{w} ± v, and
(ii) for each w ∈ Y there exists an arc b of G such that ∂b = −χ_{w} ± v.

Theorem 2.3 (Johnson and Padberg [11]): Let G = (V, B; ∂) be a closed bidirected graph. Then we have

(i) P_{I}(G) is full-dimensional.
(ii) For each strong biclique (X, Y) of G, inequality x(X) − x(Y) ≤ 1 − |Y | indu-
ces a facet of P_{I}(G),

where x(Z) = ∑_{v∈Z} x(v) for any Z ⊆ V. □

A closed bidirected graph G is called perfect ([11]) if for each {0, ±1}-vector c: V → {0, ±1}, two objective function values of the following dual linear programming problems are equal.

(P) | \begin{matrix}Maximize & ∑_{v∈V} c(v)x(v) \\ s.t. & x(X) − x(Y) ≤ 1 − |Y | ((X, Y) ∈ S(G)). \end{matrix}  (2.8)

(D) | \begin{matrix}Minimize & ∑_{(X,Y)∈S(G)}(1 − |Y |)λ_{(X,Y)} \\ s.t. & ∑_{(X,Y)∈S(G),v∈X} λ_{(X,Y)} − ∑_{(X,Y)∈S(G),v∈Y} λ_{(X,Y)} ≥ c(v) (v ∈ V), \end{matrix}

(2.9)

where S(G) denote the set of strong bicliques of G.

The following theorem was conjectured by Johnson and Padberg [11] in 1982 and proved by Sewell [14] only recently. For a bidirected graph G = (V, B; ∂) the underlying graph \underline{G} = (V, E) of G is the (undirected) graph which edge set E is defined by

E = {{v, w} | ∃b ∈ B: ∂b = ±χ_{v} ± χ_{w}}.  (2.10)

That is, \underline{G} is the undirected graph disregarding the incidence relation of every arc of G.

Theorem 2.4 (Sewell [14]): A closed bidirected graph G is perfect if and only if its underlying graph \underline{G} is perfect. □

For a closed bidirected graph G define a polytope Q(G) ⊆ R^{V} as

Q(G) = {x|x ∈ R^{V} , x(X)−x(Y) ≤ 1−|Y | ((X,Y): a strong biclique of G)}. (2.11)

Ikebe and Tamura [10] characterized bidirected graph G for which Q(G) is integral.

Theorem 2.5 (Ikebe and Tamura [10]): For a closed bidirected graph G, Q(G) is integral if and only if its underlying graph \underline{G} is perfect. □

Combining the two theorems above we obtain the following, which is crucial for deriving our main theorem.

Corollary 2.6: Suppose G is a closed bidirected graph. Then, G is perfect if and only if Q(G) is integral. □

3. Horn Matrices

In this section we review a sequence of reductions of a {0, ±1}-matrix developed in [2].

3.1. Horn matrices

Let A be a {0, ±1}-matrix of size m × n. Then, we have either

(i) P (A) is empty (A is trivially perfect),
(ii) P (A) is nonempty while P (A) ∩ {0, 1}^{V} is empty (A is not perfect), or
(iii) P (A) ∩ {0, 1}^{V} ≠ ∅.
(3.1)

Lemma 3.1 ([3]; see also [2, Corollary 2.2]): There is an O(mn) algorithm that checks which case of (i)∼(iii) in (3.1) occurs, and finds a vector x^{∗} ∈ P (A) ∩ {0, 1}^{V} if Case (iii) occurs. □

A {0, ±1}-matrix A is disguised Horn ([3]) if P (A) ∩ {0, 1}^{V} ≠ ∅. It follows from Lemma 3.1 that we only have to consider disguised Horn matrices. Suppose that A is disguised Horn and x^{∗} ∈ P (A) ∩ {0, 1}^{V}. (Such a vector x^{∗} can be found in O(mn) time.) Define S ⊆ V by

S = {v | v ∈ V, x^{∗}(v) = 1}.  (3.2)

Let A′ be a {0, ±1}-matrix obtained from A by multiplying −1 for each column v ∈ S. Then the mapping P (A) ∋ x ↦ x′ ∈ P (A′) defined by

x′(v) = \{ \begin{matrix}1 − x(v) & if v ∈ S \\ x(v) & otherwise \end{matrix} (v ∈ V)  (3.3)

gives an isomorphism between polyhedra P (A) and P (A′). In particular, P (A) is integral if and only if P (A′) is integral. Therefore, our attention may be restricted to such a matrix A′ that we have 0 ∈ P (A′).

We call a {0, ±1}-matrix A Horn ([2]) if 0 ∈ P (A), or equivalently, n(A) ≤ 1.

3.2. Horn matrices with no forced zero

Let A be a Horn matrix. For each row r = 1, ⋯, m of A let us denote by N_{r} the set of column indices for which r-th row of A has positive entries, i.e.,

N_{r} = {v | v ∈ V, α_{rv} = 1},  (3.4)

where α_{rv} is the (r, v) component of matrix A. Let us consider the quadratic covering graph G_{A} of A. Since A is Horn, there is no two-head arcs in G_{A}. Let the directed graph D_{A} obtained by deleting all the two-tail arcs of the quadratic covering (bidirected) graph G_{A}^{1}. Suppose that C_{1}, ⋯, C_{s} are the strongly connected component of directed graph D_{A} (or equivalently, strongly connected component of bidirected graph G_{A} (see [1])).

Lemma 3.2 ([2, Corollary 3.2]): Let A be a Horn matrix and x ∈ P (A). Then, for each strong component C_{t} (t = 1, ⋯, s) of D_{A}, x is constant on C_{t}, i.e., we have x(v) = x(w) for v, w ∈ C_{t}. □

Horn matrix A is said to have no forced zero if there exits a vector x ∈ P (A) such that x(v) > 0 for each v ∈ V.

Let A be a Horn matrix of size m × n. For each row a_{r} (r = 1, ⋯, m) of A with n(a_{r}) = 1 let us denote by c(r) the unique column index for which a_{r} has the negative entry.

1The definition of D_{A} is slightly different from that in [2]. However, the difference is inessential.

Lemma 3.3 ([2, Lemmas 3.3, 3.4 and 3.6]): Let A be a Horn matrix of size m × n. Then A has no forced zero if and only if for each row a_{r} (r = 1, ⋯, m) of A with n(a_{r}) = 1 we have

(i) |N_{r}| = 1, or
(ii) For the strong component C_{t} containing c(r) we have N_{r} ∩ C_{t} = ∅.
□

Lemma 3.4 ([2, Corollary 3.7]): Given an m × n Horn matrix A, one can obtain in O(mn) time another Horn matrix A′ of size m′ × n′ (m′ ≤ m and n′ ≤ n) which has no forced zero. Moreover, P (A′) is integral if and only if P (A) is integral. □

3.3. Non-reconverging Horn matrices

Let us denote by U_{v} the set of vertices reachable from vertex v in the directed graph D_{A}, i.e.,

U_{v} = {w | w ∈ V, there is a path from v to w}.  (3.5)

A Horn matrix A is said to reconverge from vertex v if there exists a row r of A such that |N_{r} ∩ U_{v}| ≥ 2. A is called non-reconverging if there is no such vertex.

Lemma 3.5 ([2, Lemma 4.1]): Let A be a Horn matrix with no forced zero and which is reconverging from a vertex v. Then, P (A) is not integral. □

Boros and Čepek also showed that non-reconverging property of a Horn matrix with no forced zero can be checked in O(n^{2}m) time. It follows from Lemma 3.5 that it suffices to consider non-reconverging Horn matrices with no forced zero.

4. Perfect {0, ±1}-Matrices

Let A be a non-reconverging Horn matrix with no forced zero and D_{A} be the directed graph after deleting the two-tail arcs of the quadratic covering graph G_{A} of A. Let us note that for each strongly connected component C_{t} (t = 1, ⋯, s) of D_{A} and each row r of A we have |N_{r} ∩ C_{t}| ≤ 1 by the definition of non-reconverging property. Let us define an (apparently Horn) matrix A′ of size m × s by

α′_{rt} = \{ \begin{matrix}1 & if |N_{r} ∩ C_{t}| = 1 and c(r) ∉ C_{t} \\ −1 & if N_{r} ∩ C_{t} = ∅ and c(r) ∈ C_{t} \\ 0 & otherwise \end{matrix} (r = 1, ⋯, m; t = 1, ⋯, s). (4.1)

For each strong component C_{t} (t = 1, ⋯, s) of D_{A}, choose an arbitrary but fixed vertex v_{t} ∈ C_{t}. Given an x ∈ R^{V}, we define x′ ∈ R^{s} as

x′(t) = x(v_{t}) (t = 1, ⋯, s).  (4.2)

Conversely, for any x′ ∈ R^{s} we define x ∈ R^{V} as

x(v) = x′(t) (v ∈ C_{t}, t = 1, ⋯, s).  (4.3)

Lemma 4.1: Let A be a non-reconverging Horn matrix with no forced zero and A′ be defined in (4.1). Then x ∈ P (A) if and only if x′ ∈ P (A′), where x ∈ R^{V} and x′ ∈ R^{s} correspond under relations (4.2) and (4.3). (Proof) We prove for each row index r = 1, ⋯, m we have a_{r}x ≤ 1 − n(a_{r}) if and only if a′_{r}x′ ≤ 1 − n(a′_{r}). Let r = 1, ⋯, m be any row index. Case 1: n(a_{r}) = 0. We have n(a′_{r}) = 0 and by Lemma 3.2 that

a_{r}x = x(N_{r})
= ∑{x(N_{r} ∩ C_{t}) | t = 1, ⋯, s}
= ∑{x′(t) | t = 1, ⋯, s, |N_{r} ∩ C_{t}| = 1}
= x′(N′_{r})
= a′_{r}x′,  (4.4)

where N′_{r} denotes the set of column indices for which a′_{r} has positive entries. Case 2: n(a_{r}) = 1 and for the strong component C_{t^{∗}} containing c(r) we have N_{r} ∩ C_{t^{∗}} = ∅. We have n(a′_{r}) = 1 and by Lemma 3.2 that

a_{r}x = x(N_{r}) − x(c(r))
= ∑{x(N_{r} ∩ C_{t}) | t = 1, ⋯, s} − x(c(r))
= ∑{x′(t) | t = 1, ⋯, s, |N_{r} ∩ C_{t}| = 1} − x′(t^{∗})
= x′(N′_{r}) − x′(t^{∗})
= a′_{r}x′.  (4.5)

Case 3: n(a_{r}) = 1 and for the strong component C_{t^{∗}} containing c(r) we have N_{r} ∩ C_{t^{∗}} ≠ ∅. In this case, we have by Lemma 3.3 that |N_{r}| = 1. Letting {v^{∗}} = N_{r} it holds that

a_{r}x = x(v^{∗}) − x(c(r)).  (4.6)

Since v^{∗} and c(r) belong to the same strong component C_{t^{∗}}, we have a_{r}x = 0 for any x ∈ R^{V} defined by (4.3). On the other hand, we have a′_{r} = 0 by definition of A′ and |N_{r}| = 1. Therefore, inequality a′_{r}x′ ≤ 1 is vacuous. □

Then, we have

Lemma 4.2: Let A be a non-reconverging Horn matrix A with no forced zero. Then the matrix A′ defined in (4.1) is again non-reconverging Horn matrix with no forced zero. Furthermore, P (A) is integral if and only if P (A′) is. (Proof) Let ϕ: P (A) → P (A′) be defined as ϕ(x) = x′, where x′ is defined in (4.3).

It follows form Lemmas 4.1 and 3.2 that ϕ: P (A) → P (A′) is a bijection. Also, since ϕ can be regarded as a projection of P (A) onto some coordinates, ϕ: P (A) → P (A′) defines an isomorphism of polyhedra. The assertions of the present lemma now follows. □

By definition, for the matrix A′ defined by (4.1) each strong component of D_{A′} is singleton. For a Horn matrix A let us call A reduced^{2} if each strong component of D_{A} (or equivalently, of G_{A}) is singleton. It follows from Lemma 4.2 that we consider only non-reconverging reduced Horn matrix with no forced zero.

We are now ready to prove the following main theorem.

Theorem 4.3: A non-reconverging reduced Horn matrix A with no forced zero is perfect if and only if the following two conditions hold:

(i) The transitive closure G_{A}^{∗} of the quadratic covering graph G_{A} is perfect.
(ii) The characteristic vector of each nontrivial strong biclique of G_{A}^{∗} appears as
a row of A.

(Proof) First, note that for a non-reconverging reduced Horn matrix A with no forced zero, the quadratic covering graph G_{A} is acyclic, and hence, its transitive closure G_{A}^{∗} is closed bidirected graph.

Suppose P (A) is integral. Then, we have

P (A) = P_{I}(A) = P_{I}(G_{A}) = P_{I}(G_{A}^{∗}) ⊆ Q(G_{A}^{∗}).  (4.7)

On the other hand, since the the characteristic vector of each strong biclique of G_{A}^{∗} induces a facet of P_{I}(G_{A}^{∗}) = P (A) due to Theorem 2.3, it appears as a row of A or is trivial, i.e., the facet is induced by 0 ≤ x(v) or x(v) ≤ 1 for some v ∈ V. Therefore, we have Q(G_{A}^{∗}) ⊆ P (A). Then we have Q(G_{A}^{∗}) = P (A) and it follows from Corollary 2.6 that G_{A}^{∗} is perfect.

Conversely, suppose that Conditions (i) and (ii) hold. Then, we have

P_{I}(A) = P_{I}(G_{A}^{∗}) = Q(G_{A}^{∗}) ⊇ P (A).  (4.8)

Hence, we have P_{I}(A) = P (A), i.e., A is perfect. □

Acknowledgments

This work was supported by a Research Fellowship of Japan Society for the Promotion of Science for Young Scientists and by a Grant-in-Aid of the Ministry of Education, Science, Sports and Culture of Japan.

2In [6] and [2] the term irreducible were used in different meaning. Still, we prefer to use the same term here since it is “more reduced” than that of [6] and [2].

References

[1] K. Ando, S. Fujishige and T. Nemoto: Decomposition of a bidirected graph into strongly connected components and its signed poset structure. Discrete Applied Mathematics 68 (1996) 237-248.

[2] E. Boros and O. Čepek: Perfect 0, ±1 matrices. RUTCOR Research Report 20-95. RUTCOR, Rutgers University (June 1995). Discrete Mathematics 165-166 (1997) 81-100. (to appear).

[3] E. Boros, P. L. Hammer and X. Sun: Recognition of q-Horn formulae in linear time. Discrete Applied Mathematics 55 (1994) 1-13.

[4] V. Chvátal: On certain polytopes associated with graphs. Journal of Combinatorial Theory B 18 (1975) 138-154.

[5] M. Conforti and G. Cornuéjols: Balanced 0, ±1-matrices, bicoloring and total dual integrality. Mathematical Programming 71 (1995) 249-258.

[6] M. Conforti, G. Cornuéjols and C. de Francesco: Perfect 0, ±1 matrices. Working Paper. Dipartimento di Mathematica Pura ed Applicata, Università di Padova (October 1993). Linear Algebra and its Applications (to appear).

[7] J. Edmonds and E. L. Johnson: Matching: a well-solved class of linear programs. In: Combinatorial Structures and Their Applications (R. Guy, H. Hanani, N. Sauer and J. Schönheim, eds., Gordon and Breach, New York, 1970), pp. 88-92.

[8] D. R. Fulkerson: Anti-blocking polyhedra. Journal of Combinatorial Theory B 12 (1972) 50-71.

[9] B. Guenin: Perfect and ideal 0, ±1 matrices. Working Paper. GSIA, Carnegie Mellon University (December 1994).

[10] Y. T. Ikebe and A. Tamura: Perfect bidirected graphs. Report CSIM 96-03. Department of Computer Science and Information Mathematics, University of Electro-Communications, Chofu, Japan (May 1996).

[11] E. L. Johnson and M. W. Padberg: Degree-two inequalities, clique facets, and biperfect graphs. Annals of Discrete Mathematics 16 (1982) 169-187.

[12] E. L. Lawler: Combinatorial Optimization – Networks and Matroids (Holt, Reinehart and Winston, New York, 1976).

[13] L. Lovász: Normal hypergraphs and the perfect graph conjecture. Discrete Mathematics 2 (1972) 253-267.

[14] E. C. Sewell: Binary integer programs with two variables per inequality. Mathematical Programming 75 (1996) 467-476.

[15] K. Truemper: On balanced matrices and Tutte’s characterization of regular matroid. Preprint (1978).

Kazutoshi Ando: Institute of Policy and Planning Sciences University of Tsukuba Tsukuba, Ibaraki 305, Japan

E-mail: ando@aries.sk.tsukuba.ac.jp