A Polynomial-Time-Delay and Polynomial-Space
Algorithm for Enumeration Problems in
Multi-Criteria Optimization
Yoshio Okamoto1 and Takeaki Uno2
1

Department of Information and Computer Sciences, Toyohashi University ofTechnlology, Hibarigaoka 1–1, Tempaku, Toyohashi, Aichi, 441-8580, Japan. E-mail:okamotoy@ics.tut.ac.jp
2
National Institute of Informatics, Hitotsubashi 2–1–2, Chiyoda-ku, Tokyo,
101-8430, Japan. E-mail: uno@nii.jp

Abstract. We propose a polynomial-time-delay polynomial-space algorithm to enumerate all efficient extreme solutions of a multi-criteria
minimum-cost spanning tree problem, while only the bi-criteria case wasstudied in the literature. The algorithm is based on the reverse searchframework due to Avis & Fukuda. We also show that the same technique
can be applied to the multi-criteria version of the minimum-cost basis
problem in a (possibly degenerated) submodular system. As an ultimate
generalization, we propose an algorithm to enumerate all efficient extreme solutions of a multi-criteria linear program. When the given linear
program has no degeneracy, the algorithm runs in polynomial-time delay and polynomial space. To best of our knowledge, they are the firstpolynomial-time delay and polynomial-space algorithms for the problems.

1

Introduction

The multi-criteria optimization is a vast field in optimization theory, operations
research, and decision science. In a multi-criteria optimization problem, we usually need to enumerate the solutions which have a certain specified property, forexample, the Pareto optimality or the efficiency.3 See Ehrgott [3] for detail.
There have been two main streams in algorithm design for the multi-criteria
optimization: exact approach and approximate approach. In the exact approach,the enumeration has to be exact, namely, all the solutions have to be output(without any duplication). For example, in the multi-criteria linear programming many exact algorithms have been proposed which enumerate all efficientextreme solutions or enumerate all efficient faces (see Ehrgott [3] and references therein). For bi-criteria combinatorial optimization problems, Ulungu &Teghem [8] proposed the so-called two-phase method which first determines the3

The word “efficient” is used differently in multi-criteria optimization and in algorithm theory. In multi-criteria optimization (or economics) efficiency is just anothername for Pareto optimality. We hope that the reader is never confused.

2

Yoshio Okamoto and Takeaki Uno

extreme efficient solutions then enumerate the rest of the efficient solutions. On
the other hand, in the approximate approach the enumeration is partial. See Zitzler, Laumanns & Bleuler [11] for example. A bit different approximate approach
was done by Papadimitriou & Yannakakis [7], which has a certain approximation
guarantee. See a recent short survey by Zaroliagis [10].
This work concentrates on the exact approach and we will exploit techniquesfrom enumeration algorithmics. Despite many algorithm have been reported for
multi-criteria optimization from the exact approach viewpoint, few of them havea certain theoretical guarantee of complexity. Observe that enumeration of thePareto-optimal extreme solutions of a single-criteria linear program is equivalent
to enumeration of the vertices of a convex polyhedron, and a recent result by
Khachiyan, Boros, Borys, Elbassioni & Gurvich [5] shows that this problem
admits no polynomial total time algorithm unless P = NP. This looks one ofthe obstructions for a theoretical investigation. So, we concentrate on a simpler
problem to reveal the difficulty for the development of an algorithmic theory ofmulti-criteria enumeration problems.
As a sample problem, we study the multi-criteria minimum-cost spanning
tree problem: given a connected undirected graph and several edge-cost functions, we have to find all spanning trees which minimize some convex combinations of the cost functions. In the multi-criteria optimization terminology, theoutputs are exactly the solutions for all possible weighted sum scalarizations,and they correspond to the extreme efficient solutions. The determination of theextreme efficient solutions is a first step for complete enumeration of the efficientsolutions, for example in the two-phase method [8].
We will compare two main methods in enumeration algorithmics. One is thebinary partition method, and the other is the reverse search method. In thebinary partition method, we recursively divide the solution space until we gettrivial instances. In the reverse search method proposed by Avis & Fukuda [1], we
implicitly define a rooted tree on the solutions to be enumerated, and traverse it.
We try to apply the two enumeration methods above to the multi-criteria
minimum-cost spanning tree problem. For the binary partition method, we provethat a subproblem arising from a natural binary partition approach is NPcomplete. This implies that an approach by the binary partition method seems
difficult. On the other hand, with the reverse search method we design an algorithm which runs with polynomial-time delay and in polynomial space. This is
the first algorithm for this problem with such a complexity guarantee.
Our reverse-search algorithm can be extended to the multi-criteria version of
the minimum-cost base problem in matroids and submodular systems. Furthermore, a similar algorithm turns out to work for the multi-criteria linear programming. Although there have been many algorithms proposed for the multi-criteria
linear programming, none of them has a performance guarantee as running withpolynomial-time delay and in polynomial space (see Ehrgott [3] and references
therein). Indeed, these algorithms store all the outputs as a list in the working
memory to get rid of duplication, which looks a bottleneck for the efficiency. We
may accomplish the polynomial-time delay by a small modification (for exam-

Enumeration Problems in Multi-Criteria Optimization

3

ple, using a balanced binary search tree instead of a list). However, it appears
difficult for these algorithms to achieve the polynomial space by a small modification; namely, the essential improvement for memory usage is by far hard. On
the other hand, our reverse-search algorithm can achieve both of the goals. This
exhibits the power of the reverse search, and we hope that this work initiates amore fruitful connection of the multi-criteria optimization with the algorithms
community.
The paper is organized as follows. In the next section, we give an introduction to enumeration algorithmics terminology and a concise description of themulti-criteria minimum-cost spanning tree problem. Section 3 discusses someexisting methods to enumerate the spanning trees and observe how natural extensions of these methods fail. This includes the NP-completeness result of anatural subproblem arising from a binary partition method. Then in Section 4,
we consider how we can overcome this issue, and design an algorithm runningin polynomial-time delay and polynomial space with the reverse search method.
Section 5 discusses a possible generalization of our reverse search algorithm tothe multi-criteria linear programming. The final section concludes the paper withsome open questions.

2

Preliminaries

An enumeration problem asks to output all objects, called solutions, which satisfy a given condition. To measure the efficiency of enumeration algorithms, wehave to take into account the size of output (i.e., the number of solutions) explicitly since it could be exponentially large in terms of the size of input. An
enumeration algorithm runs in polynomial-time delay if for any output object
the next output object can be obtained in polynomial time in the size of input;
it runs in polynomial-space if the working space it uses is bounded by a polynomial of the size of input. Note that we only count the working space, excluding
the space for outputs. Intuitively speaking, the working space is a read/write
memory and the output space is a write-only disk.
Pk
A convex combination of k functions c1 , c2 , . . . , ck is a function
i=1 λi ci
for some non-negative real numbers λ1 , λ2 , . . . , λk summing up to one. We callthe vector (λ1 , . . . , λk )> ∈ IRk of coefficients the barycentric coordinate of the
combination.
Given a connected undirected graph G = (V, E), a spanning tree of G is anedge subset T ⊆ E of size |V | − 1 which embraces no cycle. For a non-negativeedge-cost function c : E → IR+ , a minimum-cost spanning tree of G withP respect
to c is a spanning tree T of G which minimizes the total cost c(T ) = e∈T c(e).
We study the following problem.
Problem: MC-MCST
Input: a connected undirected graph G = (V, E) and k distinct nonnegative edge-cost functions c1 , . . . , ck : E → IR+
Enumerate: the spanning trees of G each of which is minimum-costwith respect to some convex combination of c1 , . . . , ck .

4Yoshio Okamoto and Takeaki Uno

We call a spanning tree of G feasible if it is minimum-cost with respect to someconvex combination of c1 , . . . , ck (i.e., if it is to be output in MC-MCST).

3

Failed Attempts for Generalization by Straightforward
Approaches

In this section, we first describe two existing methods for enumeration of spanning trees in a given connected graph, and observe why the straightforward
generalizations of them to MC-MCST do not give efficient algorithms.
3.1

Binary Partition Method

Let us first look at a simple binary partition approach to enumerate all spanning
trees in a given connected undirected graph G = (V, E). First of all, we choose anarbitrary edge e1 ∈ E and classify the spanning trees of G into two groups: thosecontaining e1 and those not containing e1 . Then, we choose another arbitraryedge e2 ∈ E \{e1 }, and divide the groups similarly. This will give a recursion tree,
and we stop the recursive call when the obtained group is ensured to contain no
spanning tree. In this way, we can reduce redundant computation. The problem
to decide whether a group contains a spanning tree can be formulated as “fordisjoint subsets E1 , E2 ⊆ E, does there exist a spanning tree of G which contains
the edges in E1 but does not contain any edges in E2 ?” This can be solved inlinear time.
To solve MC-MCST in the same way, we have to solve the following problem.
Problem: BinaryPartition
Input: a connected undirected graph G = (V, E), two disjoint subsets E1 , E2 ⊆ E and k distinct non-negative edge-cost functions
c1 , . . . , ck : E → IR+
Question: Does there exist a spanning trees of G which contains theedges in E1 but does not contain any edges in E2 and is minimum-costwith respect to some convex combination of c1 , . . . , ck .
If the problem BinaryPartition can be solved in polynomial time, then we
can use the same binary partition strategy as above to obtain an algorithm tosolve MC-MCST in polynomial-time delay and polynomial space. However, thefollowing theorem shows that it is quite unlikely for us to achieve this goal.
Theorem 1. The problem BinaryPartition is NP-complete.
Proof. We can easily see the membership of the problem in NP. We show NPhardness. To this end, we reduce the satisfiability problem (SAT) to BinaryPartition. An instance of SAT is given as a set of boolean variables x1 , . . . , xn anda set of clauses C1 , . . . , Cm each of which consists of (possibly several) literals.
Each literal is either a variable or its negation.
From the given instance of SAT, we construct a connected graph G = (V, E).
For each variable xi we set up three vertices vir , vit , vif . For each clause Cj we set

Enumeration Problems in Multi-Criteria Optimization

v1t

v1f v2tv2f v3t

v1r

v2r

v3f v4t

v4f

v3r

v4r

w2q

w3r

5

r
w1q

w1r
ux1 1

ux1 2

ux1 3

w2r

ux2 3

ux2 2

ux3 1

w3q
ux3 3

ux3 4

Fig. 1. Reduction in the proof of Theorem 1. This is an example for the formulaC1 ∧ C2 ∧ C3 , where C1 = x1 ∨ x2 ∨ x3 , C2 = x2 ∨ x3 . C3 = x1 ∨ x3 ∨ x4 . A black
thin edge belongs to E \ (E1 ∪ E2 ); a blue thick edge belongs to E1 ; a red broken edge
belongs to E2 .
Table 1. Summary of the costs.

ci
ci
ci
ci

{vir , vit } {vir , vif } {vit , vif } {vir , r} {vir0 , vit0 } {vir0 , vif0 } {vit0 , vif0 } {vir0 , r}
0
1
1/n
1
0
0
1/n
1
1
0
1/n
1
0
0
1/n
1
{wjr , wjq }2 − 1/(2n)2 − 1/(2n){wjr , r} {wjq , u`j }1
1
1
1{wjr , u`j }1 if ` = xi , 2 otherwise
1 if ` = xi , 2 otherwise

up two vertices wjr , wjq , and for each literal ` of Cj we set up one vertex u`j . We
also use an extra vertex r. They are the vertices of G.
Next, we draw the edges of G. For each variable xi , we draw edges {vit , vif } ∈E1 , {vir , vit } ∈ E \ (E1 ∪ E2 ), {vir , vif } ∈ E \ (E1 ∪ E2 ), and {vir , r} ∈ E1 . For eachclause Cj we draw an edge {wjr , wjq } ∈ E2 , {wjr , r} ∈ E1 , and for each literal `of Cj we draw edges {wjr , u`j } ∈ E \ (E1 ∪ E2 ), {wjq , u`j } ∈ E1 . This completes
the description of G. Fig. 1 shows an example.
Now, we set up 2n cost functions, each of which is identified with a variable orits negation (i.e., a literal). Namely, for each positive literal xi , we define the costfunction ci and, Similarly, for a negative literal xi , we define the cost function ci .
The definition is as follows. They are summarized in Table 1: ci ({vir , vit }) = 0,ci ({vir , vif }) = 1, ci ({vit , vif }) = 1/n, ci ({vir , r}) = 1; for every i0 ∈ {1, . . . , n}\{i},ci ({vir0 , vit0 }) = 0, ci ({vir0 , vif0 }) = 0, ci ({vit0 , vif0 }) = 1/n, ci ({vir0 , r}) = 1; for everyj ∈ {1, . . . , m} and every literal ` of the clause Cj , ci ({wjr , wjq }) = 2 − 1/(2n),ci ({wjr , r}) = 1, ci ({wjq , u`j }) = 1, andci ({wjr , u`j }) =(1 if ` = xi ,2 otherwise.

6

Yoshio Okamoto and Takeaki Uno

Similarly, ci ({vir , vit }) = 1, ci ({vir , vif }) = 0, ci ({vit , vif }) = 1/n, ci ({vir , r}) = 1;
for every i0 ∈ {1, . . . , n} \ {i}, ci ({vir0 , vit0 }) = 0, ci ({vir0 , vif0 }) = 0, ci ({vit0 , vif0 }) =1/n, ci ({vir0 , r}) = 1; for every j ∈ {1, . . . , m} and every literal ` of the clause
Cj , ci ({wjr , wjq }) = 2 − 1/(2n), ci ({wjr , r}) = 1, ci ({wjq , u`j }) = 1, and(1 if ` = xi ,r`ci ({wj , uj }) =2 otherwise.
Thus, we complete the construction of an instance of MC-MCST.
We may prove that there exists a spanning tree of G which is minimum-costwith respect to some convex combination of the ci and the ci , i ∈ {1, . . . , n} if
and only if the given SAT instance is satisfiable. We omit the detail here due tothe page limitation in this proceedings version.
utHence, we give up adapting the binary partition method, and try anothermethod.
3.2

Reverse Search Method

The reverse search method, proposed by Avis & Fukuda [1], is one of the mostpowerful techniques in enumeration algorithmics. Let G = (V, E) be a given
undirected connected graph, and we want to enumerate the spanning trees in G.
To do this, we set up a rooted tree R on the spanning trees of G, namely, eachnode of R is a spanning tree of G. The enumeration will be done by traversing R
in a depth-first-search manner, but we do not store the entire rooted tree itself;
we just specify a parent-child relation which implicitly defines R. In enumeration,
we recursively move to children by the depth first search. Therefore, to design
an efficient reverse-search algorithm it is enough for us to provide a parent-childrelation so that we can find a parent/child efficiently. Since we do not need tostore the entire family of spanning trees, but only a spanning tree under current
investigation, this enables us to obtain an algorithm which runs in polynomial
time delay and polynomial space. See Avis & Fukuda [1] and Nakano & Uno [6]for detail.
First of all, we define an adjacency relation on the family of spanning treesof G. Two distinct spanning trees T and T 0 of G are adjacent if the symmetricdifference of T and T 0 is of size two. Through this adjacency relation, we naturally
define the undirected graph G(G) which has the spanning trees of G as the nodeset. We can easily see that the number of nodes adjacent to one node is O(|V ||E|),and it is well-known [9, Exercise 2.1.62] that G(G) is connected.
On G(G) we define a rooted tree R. For this purpose, we assume that theedges of G are labeled according to some fixed total order ≺ as e1 ≺ e2 ≺ · · · ≺em . Then, the root of R is defined as a (unique) lexicographically maximum
spanning tree with respect to ≺, and a parent of a spanning tree T of G in
the rooted tree R is a (unique) lexicographically maximum neighbor of T in
G(G). This parent-child relation gives a well-defined rooted tree, and we canfind a root, a parent of a non-root spanning tree, and the children of a non-leaf

Enumeration Problems in Multi-Criteria Optimization

7

spanning tree in polynomial time. Therefore, this leads to an algorithm runningin polynomial-time delay and polynomial space for enumerating the spanning
trees in an undirected connected graph.
Let us try to generalize this approach to MC-MCST. We are given an undirected connected graph G = (V, E) and k edge-cost functions c1 , . . . , ck . In thiscase, we consider the subgraph of G(G) induced by the feasible spanning trees(i.e., to be enumerated in MC-MCST). Denote this induced subgraph by GM (G).
Although GM (G) depends on the edge-cost functions, we think them fixed thus
do not include in the notation for convenience. Ehrgott [2] showed that the graph
GM (G) is always connected. Therefore, we can define a rooted tree R on GM (G).
The most natural way is to use the same strategy as in enumeration of the spanning trees of a connected graph. Namely, we assume that the edges of G arelabeled according to some fixed total order ≺ as e1 ≺ e2 ≺ · · · ≺ em . Then, theroot of R is defined as a (unique) lexicographically maximum spanning tree withrespect to ≺, and a parent of a spanning tree T of G in the rooted tree R is a
(unique) lexicographically maximum neighbor of T in GM (G).
However, as opposed to the spanning trees enumeration case, for MC-MCST
we have (at least) two troubles here. The first problem is that we do not know
how to find a root in polynomial time. Actually, a greedy method fails since there
can be many ≺-maximal feasible spanning trees in GM (G). The second problem
is even worse: the graph R may not be connected. Therefore, the rooted tree is
not well-defined in general.
Hence, we need to devise another way to specify a rooted tree on GM (G) if
we wish to solve MC-MCST via reverse search.

4

The Proposed Algorithm

In our reverse-search algorithm for MC-MCST, we use GM (G) defined in theprevious section. Then, we have to define a promised rooted tree R. For thispurpose, we associate the following type of sequence to each feasible spanning
tree. We assume that the edges of G are labeled according to some fixed totalorder ≺ as e1 ≺ e2 ≺ · · · ≺ em . This order ≺ will be used to break a possibletie. For a feasible spanning tree T of G, let λT ∈ IRk be a lexicographicallymaximum barycentric coordinate of a convex combination of c1 , . . . , ck which T
minimizes. The following lemma shows that λT can be computed in polynomial
time.

Lemma 2. For every feasible spanning tree T of G, the vector λT can be foundin polynomial time.

8

Yoshio Okamoto and Takeaki Uno

Proof. We can phrase the problem in the following form.
lex-max.
subj. toλkXXe∈T i=1kX

λi ci (e) ≤kXX

λi ci (e) for all feasible T 0 adjacent to T,e∈T 0 i=1

λi = 1,i=1λi ≥ 0for all i ∈ {1, . . . , k}.

Note that in the first constraint we do not need to take into account all of thespanning trees of G, but we only need the spanning trees adjacent to T . Thisis due to the convexity (or matroid property) of the minimum-cost spanning
tree problem (we omit the detail). Since the number of spanning trees adjacent
to T is O(|V ||E|), the number of constraints is polynomial. This lexicographic
maximization problem can be solved by maximizing λi one by one in increasingorder of i ∈ {1, . . . , k}, and each maximization is reduced to a linear program.
Thus, using any polynomial-time algorithm for linear programming, we can solve
the problem in polynomial time.
ut
The root of R is chosen as a feasible spanning tree R of G which has alexicographically maximum λT among all feasible spanning tree T . Namely, sucha barycentric coordinate λR should satisfy (λR )1 = 1 and (λR )i = 0 for alli ∈ {2, . . . , k}. Thus, R is a minimum-cost spanning tree with respect to c1 .
If there are several minimum-cost spanning trees with respect to c1 , then wechoose a ≺-maximum one as a root. Such a tree R is unique, and can be found inpolynomial time by any polynomial-time minimum-cost spanning tree algorithm.
To specify the parent of a non-root feasible spanning tree T of G, we distinguish two cases. In the first case, we assume that λT = (1, 0, 0, . . . , 0)> . Then,
T and R both minimize c1 . Therefore, as the following lemma certifies, we canobtain another minimum-spanning tree with respect to c1 from T by deleting
one edge from T and adding one edge from R.
Lemma 3. Let G = (V, E) be a connected undirected graph, c : E → IR+ be a
non-negative edge-cost function, and T1 , T2 ⊆ E be minimum-cost spanning treesof G with respect to c. Then, there exist two edges e1 ∈ T1 \ T2 and e2 ∈ T2 \ T1
such that (T2 ∪ {e1 }) \ {e2 } is also a minimum-cost spanning tree of G withrespect to c.
Although this is a well-known fact as, for example, in [9, Exercise 2.3.13], wegive a proof here since we actually use the argument in the constructive proof
below for the construction of our rooted tree.
Proof. Let us choose a minimum-cost edge e1 ∈ T1 \ T2 , namely c(e1 ) ≤ c(e)for every e ∈ T1 \ T2 . Then, we can see that T2 ∪ {e1 } embraces a uniquecycle, say C. Note that C contains e1 . Now, we choose a maximum-cost edge

Enumeration Problems in Multi-Criteria Optimization9e2 ∈ C \ {e1 } ⊆ T \ {e1 }, namely, c(e2 ) ≥ c(e) for every edge e ∈ C \ {e1 }. Then,
T = (T2 ∪ {e1 }) \ {e2 } is a spanning tree of G.
Now we look at the cost. If c(e1 ) < c(e2 ), then it follows that c(T ) = c(T2 ) +c(e1 ) − c(e2 ) < c(T2 ). Hence it contradicts the minimality of T2 . On the other
hand, suppose that c(e1 ) > c(e2 ). Then by the choice of e1 it follows that c(e) >c(e2 ) for all e ∈ T1 \ T2 . We consider a (unique) cycle C 0 in T1 ∪ {e2 } and pick anarbitrary edge from e0 ∈ C 0 \{e2 }. Then, T 0 = (T1 ∪{e2 })\{e0 } is a spanning treeof G and the cost is c(T 0 ) = c(T1 ) + c(e2 ) − c(e0 ) < c(T1 ). Hence it contradicts
the minimality of T1 . Thus, it must hold that c(e1 ) = c(e2 ) and hence T is alsoa minimum-cost spanning tree of G with respect to c.
ut
The parent of T is constructively defined as follows. First we choose a minimum-cost edge eR ∈ R \ T (with respect to c1 ), and if there are several choices,
we choose a ≺-maximum one. This makes the choice of eR unique. Then, T ∪{eR }contains a cycle C and we choose a maximum-cost edge eT ∈ C \ {eR } (withrespect to c1 ), and if there are several choices, we choose a ≺-minimum one. Fromthese choices, define the parent of T as T 0 = (T ∪{eR })\{eT }. From the discussion
above, we can see that T 0 is a feasible spanning tree and |R4T 0 | < |R4T |. Notethat T 0 can be found in polynomial time from T .
In the next case, we assume that λT 6= (1, 0, 0, . . . , 0)> . Then, we consider
the corresponding λT . Let j ∈ {2, . . . , k} be the minimum index such that
(λT )j 6= 0. Then, we take µ ∈ IRk obtained from λT by increasing the firstcomponent by a sufficiently small ε > 0 and decreasing the j-th component by
ε. By our assumption for the second case, we can see that such an ε exists whichkeeps µT to be a barycentric coordinate. Let S be a minimum-cost spanningPk
tree of G with respect to i=1 µi ci . If there are several minimum-cost spanning
trees, then we choose a ≺-maximum one. By the lexicographic maximality of
λT and the fact that µ is lexicographically larger than λT , we see that S isdifferent from T . Since ε P
is sufficiently small, S is also a minimum-cost spanningktree with respect to c = i=1 (λT )i ci . Hence, by Lemma 3 similarly to the firstcase, we choose an edge eS ∈ S \ T such that c(eS ) ≤ c(e) for all e ∈ S \ T (ifthere are more than one such edges, then we choose the ≺-maximal one), andfor a (unique) cycle C of T ∪ {eS } we choose an edge eT ∈ C \ {eS } such thatc(eT ) ≤ c(e) for all e ∈ C \ {eS } (if there are more than one such edges, then wechoose the ≺-minimal one). Then, we can see (from the proof of Lemma 3) thatT 0 = (T ∪ {eS }) \ {eT } is a minimum-cost spanning tree with respect to c, and|S4T 0 | < |S4T | holds. We define the parent of T as T 0 , and we can find T 0 in
polynomial time from T . In this way, the definition of a parent is completed. By
the construction, the parent of T is adjacent to T in GM (G), and it is unique.
Furthermore, the next lemma is important.
Lemma 4. Let G = (V, E) be a connected undirected graph and c1 , . . . , ck : E →IR+ be non-negative edge-cost functions. Then, the parent-child relation defined
above is well-defined. Namely, from a non-root feasible spanning tree T ⊆ E, by
moving to the parent step by step we can arrive at the root R.

10

Yoshio Okamoto and Takeaki Uno

Proof. Let T be a non-root feasible spanning tree and T 0 its parent. The investigation is divided into two parts according to the case distinctions above.
Let us first consider when the first case is applied. In this case it holds that
λT 0 = λT = (1, 0, 0, . . . , 0)> and |R4T 0 | < |R4T |. Therefore, we can arrive R
at some point.
Next let us consider when the second case is applied. Let T = T0 , T 0 = T1 , andin general denote the parent of Tj by Tj+1 . This construction can continue unless
λTj = (1, 0, 0, . . . , 0)> . Hence, it suffices to show that for every j there exists
some j 0 > j such that λTj0 is lexicographically larger than λTj . If this is true, thenat some point (when the index is j, say) it must hold that λTj = (1, 0, 0, . . . , 0)>
and the case is reduced to the first one.
Fix an arbitrary j. We are done if λTj+1 is lexicographically larger than λTj .
Therefore, we assume λTj+1 = λTj . Let Sj be a spanning tree used to obtain Tj
as S was used to obtain T in the text above. Since Sj and Sj+1 are dependent
only on λTj and λTj+1 respectively, it holds that Sj = Sj+1 . However, for any i
it holds that |Si 4Ti+1 | < |Si 4Ti |. Therefore, there cannot be an infinitely longsequence Si = Si+1 = Si+2 = · · · of identical spanning trees. Thus, there must
exist some j 0 > j such that λTj0 is lexicographically larger than λTj .
ut
From the discussion above, we finally obtain the following theorem.
Theorem 5. By the reverse search algorithm described above, we can solve MCMCST in polynomial-time delay and polynomial space.

5

Generalization

The reverse search algorithm in the previous section can be generalized in several
ways. A close inspection of the discussion shows that we only used the matroid
property of the minimum-cost spanning tree problem in the algorithm. Therefore,
we can conclude that the multi-criteria minimum-cost base problem in matroids
can be solved in polynomial-time delay and polynomial space, when a matroid
is given as the independent set oracle. More generally, we can solve the multicriteria minimum-cost base problem in submodular systems in polynomial-timedelay and polynomial space when a submodular function is given as a valuegiving oracle. To this end, we need to identify the adjacent bases of a given basein a submodular system. This task is an instance of the submodular function
minimization problem, which can be solved in polynomial time [4].
As an extreme generalization, we can consider the multi-criteria linear programming. In a linear program, we are given a system of inequalities Ax ≥ b, x ≥0 where A ∈ IRm×n is a matrix, and b ∈ IRm is a vector. Then we want to find,for a given c ∈ IRn , a solution x to the inequality system which minimizes c> x.
The inequality system above defines a convex polyhedron, called the feasible
region of the problem. Here we assume (without loss of generality) that it isbounded and non-empty. With this assumption, a feasible region has at least
one extreme point, and furthermore there exists an optimal solution which isEnumeration Problems in Multi-Criteria Optimization

11

an extreme point of the polyhedron. We call such a solution an extreme optimal solution. In a multi-criteria linear program, we are given a system of linear inequalities Ax ≥ b, x ≥ 0, and we want to enumerate the extreme optimal solutions which minimize some convex combination of given k cost vectors
c1 , . . . , ck ∈ IRn .
Problem: MC-LP
Input: a matrix A ∈ IRm×n , two vectors b ∈ IRm and c1 , . . . , ck ∈ IRn
Enumerate: the extreme solutions x to the inequality system Ax ≥b, x ≥ 0 which minimize some convex combination of c1 , . . . , ck .
We call an instance of MC-LP non-degenerated if every extreme point of thepolyhedron determined by the given inequality system lies on n facets.
Theorem 6. The non-degenerated MC-LP can be solved in polynomial-time delay and polynomial space.
Proof (sketch). In the feasible region every extreme solution is adjacent to otherextreme solutions through edges. This adjacency naturally defines an undirected
graph, and in the same way as we did for MC-MCST we can implicitly specify arooted tree in this graph. For a non-degenerated linear program, every extreme
solution is adjacent to at most n other extreme solutions, and the adjacentextreme solutions can be found by pivot operations in polynomial time. The
connectedness of the analogue of GM (G) is known [3]. Furthermore, we canobtain propositions similar to Lemmas 2, 3 and 4 (the proofs are similar), andthus Theorem 6 is proven.
utNote that MC-LP with possible degeneracy seems very difficult to tackle. It is
known that the vertex enumeration of a degenerated convex polyhedron, whichcorresponds to the enumeration of the extreme solutions to a single-criterion
linear program, cannot be performed in polynomial total time (hence not inpolynomial-time delay and polynomial space) unless P = NP [5].

6Concluding Remark

We have looked at some multi-criteria optimization problems from the viewpoint of enumerative algorithmics. There seem many problems in multi-criteria
optimization to which the algorithm theory can potentially contribute.
A key fact in our reverse search algorithm for MC-MCST is that there areat most polynomially many spanning trees adjacent to one spanning tree. This
is no longer the case if we consider the bipartite matching problem. So far,
we do not know how to obtain a polynomial-time delay and polynomial-spacealgorithm for the multi-criteria assignment problem (i.e., maximum bipartite
matching problem). We can show that a natural binary partition approach does
not work in the same way as we did in Section 3. We leave this issue as an open
problem.

12

Yoshio Okamoto and Takeaki Uno

Another problem is concerned with Lemma 2, where we saw that λT canbe obtained in polynomial time. However, it uses a polynomial-time linear programming algorithm, hence not a strongly polynomial-time algorithm. We do
not know whether it can be computed in strongly polynomial time.
Acknowledgments This work started when the authors visited Institute of Theoretical Computer Science, ETH Zurich in 2005. The authors are grateful to Emo
Welzl and his group members for hospitality. A part of this research is supported
by Grant-in-Aid for Scientific Research from Ministry of Education, Science andCulture, Japan, and Japan Society for the Promotion of Science.

References
1. D. Avis and K. Fukuda, Reverse search for enumeration. Discrete Applied Mathematics 65 (1996) 21–46.
2. M. Ehrgott, On matroids with multiple objectives. Optimization 38 (1996) 73–84.
3. M. Ehrgott, Multicriteria Optimization (Second Edition). Springer, Berlin Heidelberg, 2005.
4. M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization (2nd Corrected Edition). Springer-Verlag, Berlin New York,
1993.
5. L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, and V. Gurvich, Generating allvertices of a polyhedron is hard. Proc. 17th SODA (2006) 758–765. Full version toappear in Discrete & Computational Geometry.
6. S.-I. Nakano and T. Uno, Constant time generation of trees with specified diameter.
Proc. 30th WG (2004) 33–45.
7. C. Papadimitriou and M. Yannakakis, On the approximability of trade-offs andoptimal access of web sources. Proc. 41st FOCS (2000) 86–92.
8. E.L. Ulungu and J. Teghem, The two phase method: an efficient procedure to solve
bi-objective combinatorial optimization problems. Foundations of Computing and
Decision Sciences 20 (1995) 149–165.
9. D.B. West, Introduction to Graph Theory (Second Edition). Prentice Hall, Upper
Saddle River, 2001.
10. C. Zaroliagis, Recent advances in multiobjective optimization. Proc. 3rd SAGA
(2005) 45–47.
11. E. Zitzler, M. Laumanns, and S. Bleuler, A tutorial on evolutionary multiobjective optimization. In: X. Gandibleux, M. Sevaux, K. Sörensen, V. T’kindt, eds.,
Metaheuristics for Multiobjective Optimisation, Lecture Notes in Economics andMathematical Systems 535 (2004) pp. 3–38.