Linear Programming Problems with Fundamental Cut Matrices

Abstract

Keywords: Network design; submodular function; fundamental cut sets; linear programming.

1. Introduction

Let G = (V, E) be a connected, simple and undirected graph with node set V and edge set E. Throughout the paper, we denote the number of nodes in G by n, that is, n = |V| and denote the number of edges in G by m, that is, m = |E|. Let T be a spanning tree of G. We denote the edges of T by t1, …, tn-1. Removing any edge tk splits T into two subtrees whose node sets are denoted by 𝑉𝑘 and ̅̅̅ 𝑉𝑘 = 𝑉\𝑉𝑘 . The cut separating 𝑉𝑘 and ̅̅̅ 𝑉𝑘 in the graph G is called the fundamental cut (FC) corresponding to tk. We use 𝛿(𝑆) to denote the cut separating a subset ∅ ≠ 𝑆 ⊂ 𝑉 and 𝑆̅ = 𝑉\𝑆 and use 𝑥(𝛿(𝑆)) = ∑{𝑥𝑒 ; 𝑒 ∈ 𝛿(𝑆)}. The set ℱ(𝑇) = {𝑉1 , … , 𝑉𝑛−1 } is called fundamental cut sets of the spanning tree T. Let A be an (n - 1)  m binary matrix whose columns are indexed by the edges of G and rows are 0-1 characteristic vectors of the fundamental cuts of G corresponding to edges of T. This matrix is called FC matrix. In this paper, we show that the simplex algorithm finds an optimal solution to a linear programming problem with an FC constraint matrix and a non-negative right-hand side vector in at most m - n + 1 iterations. We also give some characteristics of an FC matrix. Despite the many recent approaches, the simplex method still remains to be one of the most efficient algorithm in practice. Computational tests show that the expected number of pivot steps (simplex algorithm iterations) for solving the majority of practical problems is a linear function of the number of variables [2], [10], [13]. However, there are examples (see [7]) for which the number of the simplex pivot steps is exponential. Determining whether the number of the simplex

Corresponding Author: e-mail: hakankutucu@karabuk.edu.tr, tel: (370) 418 70 50 / 3870

method pivot steps can be bounded by a polynomial of the input size is a very difficult problem in general. The FC matrices defined above are viewed as representations of matroids in combinatorial theory. A representation of a matroid M is a matrix A with entries over some field such that there is a one-to-one correspondence between the columns of A and the ground set of M, and a set of columns in A are linearly independent (as vectors) iff the corresponding set is independent in M. If M can be represented by a matrix A with entries over the two-element field, GF(2), then it is called a binary matroid. When the matrix A is totally unimodular, M is called a regular matroid. It is well known that the graphic matroid M = (E, F) and its dual matroid are regular, where E is the edge set of G and F contains any forest, in particular, any spanning tree in G. Any spanning tree T in G is a base of the graphic matroid M = (E, F). Thus, an FC matrix is the representation of the graphic matroid M = (E, F) over the field GF(2) with respect to its base T. Many other results on binary and regular matroids can be found in [9], [12], [14]. Contrary to the regular matrix representation of M, its FC matrix is not unimodular, in general. For example, consider the graph G in Figure 1, which includes a spanning tree T shown as bold edges. It is easy to see that the following matrix

is an FC matrix of G, whose columns indexed by edges (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) from left to right, and rows are 0-1 characteristic vectors of the fundamental cuts corresponding to edges (1, 2), (2, 3), (2, 4) of the tree T. It is not difficult to see that this matrix is a representation of the graphic matroid M = (E, F) of the graph G in Figure 1 with respect to the base T. However, it is not a unimodular matrix, since the determinant of the submatrix

equals to 2  -1, 1. Here, we should mention, as in the case of signed matrices [14], after replacing some of 1's with -1 in each column, the matrix above will be totally unimodular. However, in this paper, we consider only FC matrices with 0 and 1 entries. Now, consider another spanning tree T0 of the graph G in Figure 1 with edges a = (1, 4), b = (3, 4) and c = (2, 3). Let eij denote the edge connecting vertices i and j. For the graph G, the following FC matrix with respect to the tree T0

is a totally unimodular matrix, since all 1's in each column are consecutive [10]. It is easy to see that the tree T0 is a hamiltonian path between the nodes 1 and 2. In Section 4, we show that an FC matrix of some graph with respect to a hamiltonian path (spanning tree) is totally unimodular. Special cases of the graph G and the right-hand side vector allow to get an integer solution to above mentioned network design problems by solving linear programming problems with FC constraint matrices iteratively for different spanning trees.

Figure 1. A spanning tree T of graph G. Let I be an identity square matrix and let N be a binary matrix, where the number of rows of I and N are the same. As an inverse question, in Section 4, we will also prove that if each column of N has only two nonzero entries, then A = (I, N) is an FC matrix, which is the representation of some graphic matroid with respect to a star-spanning tree base. If N has odd number of rows and columns (the odd cycle), then A = (I, N) is not a balanced matrix by the definition [1]. As characterization of FC matrices, we prove that linear programming problems with an FC constraint matrix is strongly polynomial solvable. Thus, determining whether a given matrix in the form A = (I, N) is an FC matrix presents some interest. The paper is organized as follows. Section 2 includes a brief description of some network design problems in solving which linear programing (LP) problems with FC matrices are used as subroutine. In Section 3, we show that some linear programming problems can be written as in terms of the fundamental cuts. Then, in Section 4, we give the complexity of the simplex algorithm for these linear programming problems. We discuss some characterizations of an FC matrix in terms of special submatrices in Section 5. Finally, we give some concluding remarks and some directions for future work in Section 6.

2. Network Design Problems: Motivation

In [8] and [11], the authors introduced the following general minimum cost network design problem (NDP) on a given graph G = (V, E), min ∑ 𝑐𝑒 𝑥𝑒 , 𝑒 ∈𝐸

where f(S) is a symmetric submodular function defined on the subsets of V . The theory of linear programming [10] states that a linear program with exponential number of inequalities can be solved in polynomial time if and only if the separation problem associated with these inequalities is polynomially solvable. This result has theoretical consequences. For solving network design problems, approximation solutions and polyhedral approaches use the combination of separation algorithms and linear programming solvers. The difficulty with this approach to solve NDP is that the separation problem ∆(𝑥, 𝑓) = min{𝑥(𝛿(𝑠)) − 𝑓(𝑆); ∅ ≠ 𝑆 ⊂ 𝑉}

is NP-hard, for reason that when f(S) is a cut function as a special case of symmetric submodular functions, ∆(𝑥, 𝑓) is the well known maximum cut problem. However, ∆(𝑥, 𝑓) is reduced to the minimum cut problem when f(S) is a modular function [11]. In order to use the same techniques in solving NDP, it is necessary to find the capacity xe of edges 𝑒 ∈ 𝐸 and then to test whether the capacities xe satisfy the constraints for any ∅ ≠ 𝑆 ⊂ 𝑉. Therefore, we fix some spanning tree T in the graph G and set 𝑏𝑡 = 𝑓(𝑉𝑡 ) − 𝑙(𝛿(𝑉𝑡 )) for each t in T, then the capacity 𝑥𝑒 = 𝑦𝑒 + 𝑙𝑒 of edges 𝑒 ∈ 𝐸 can be defined by solution 𝑦 = (𝑦𝑒 ; 𝑒 ∈ 𝐸) of the linear program 𝜑1 (𝑇) (see Section 3) with the FC constraint matrix. In order to test whether the capacities xe satisfy the constraints for any ∅ ≠ 𝑆 ⊂ 𝑉, one can use a combination of the branch and bound techniques and results derived in solving ∆(𝑥, 𝑊) for a modular function W approximated f. If the answer is yes and all capacities are integer, then the algorithm terminates. If any constraint for the cut (determined by some node subset) is violated, then the algorithm finds a new spanning tree T1 whose fundamental cut set contains this subset and again find an optimal solution to 𝜑1 (𝑇1 ). This process iterates until all constraints hold. Another network design problem is the optimum communication spanning trees (OCST) [5] which can be used as subproblem to solve linear programing problem with FC matrices. Let a set V of n nodes and a set of requirements rvw for pair of distinct nodes v and w in V be given. The OCST problem is to build a spanning tree connecting these n nodes such that the total cost of the spanning tree is minimum among of all spanning trees. The cost of communication for a pair of nodes v and w is rvw multiplied by the sum of the distances cij of edges on the unique path connecting v and w in the spanning tree. The cost of a spanning tree is the sum of communications for all pair of nodes in the spanning tree. In [5], it is noted without a proof that the OCST problem is hard to solve, in general. Let G = (V, E) be a complete graph on n nodes with weight cij of edges and let R = (V, E(R)) denote a graph of given requirements, that is, (𝑖, 𝑗) ∈ 𝐸(𝑅) if rij > 0. Let 𝛿𝑅 (𝑆) denote a cut in the graph R determined by subset ∅ ≠ 𝑆 ⊂ 𝑉. The OCST problem on graph G can be formulated as follow to find a spanning tree 𝑇∗ of minimum cost. 𝑐(𝑇∗ ) = ∑ 𝑐𝑒 𝑥𝑒 ⟶ 𝑚𝑖𝑛 , 𝑒 ∈𝐸

subject to 𝑥𝑒 = 𝑟(𝛿𝑅 (𝑉𝑒 )), 𝑉𝑒 ∈ ℱ(𝑇∗ ). For graphs G with cyclomatic number 𝜐(𝐺) = 𝑚 − 𝑛 + 1 bounded by some small constant, the spanning tree 𝑇∗ can be found by enumerating all spanning trees in G. In order to solve the OCST problem in general, one can use the following observations on the problem of OCST. The first observation is that, for a spanning tree T0 of the graph G, as a feasible solution to the OCST problem, the vector y with components yt = bt for each t  T0 and ye = 0 for all 𝑒 ∈ 𝐸\𝑇0 is the initial basic feasible solution to the problem 𝜑1 (𝑇0 ) with the right hand vector 𝑏 = (𝑏𝑡 = 𝑟(𝛿𝑅 (𝑉𝑡 )); 𝑡 ∈ 𝑇0 ) and y satisfies the above constraints when 𝑇∗ = 𝑇0 . Let 𝒯(𝑇0 ) denote the set of spanning trees derived from tree T0 by adding any edge 𝑒 ∈ 𝐸\𝑇0 to T0 and deleting an edge 𝑡 ∈ 𝑇0 on the unique cycle in 𝑇0 ∪ {𝑒}. The second observation is that if the basic solution 𝑦 = (𝑦𝑒 ; 𝑒 ∈ 𝐸) is an optimal solution to 𝜑1 (𝑇0 ), then c(T0)  c(T) for any 𝑇 ∈ 𝒯(𝑇0 ). Note that heuristics based on Proposition 2 and 3 (see Section 3) can be used for defining the spanning tree T0. It easy to see that the inequality 𝑐(𝑇) ≤ 𝜑1 (𝑇), as cutting plane, allows to eliminate 𝑂(𝑛𝜐(𝐺)) spanning trees from the set of feasible solutions. Taking into account 𝜐(𝐺) = 𝑂(𝑛2 ) for a complete graph G, the use of inequality 𝑐(𝑇) ≤ 𝜑1 (𝑇) essentially reduces the number of branching iterations for solving the OCST problem on G.

Due to the second observation, we get a generalization of the following result. For the case when 𝑟𝑖𝑗 is any non-negative number and 𝑐𝑖𝑗 = 1 for all edges (𝑖, 𝑗), it was shown that the wellknown Gomory and Hu algorithm constructed spanning tree T(GH) of the complete graph with the capacity 𝑟𝑖𝑗 of edges is an OCST [5]. Indeed, from Proposition 2, it follows that if nonnegative cost of edges satisfy (8) with respect to T(GH), then the above mentioned intial basic feasible solution for T(GH) = T0 is the optimal solution to the problem 𝜑1 (𝑇(𝐺𝐻)) and 𝑐(𝑇(𝐺𝐻)) ≤ 𝑐(𝑇) for any spanning tree T in G, that is, 𝑇(𝐺𝐻) = 𝑇∗ . Moreover, by the first observation, the condition that a spanning tree T itself is an optimal solution to 𝜑1 (𝑇) as the fixed point mapping 𝜑1 (𝑇) T allows to apply the theory of fixed point mappings to solve the OCST problem. We leave this future work.

3. LP Problems With AN FC Matrix

Consider the following linear programming problem min cx, subject to Ax = f, x  l  0, for a given vectors c, l  RE and f  RT , where l  0, f  0. Let T be a spanning tree with edges t1, …, tn-1. This LP problem can be written as the following problem in the terms of the fundamental cuts 𝛿(𝑉𝑘 ) for all 𝑉𝑘 ∈ ℱ(𝑇). min ∑ 𝑐𝑒 𝑥𝑒 , 𝑒 ∈𝐸

It is convenient to write it in the variables ye = xe - le as follows. 𝜑1 (𝑇) = min ∑𝑒 ∈𝐸 𝑐𝑒 𝑦𝑒 ,

where 𝑏(𝑡𝑘 ) = 𝑓𝑘 − 𝑙(𝛿(𝑉𝑘 )) for all k = 1,...,n-1 and we will denote the vector (𝑏(𝑡𝑘 ); 𝑘 = 1, … , 𝑛 − 1) by b for short. Since each edge tk is an edge of the cut 𝛿(𝑉𝑘 ), then the matrix A can be represented in the form (I, N) by permuting columns, where I is (n  1)  (n  1) identity matrix whose columns are indexed by edges of the tree T. The rows of the matrix A are 0 or 1 characteristic vectors of the cuts 𝛿(𝑉𝑘 ). A column h of N contains 1 in a row 𝛿(𝑉𝑘 ) if the edge tk is an edge of the cycle C(h) obtained by adding the edge h  E \ T to the tree T. Conversely, if t1, ..., tp are edges of the cycle C(h), then h is just an edge of the cuts 𝛿(𝑉1 ), … , 𝛿(𝑉𝑝 ). So, we have the following property; Property 1 For any edge h  E\T, if t1, ..., tp are edges of a cycle C(h), then the column h has just 1 in the rows corresponding to cuts 𝛿(𝑉𝑘 ), 𝑘 = 1, … , 𝑝. This implies the linear dependence of the vector columns indexed by t1,..., tp and h.

For any e  E, we write e  C(h) if e is an edge of the cycle C(h). For edges e, h  E \ T, if the cycle C(e) contains only edges tk  C(h), the cycle C(e) is called a subcycle of C(h), that is the edge e is a chord of C(h). Let ae denote the column e of the matrix N for each edge e  E \ T. It follows that ah  ae for any chord e of the cycle C(h). We also assume that b(tk)  0 for each 𝑉𝑘 ∈ ℱ(𝑇), otherwise the problem (1)-(3) is infeasible. Hence, the variables 𝑦𝑡1 , … , 𝑦𝑡𝑛−1 corresponding to the columns of I form basis for (1)-(3). The following propositions will be used to solve the problem (1)-(3). Proposition 2 For an edge h  E \ T, if ∑𝑡𝑘 ∈𝐶(ℎ) 𝑐𝑡𝑘 ≤ 𝑐ℎ ,

then the edge h can be deleted in the graph G. Proof. The dual problem of (1)-(3) can be given as max

in which conditions 𝑢(𝑡𝑘 ) ≤ 𝑐𝑡𝑘 are associated with the edges tk  T. By Property 1, ∑ 𝑢(𝑡𝑘 ) = 𝛿(𝑉𝑘 )∋ 𝑒

the left side of the constraints (6) for e = h is the sum of those for e = tk  C(h). Therefore, the edge h can be deleted in G. Proposition 3 Let C(h) be any cycle and let e be a chord of C(h), where e, h  E \ T. If ∑𝑡𝑘 ∈𝐶(ℎ) 𝑐𝑡𝑘 − 𝑐ℎ ≤ ∑𝑡𝑘 ∈𝐶(𝑒) 𝑐𝑡𝑘 − 𝑐𝑒 ,

then the edge h can be deleted in the graph G. Proof. The dual problem (5)-(6) can also be represented as max

𝑧(𝑡𝑘 ) ≥ 0, 𝑉𝑘 ∈ ℱ(𝑇) by setting 𝑧(𝑡𝑘 ) = 𝑐𝑡𝑘 − 𝑢(𝑡𝑘 ). Since the edge e is a chord of C(h), ah  ae, that is, ∑ 𝑧(𝑡𝑘 ) ≥ ∑ 𝑧(𝑡𝑘 ). 𝛿(𝑉𝑘 )∋ℎ

It follows that ∑ 𝑧(𝑡𝑘 ) ≥ ∑ 𝑧(𝑡𝑘 ) ≥ ∑ 𝑐𝑡𝑘 − 𝑐𝑒 ≥ 𝛿(𝑉𝑘 )∋ℎ

which is the last inequality (7). Therefore, we can delete the constraints (2) for e = h. In other words, the edge h can be deleted in the graph G. ∎

By Proposition 3, if (7) holds for one of chords e1, …, ep  E \ T of any cycle C(h), then the constraint (2) for e = h can be deleted. Hence, we have ∑𝑡𝑘 ∈𝐶(ℎ) 𝑐𝑡𝑘 − 𝑐ℎ > ∑𝑡𝑘 ∈𝐶(𝑒𝑖 ) 𝑐𝑡𝑘 − 𝑐𝑒𝑖

for any cycle C(h) (h  E \ T) and its chords e1, …, ep  E \ T.

4. The Complexity Of Problem (1)-(3)

Using Propositions 2 and 3, we delete the edges e  E \ T in the graph G for which the conditions (4) and (7) hold. It is clear that this can be carried out in O(m  n + 1) time. In the result, we have ∑𝑡𝑘 ∈ 𝐶(ℎ) 𝑐𝑡𝑘 > 𝑐ℎ ,

and the condition (8) holds for any cycle C(h) and its chords e  E\T. Although theoretically the number of pivot steps of the simplex algorithms is exponential, the following theorem states that the number of the classical simplex algorithm with Dantzig's pivot rule is bounded by a linear function of the number of edges for solving the linear program (1)-(3). It seems that to find a polynomial time simplex method and the closely related Hirsch conjecture proof is a hard problem in general. Theorem 4 The simplex algorithm finds an optimal solution to (1)-(3) in at most m  n + 1 iterations. Proof. Without loss of generality, we assume b > 0, since if b(tk) = 0 for some tk, then 𝑥𝑡0𝑘 = 𝑙𝑡𝑘 in an optimal solution and hence the edges of the cut 𝛿(𝑉𝑘 ) can be deleted in G and the problem (1)(3) can be solved independently for each connected component. Since b > 0, we can take 𝑦𝑡0𝑘 = 𝑏(𝑡𝑘 ) for all 𝑡𝑘 ∈ 𝑇, 𝑦𝑒0 = 0 for all 𝑒 ∈ 𝐸\𝑇 as the initial basic feasible solution for the problem (1)-(3). Hence (1)-(3) has an optimal solution by the theory of linear programming. According to (9) the reduced cost is 𝑐̅𝑒 = 𝑐𝑒 − ∑ 𝑐𝑡𝑘 < 0, 𝑡𝑘 ∈𝐶(𝑒)

for each e  E \ T. Because ye can be selected as the entering variable for any e  E \ T. From (8) it follows that the classical simplex algorithm selects yh for which 𝑐̅ℎ = min{𝑐̅𝑒 ; 𝑒 ∈ 𝐸\𝑇}, for entering to the basic 𝑦 and 𝑦𝑒0 = 0 for any chord e of the cycle C(h). Moreover 𝑦𝑡0𝑞 = 0, since 𝑦𝑡𝑞 = 0 is a leaving variable for some edge tq  C(h), since columns for edges tq  C(h) and h as vectors are linearly dependent by Property 1. Let the simplex algorithm proceeds to a basic solution 𝑦 1 = (𝑦𝑒1 ; 𝑒 ∈ 𝐸) by choosing to bring yg into basic 𝑦̅ and removing the variable yh from the basic 𝑦̅ for first time. Then the following two cases are possible for positions of the edges h and g with respect to fundamental cuts. 0

Figure 2. h = (1, 7), tq = (6, 7), g = (3, 7) Case 1: In some basis solutions generated before y1, when yh became a basic variable and 𝑦𝑡𝑞 non-basic variable, there is a subcycle C(e0) of C(H), such that yt > 0 for edges t in 𝐶(𝑒0 ) ∩ 𝑇 and 𝑡𝑞 ∉ 𝐶(𝑒). Since 𝑦𝑡𝑞 = 0 the subcycle C(e0) as cycle C(h), the edge e0 is entering to some basic solution and some edge 𝑡1 ∈ 𝐶(𝑒0 ) ∩ 𝑇 is leaving. This can be repeated for some subcycle of C(e1) of C(e0) such that t1  C (e1). We assume that this process is carried out for edges ei, where i = 0,1,…,p and g = ep. By Proposition 2 and ∑

for edges e = e0, e1,…,ep1, the variables 𝑦𝑒𝑖 were in some basic solutions generated before y1. Since yh is leaving basic variable from the basic solution 𝑦̅ and yg is entering basic variable to 𝑦̅, C(g) = C(ep) is the last of such subcycles that the following inequality ∑( ∑ 𝑒𝑖

holds. Figures 2 displays a piece of T whose edges are bold lines, where 𝑦𝑡1 for bold edges are in the basic solution y1 except tq = (6,7). When yh = y17 entered to the basic solution, 𝑦𝑡𝑞 became a nonbasic variable. In some solutions generated before y1, for edges e and t on the subcycles C(3,6) and C(3,5) of the cycle C(1,7), the variables ye and yt became a basic and a non-basic variable, respectively, in the following order;  

the y36 became a basic variable and t56 became non-basic variable on the subcycle C(3,6) of C(1,7); the y35 became a basic variable and t45 became non-basic variable on the subcycle C(3,5) of C(1,7);

After y36 and y35 became basic variables, yg = y37 is entering variable to the basic solution y1 and yh = y17 is a leaving variable from y1 with respect to the cycle with edges g = (3,7), h = (1,7), t = (1,2), t = (2, 3).

Figure 3. h = (1, 5), tq = (3, 4), g = (4, 7) Case 2: The edge tq is on the cycles C(h) and C(g) that are not subcycles of C(h). As in Case 1, in some basic solutions generated before y1, for some edges t in 𝑇 ∩ 𝐶(ℎ), the variable yt and ye became a non-basic and a basic variable, respectively, for some subcycles C(e) of C(h). Differently from Case 1, there is a cycle C in G such that the edges h, g and edges e of these subcycles are on C. Figure 3 indicates that the cycle C with edges h, (1, 3), (3, 7), g, (4, 5) for 1 which 𝑦𝑒1 (e = (1,3), (4,5), h) and 𝑦𝑡1 = 𝑦37 (t = (3,7)  T) are basic variables. Now, from that yg is an entering basic variable to 𝑦̅ implies ∑ 𝑢(𝑡𝑘 ) > 𝑐𝑔 , 𝛿(𝑉𝑘 )∋𝑔

for the simplex multipliers {u(tk)} as trial solution to the dual of (1)-(3) which means that the dual constraint associated with the variable yg is violated. To enter yg to the basic solution, the simplex algorithm defines new multipliers {u(tk)} satisfying the following equation ∑ 𝑢(𝑡𝑘 ) = 𝑐𝑔 . 𝛿(𝑉𝑘 )∋𝑔

This means that in both cases, ∑{𝑢(𝑡𝑘 ); for edges 𝑡𝑘 on 𝐶(ℎ) and 𝐶(𝑔)} is decreasing after the simplex algorithm defined the basic y1. Therefore, each yh can be a basic variable only once and hence the simplex algorithm finds an optimal solution to the problem (1)-(3) in at most m  n + 1 iterations. ∎ Consider the problem (1)-(3) on the graph G in Figure 2. Let T be a spanning tree with bold edges (1,4), (2,5), (3,6), (4,5), (5,6) and then ℱ(𝑇) = {V14 = {1}, V25 = {2}, V36 = {3}, V45 = {1,4}, V56 = {3,6}}. The edges crossing with the dashed lines represent edges of corresponding fundamental cuts whose numbers are shown in rectangles at the end of the dashed lines. Let b(14) = 5, b(25) = 6, b(36) = 6, b(45) = 7 and b(56) = 8 for the fundamental cut sets in ℱ(𝑇). The number next to each edge e indicates its cost ce. Since conditions (4) and (8) do not hold at any edge of the cycles C(12), C(13), C(23), C(46), any edge cannot be deleted in G. In this example, y14 = 5, y25 = 6, y36 = 6, y45=7 and y56 = 8 are initial basic variables corresponding to the edges in T. In the first iteration, the variables y13 and y14 are entering and leaving basic variables, respectively. In the next three iterations, y23 and y36, y46 and y56, y12 and y25 become basic and non-basic variables, ∗ ∗ ∗ ∗ respectively. The optimal solution is 𝑦13 = 2.5, 𝑦32 = 3.5, 𝑦12 = 2.5, 𝑦46 = 2 and 𝑦𝑒∗ = 0 for the other edges.

As a conclusion of Section 2, let P(T) be a polytope defined by (2) and (3) and let its vertices vT and vop be an initial and an optimal basic solutions, respectively. By Theorem 4, it follows that the minimum distance between the vertices vT and vop is not greater than m  n + 1 in P(T). Theorem 4 states that the Hirsch conjecture [3] holds for the facet containing vertices vT , vop, if m  3(n  1) in a graph G.

Figure 4. A graph G, a spanning tree T and five fundamental cuts. It is not difficult to give some examples to show that (1)-(3) has no integer-valued optimal solutions for ℱ(𝑇) with respect to some spanning tree T. When T is a Hamiltonian path, all 1’s are consecutive in each column of the matrix A (see Proposition 6) from which it follows that the matrix A is unimodular [10]. This means that the problem (1)-(3) has an integer valued solution for an integer vector b, when T is any Hamiltonian path. The problem (1)-(3) with the vector b = 1 is the LP relaxation of the ℱ(𝑇)Constrained Forest Problem (CFP) [4] when the proper function 𝑓(𝑆) = 1 (𝑓: 2𝑉 → {0,1} for the fundamental cut sets 𝑆 ∈ ℱ(𝑇)). Hence, if the tree T is any Hamiltonian path, then the LP relaxation of CFP has an integer-valued optimal solution.

5. Characterization Of The FC Matrices

Let A = (I,N) be a given binary matrix. Is there an undirected simple graph G = (V,E) for which the columns of A can be indexed by edges in E, so that the rows of A are 0, 1 characteristics vectors of fundamental cuts corresponding to the edges of some spanning tree in G? In other words, whether the matrix A represents a graphic matroid with respect to some its base. The following lemma allows to construct a graph for some particular cases of the matrix A = (I,N). Lemma 5 If a binary matrix A = (I,N) has n - 1 rows and m  (n - 1)n/2 columns, and each column of N contains two 1's and no identical columns in N, then it can be represented by graph a G = (V,E) with n nodes and m edges with respect to (n - 1) star-spanning tree T in G. Proof. Let T be a star with n - 1 edges and n nodes. First we index rows of A and columns of I by edges of the tree T. Then we construct the graph G = (V,E) by adding edges to T: for any column j of N containing 1’s in rows t and h, we add an edge j to the tree T so that it connects leaves of edges t and h. Since there is no any identical columns in N, the graph G has no parallel edges. m  (n - 1)n/2 can be written as m - (n - 1)  (n - 1)(n - 2)/2 which means that the columns of N can be indexed by no tree edges of a simple undirected graph G. Suppose that a row t in A has 1's in columns j1, j2,..., jp. In G, since edges j1, j2,..., jp connect the leaf of the edge t to the leaves of the other edges

in T, then the cut corresponding to the edge t contains all those edges. So, the row t is the characteristic vectors of the fundamental cut corresponding to the edge t in T and the proof is complete. ∎ Proposition 6 Let T = (V,E(T)) be a Hamiltonian path connecting some two nodes v,w  V in a graph G = (V,E). The FC matrix of the graph G with respect to the tree T is totally unimodular. Proof. Without loss of generality, we may assume that the Hamiltonian path T = ((v = 1, 2), (2, 3), …, (n-1, n = w)) connects the nodes v and w. Consider an FC matrix whose ith row is indexed by the edge (i, i + 1) in T for i =1, …, n - 1 and the columns are indexed as follows: the first n - 1 columns are indexed by the edges in T and then the other m - n + 1 columns are indexed by the edges (1, i), for 3  i  n, the edges (2, i), for 4  i  n and so on. Thus, the row of the FC matrix corresponding to the cut determined by deleting the edge (1, 2) contains 1's in the columns (1, 2) and (1, i) for 3  i  n. The row (2, 3) corresponding to the cut determined by deleting the edge (2, 3) contains 1's in all columns (1, i) for 3  i  n, since nodes 1 and 2 are on the same side of the cut. Similarly, the row (3, 4) corresponding to the cut determined by deleting the edge (3, 4) contains 1's in all columns (1, i) for 4  i  n and so on. That is, the columns (1, i) (3  i  n) of the FC matrix contain the 1's consecutively. Since the first (n - 1) columns are unit vectors, this FC matrix is in the form A = (I,N). By Heller and Hoffman, the FC is a totally unimodular matrix [10]. ∎ Let A = (I,N) be an FC matrix whose columns are indexed by 1,…,m and rows are indexed by 1,…, p, where p = n - 1. Suppose that a column k in N contains 1's in rows k1, …, kq in N. In other words, the column k induces a q x (m - p) submatrix A(k) of N with the rows k1, …, kq. If there exist a reordering of the rows of A(k) such that the permuted submatrix has no column containing 0's between 1's, then we call it an HP (Hamiltonian path) matrix. Since A is an FC matrix, there is a graph G = (V,E) with |E| = m and |V | = n such that the rows of A are 0, 1 characteristics vectors of fundamental cuts corresponding to some spanning tree of G. Now, let A(k) and A(h) be HP matrices induced by the columns k and h of N and let (kh)1, …, (kh)t be common rows of A(k) and A(h). This means that the edges corresponding to the rows (kh)1, …, (kh)t are on the cycles C(k) and C(h) created by adding the edges ek and eh to the spanning tree. Suppose that these rows were reordered as (kh)1, …, (kh)t to transform A(k) and A(h) to HP matrices. If the common rows can be reordered as (kh)1, …, (kh)t or (kh)t, …, (kh)1 to transform A(h) and A(k) to HP matrices, we call k and h tree-common columns.

Figure 5. A graph G (bold and dashed lines) and a spanning tree T (bold lines). In order to explain the key moments of the tree-common columns, first consider the graph of Figure 3, where the bold lines represent the edges of the spanning tree. To make a distinction between the edges of T and the others, we denote the edges of T by a = (1, 2), b = (2, 3), c = (3, 4), d = (4, 5), k = (6, 7), h = (3, 7), f = (3, 8), e = (8, 9) and denote the other edges (dashed lines) with end nodes i and j by eij in G. The matrix N is as follows:

If the rows of the submatrix induced by the column e16 are reordered as abhk, then it becomes an HP matrix. The submatrix induced by the column e68 is an HP matrix with the reordering khf of its rows. The column e56 induces a submatrix which is an HP matrix after reordering its rows as dchk. Thus, the columns e16 and e56 are tree-common columns. Theorem 7 An FC matrix satisfies the following conditions: 1. 2.

Its columns induce an HP matrix. If submatrices induced by any pair of distinct columns have common rows, then these columns are tree-common.

Proof. Let A = (I,N) be an FC matrix. There exist unknown undirected graph G = (V,E): the columns of A can be indexed by edges of G and the rows are 0, 1 characteristics vectors of the fundamental cuts corresponding to the edges of some spanning tree T in G. Let k be the first column in N with the maximum number of ones. Then the edge k cannot be a chord of any cycle and the nodes of the cycle C(k) induce the subgraph Gk in which the edges t  C(k) are on a Hamiltonian path Pk. Because the submatrix A(k) induced by the column k is an HP matrix by Proposition 6. Now, let h be the second column in N (if exists) with the maximum number of ones such that no all rows of the submatrix A(h) are the rows of A(k). Similarly, it can be shown that A(h) is an HP matrix, too. Therefore, by iterating this, it can be shown that the selected columns induce HP submatrices. Since the edges for any non-selected columns are chords of cycles created by edges for the selected columns, the submatrices induced by the first type columns are HP. Suppose that submatrices A(h) and A(k) have common rows (kh)1, …, (kh)q  T. This means that these edges are on a subpath Pkh in the tree T, since Pk and Ph are paths in T. The subpath Pkh is in T, hence, k and h are tree-common columns that complete the proof. ∎ Note that the converse of Theorem 7 is not true, for example, the well known dual Fano matrix [9] satisfies the conditions 1 and 2 of Theorem 7, however, it is not an FC matrix. The well ′ known Seymour's matrices 𝑅10 and 𝑅10 [12] are not an FC matrix, since they contain rows which do not induce an HP matrix. Any FC matrix can be regarded as the representation of a graphic matroid as binary matroid. An FC matrix is not generally a totally unimodular matrix. Therefore, this representation is not always regular for a graphic matroid.

6. Conclusion

The problem of graph visualization is important in computer science [6]. The proof of Theorem 7 can be used to design an algorithm for drawing graphs represented by FC matrices. We observed that when the matrix A is an FC-matrix of the Hamiltonian-spanning tree, 𝑃 = {𝑥 ∈ 𝑅𝑚 ; 𝐴𝑥 = 𝑓, 𝑥 ≥ 𝑙 ≥ 0} is an integral polytope [10] by Proposition 6. In terms of the linear complexity of the simplex algorithm for the problem min{𝑐𝑥; 𝑥 ∈ 𝑃},

it appears that one of the most promising approaches for network design problems [8], [11] is to find an integer solution of (10) in each iteration of the branch and cut algorithm. Therefore, characterization of all spanning trees of the graph G, for which P is an integral polytope, can be used to get new polyhedral results for reducing subproblems encountered in solution of the abovementioned network design problems. Another suggested direction for future investigation is to strength Theorem 4, i.e., to prove that the simplex algorithm finds a solution to the problem (10) in almost linear time for a binary matroid matrix A and a given non-negative vectors c and f.

Share and Cite