...mostly algebraic nature. The families of problems covered here mostly include separation problems, problems on graphs and hypergraphs, and SAT problems.

Key words: hypergraphs; algebraic combinatorics; family of problems; cut tree; extremal combinatorics

MSC2000 subject classification: Primary: 05C15, 05C35, 05C40, 05C50, 05C65, 05D99

OR/MS subject classification: Primary: Networks/graphs, theory; secondary: mathematics, combinatorics

History: Received April 7, 2004; revised January 10, 2005.

1. Introduction. In common situation in combinatorial optimization, there is a family of problems defined over the same set of possible solutions, where one wants an optimal solution for every problem in this family. Some of these cases capture an amount of degeneracy, that is, there are solutions that are optimal for more than one problem. In these kinds of problems-solutions systems, we raise the question of how big a set we need, in order to supply an optimal solution for every problem.

As an example, consider the multiterminal min-cut family of problems. Let G = (V, E) be an edge-weighted graph with [absolute value of V] = n. For s, t [member of] V, the (s, t) min-cut problem is to find a minimum weight cut separating s and t in G. Gomory and Hu [9] proved that there is a set of only n - 1 cuts such that for each of the [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] problems there is at least one optimal solution in this set. We say that such a family of problems is (n - 1)-solvable.

Hassin [11] and Cheng and Hu [4] proved a stronger version of this result. Consider a set X. Let a cut denote a partition of X into two sets. Assign to each cut an arbitrary weight. The problem is to find, for every pair s, t [member of] X a minimum weight cut that separates it. Hassin [11] and Cheng and Hu [4] showed that even under this generalization, the problem is (n - 1)-solvable.

An interesting generalization of this problem is the k-PAIRS problem, in which every problem consists of k pairs of elements, and the problem is to find an optimal cut that separates all the pairs simultaneously. Hassin [11] proved that the family of k-pairs problems on a set of n elements is d-solvable with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We note that for k = 1 and k = 2 the value of the minimum k-pairs cut equals the multicommodity max flow between the pairs, and for a bigger k it constitutes an upper bound on the flow.

This framework is not restricted to 0-1 problems. For instance, Hassin [11] considered the k-CUT problem, which is another generalization of the min-cut problem. In this problem, the input is a k-element subset of X, and a solution is a partition of the set into k nonempty subsets, each containing one element out of the input k-tuple. Hassin showed that this family of problems is d-solvable for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Moreover, this d is the rank of the solution matrix for this problem (the solution matrix will be defined and discussed in the next section). Hassin generalized in this work a result of Lovasz [16], giving this bound for the number of edges in a k-forest, which is a k-uniform hypergraph with the property that for each edge there is a k-cut separating all of its vertices and does not do so to any of the other edges. The edges of such a hypergraph can be viewed as a family of k-cut problems where each problem has a solution--a k-cut--that does not solve any other problem. Another proof for Lovasz's result can be found in Parekh [17].

In some systems, we are able not only to prove the existence of the small-sized solutions set, but also to characterize its combinatorial structure, show an algorithm for finding it, and answer optimal solution queries using it. In the original work of Gomory and Hu [9], they also found a compact representation for the set of optimal solutions--a small-sized data structure containing all the n - 1 solutions. They showed that if one builds a graph where each edge (u, v) is assigned the weight of the minimum cut between u and v, then there exists a spanning tree of this graph whose n - 1 edges contain, for every problem (s, t), an edge corresponding to a minimum cut for (s, t). This highly regular structure is called the Gomory-Hu cut tree. Such a tree can be built by solving only n - 1 min-cut problems. Given s, t [member of] X, the (s, t) min-cut can be computed out of the tree in O(1) time if maintained properly.

Hassin [13] considered the family of xcut problems. In this set of problems one is given a pair s, t, and needs to find the optimal cut such that s and t are on the same side. Hassin showed a compact representation for all the optimal xcut solutions, analogous to the Gomory-Hu cut tree. This representation consists of a tree with one extra pair of elements, i.e., a base of the 2-forest matroid.

Hartvigsen [10] provided a compact representation for the k-cut and the k-pairs problems as well. This representation is based on matrices rather than graphs.

In the remainder of this section, we give an overview of the paper. In [section] 2 we provide several definitions and notation that will be used throughout the paper. In [section] 3 we give the necessary background for the three methods that we use to obtain the bounds. Section 4 contains our main results: In [section] 4.1 we consider the family of k-pairs problems, all defined over a common ground set X of n elements. We first give a new proof for the result by Hassin [11] mentioned earlier, stating that there exists a set of size k [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which contains an optimal solution for every problem in this family. We then consider some subfamilies of this family of problems. For the family of disjoint pairs problems we show that a smaller set exists, one with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] - 1 solutions. Strengthening the latter result, we show that for the case where each problem has exactly k disjoint pairs (instead of at most k), a set containing an optimal solution to every problem exists with only [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] cuts.

In [section] 4.2, we look at the problem of 2-coloring a hypergraph with at most k edges. Again all problems considered are defined over the same set of n elements. This family is an extension of the k-pairs one. We show that although the number of problems in this family is much bigger than for the k-pairs problem, there exists a set containing an optimal solution to every problem of the same size as the one whose existence was proved for the k-pairs, namely [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For the coloring problem of one hyperedge (k = 1) of size at least t, we show the existence of an (n - t + 1)-sized optimal solutions set, and that the Gomory-Hu tree of the complete graph on the n vertices contains such a set.

In [section] 4.3, we prove the existence of a small optimal-solutions set for a family of problems we call the k-in-one-side problems. The problem here is again to find a minimum cut of the n elements, but this time we require that the cut puts k given elements on the same side. The size of the set whose existence we prove is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Next we look at the subfamily that contains instances with exactly k elements, and show that a smaller set exists for it--one with cardinality [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We derive from the latter bound a result by Lovasz concerning critically chromatic hypergraphs, and show how to "translate" some of our other results into this language.

In [section] 4.4, we consider the very general s-SAT problem. This is the problem of finding a satisfying assignment of minimum cost for a given Boolean formula in CNF with n variables and at most s clauses. In the price of finding a somewhat worse bound than the bounds in previous sections, we generalize a substantial amount of {0, 1} problems. For the s-SAT family of problems, we show the existence of a set of optimal solutions of size [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In [section] 4.5, we investigate a special kind of problems-solutions systems that we call take-out problems, where one has to find the optimal subset of the ground set X after a number of elements have been removed from it, and possibly some other constraints have been applied. One such system is the MST-failure system, in which k edges may be taken out of a given graph with n vertices, and one has to find a minimum spanning tree for every instance. In this case we present a constructive combinatorial proof, i.e., one that tells us how to find the set of optimal solutions, whose size is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and do so without solving unnecessary problems. We also apply a theorem from extremal combinatorics by Frankl [6], to show an extension of this bound for a wider collection of take-out systems, although the proof is nonconstructive.

2. Terminology. A problems-solutions system consists of a pair (P, S) as follows: S is the set of all potential solutions. This set is common to all problems. Typically, the solutions themselves are subsets or partitions of some ground set. A problem p is defined by the subset [S.sub.p] [subset or equal to] S of solutions that are feasible for it--i.e., that conform with the problem constraints. P is a family of such problems, defined over the same set of solutions S. This defines a relation we call the feasibility relation of the system (P, S), which consists of the set of all pairs {([p.sub.i], [s.sub.j])} for which solution [s.sub.j] is feasible for problem [p.sub.i], i.e., [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Over the set of all possible solutions S, we define a weight function w: S [right arrow] [??] (or a cost function, depending on the context). We define w to be an arbitrary function, with no additional demands. In particular, it does not have to be nonnegative, additive, or one-to-one. Another way to look at w is as a weak total order, or a weak permutation over all solutions, determining for every two solutions whether one is better than the other. Solutions are allowed to have the same weight. The set of optimal solutions for problem p is defined by [S.sup.*.sub.p,w] = {s | s [member of] [S.sub.p] and [for all] s' [member of] [S.sub.p]...

NOTE: All illustrations and photos have been removed from this article.



More articles from Mathematics of Operations Research
Convergence to second-order stationary points of a primal-dual algorit..., November 01, 2005
Efficient algorithms for separated continuous linear programs: the mul..., November 01, 2005
Boundedness theorems for the relaxation method., November 01, 2005
Characterizations of the strong basic constraint qualifications., November 01, 2005
Convergence of a hybrid projection-proximal point algorithm coupled wi..., November 01, 2005

Looking for additional articles?
Search our database of over 3 million articles.

Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication name or publication date.

About Goliath
Whether you're looking for sales prospects, competitive information, company analysis or best practices in managing your organization, Goliath can help you meet your business needs.

Our extensive business information databases empower business professionals with both the breadth and depth of credible, authoritative information they need to support their business goals. Whether it be strategic planning, sales prospecting, company research or defining management best practices - Goliath is your leading source for accurate information.