Packing Steiner trees: polyhedral investigations

LetG=(V, E) be a graph andT⊆V be a node set. We call an edge setS a Steiner tree forT ifS connects all pairs of nodes inT. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graphG=(V, E) with edge weightsw _e , edge capacitiesc _e ,e∈E, and node setT ₁,…,T _N , find edge setsS ₁,…,S _N such that eachS _k is a Steiner tree forT _k , at mostc _e of these edge sets use edgee for eache∈E, and the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from a routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing problem from a polyhedral point of view and define an associated polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper (in this issue).     

Inverse monoids and rational Schreier subsets of the free group

An inverse monoidM is an idempotent-pure image of the free inverse monoid on a setX if and only ifM has a presentation of the formM=Inv<X:e_o=f_i, i∈I>, wheree _i ,f _i are idempotents of the free inverse monoid: every inverse monoid is an idempotent-separating image of one of this type. IfR is anR-class of such an inverse monoid, thenR may be regarded as a Schreier subset of the free group onX. This paper is concerned with an examination of which Schreier subsets arise in this way. In particular, ifI is finite, thenR is a rational Schreier subset of the free group. Not every rational Schreier set arises in this way, but every positively labeled rational Schreier set does. Research supported by National Science Foundation grant #DMS8702019.     

Projective and indecomposableS-acts

LetS be a semigroup andE the set of all idempotents inS. LetS-Act be the category of allS-acts. LetC be a full subcategory ofS-Act which contains_s S and is closed under coproducts and summands. It is proved that, inC, anS-actP is projective and unitary if and only ifP≅ ∐ _{jϕ I} Se _i ,e _i ϕE. In particular,P is a projective, indecomposable and unitary object if and only ifP ≅Se for somee ∈E. These generalize some results obtained by Knauer and Talwar. Research partially supported by a UGC (HK) (Grant No. 2160092).     

Projective and indecomposableS-acts

LetS be a semigroup andE the set of all idempotents inS. LetS-Act be the category of allS-acts. LetC be a full subcategory ofS-Act which contains_s S and is closed under coproducts and summands. It is proved that, inC, anS-actP is projective and unitary if and only ifP≅ ∐ _{jϕ I} Se _i ,e _i ϕE. In particular,P is a projective, indecomposable and unitary object if and only ifP ≅Se for somee ∈E. These generalize some results obtained by Knauer and Talwar.     

On semi-infinite systems of linear inequalities

The ordered fieldR(M) consists of the realsR with a transcendentalM adjoined, which is larger than any realr ∈R. Given any semi-infinite matrix (s.i.m.) interpreted as linear inequalities:u ^tP_i≧c _i, ∀ _i ∈I, an arbitrary index set, it is also shown that the following are equivalent. (1) For every finiteJ ⊆I the systemu ^tP_i≧c _i,i ∈J is consistent, and (2) the s.i.m. has a solutionu ∈R(M) ⁿ. Some consequences for “duality gaps” are also given. These results were obtained as part of the activities of the Management Science Research Group and School of Urban and Public Affairs, Carnegie-Mellon University.     

On the automatic derivation of a set of geometric formulae

Leta, b, andc be the three sides of a triangleABC, a _i ,b _i ,c _i anda _e ,b _e , c_e be the lengths of the three internal and external bisectors of the three anglesA, B, andC respectively. It is easy to express the bisectors as formulae of the sides. In this paper, we solve a problem proposed by H. Zassenhaus: for any three different bisectors in {a_i, b_i, c_i, a_e, b_e, c_e}, finding the relations between each side of the triangle and the three chosen bisectors. We also prove that given any general values for three different bisectors (internal or external) of a triangle, we can not draw the triangle using a ruler and a pair of compasses alone. The formulae mentioned above are derived automatically using a general method of mechanical formula derivation.This work was partially supported by a Grant from Chinese NSF and by the NSF Grant CCR-917870.     

On fixing elements in matroid minors

LetF be a collection of 3-connected matroids which is (3, 1)-rounded, that is, whenever a 3-connected matroidM has a minor in F ande is an element ofM, thenM has a minor in F whose ground set contains.e. The aim of this note is to prove that, for all sufficiently largen, the collection ofn-element 3-connected matroids having some minor inF is also (3, 1)-rounded.This research was partially supported by the National Science Foundation under Grant No. DMS-8500494.     

Path-closed sets

Given a digraphG = (V, E), call a node setT ⊆V path-closed ifv, v′ εT andw εV is on a path fromv tov′ impliesw εT. IfG is the comparability graph of a posetP, the path-closed sets ofG are the convex sets ofP. We characterize the convex hull of (the incidence vectors of) all path-closed sets ofG and its antiblocking polyhedron inR ^v , using lattice polyhedra, and give a minmax theorem on partitioning a given subset ofV into path-closed sets. We then derive good algorithms for the linear programs associated to the convex hull, solving the problem of finding a path-closed set of maximum weight sum, and prove another min-max result closely resembling Dilworth’s theorem.     

Two Paths Joining Given Vertices in 2k-Edge-Connected Graphs

Let k≥2 be an integer and G = (V(G), E(G)) be a k-edge-connected graph. For X⊆V(G), e(X) denotes the number of edges between X and V(G) − X. Let {s_i, t_i}⊆X_i⊆V(G) (i=1,2) and X₁∩X₂=∅. We here prove that if k is even and e(X_i)≤2k−1 (i=1,2), then there exist paths P₁ and P₂ such that P_i joins s_i and t_i, V(P_i)⊆X_i (i=1,2) and G − E(P₁∪P₂) is (k−2)-edge-connected (for odd k, if e(X₁)≤2k−2 and e(X₂)≤2k−1, then the same result holds [10]), and we give a generalization of this result and some other results about paths not containing given edges.     

A RECOGNITION PROBLEM IN CONVERTING LINEAR PROGRAMMING TO NETWORK FLOW MODELS

The main goal of this paper is to study the following combinatorial problem.given a finite set E={e1,e2,…em} and a subset familly σ={S1,S2,…,Sn}of E,does there exist a tree T with the edge set E such that each induced subgraph T[Si] of Si is precisely a path (1≤i≤k)?     

On semigroups generated by restrictions of elliptic operators to invariant subspaces

Let A be the closed unbounded operator inL _p(G) that is associated with an elliptic boundary value problem for a bounded domainG. We prove the existence of a spectral projectionE determined by the set Γ = {λ;θ ₁≦argλ≦θ ₂} and show thatAE is the infinitesimal generator of an analytic semigroup provided that the following conditions hold: 1<p<∞; the boundary ϖΓ of Γ is contained in the resolvent setp(A) ofA;π/2≦θ<θ ₂≦3π/2 ; and there exists a constantc such that (I)││(λ-A)^-1││≦c/│λ│ for λ∈ϖΓ. The following consequence is obtained: Suppose that there exist constantsM andc such that λ∈p(A) and estimate (I) holds provided that |λ|≧M and Re λ=0. Then there exist bounded projectionE ⁻ andE ⁺ such thatA is completely reduced by the direct sum decompositionL _p(G)=E⁻L_p (G) ⊕E⁺L_p (G) and each of the operatorsAE ⁻ and—AE ⁺ is the infinitestimal generator of an analytic semigroup.     

Finding stabbing lines in 3-space

A line intersecting all polyhedra in a setℬ is called a “stabber” for the setℬ. This paper addresses some combinatorial and algorithmic questions about the setℒ(ℬ) of all lines stabbingℬ. We prove that the combinatorial complexity ofℒ(ℬ) has an upper bound, wheren is the total number of facets inℬ, andc is a suitable constant. This bound is almost tight. Within the same time bound it is possible to determine if a stabbing line exists and to find one. The research of M. Pellegrini was partially supported by Eni and Enidata within the AXL project, and by NSF Grant CCR-8901484. A preliminary version appeared in theProceedings of the Second ACM-SIAM Symposium on Discrete Algorithms, pp. 24–31.     

Disjoint homotopic paths and trees in a planar graph

In this paper we describe a polynomial-time algorithm for the following problem:given: a planar graphG embedded in ℝ², a subset {I ₁, …,I _p} of the faces ofG, and pathsC ₁, …,C _k inG, with endpoints on the boundary ofI ₁ ∪ … ∪I _p; find: pairwise disjoint simple pathsP ₁, …,P _k inG so that, for eachi=1, …,k, P _i is homotopic toC _i in the space ℝ²\(I ₁ ∪ … ∪I _p). Moreover, we prove a theorem characterizing the existence of a solution to this problem. Finally, we extend the algorithm to disjoint homotopic trees. As a corollary we derive that, for each fixedp, there exists a polynormial-time algorithm for the problem:given: a planar graphG embedded in ℝ² and pairwise disjoint setsW ₁, …,W _k of vertices, which can be covered by the boundaries of at mostp faces ofG;find: pairwise vertex-disjoint subtreesT ₁, …,T _k ofG whereT _i (i=1, …, k).     

Two point problems and analyticity of solutions of abstract parabolic equations

Fort ∈ [a, b], letA(t) be the unbounded operator inH ^0,p (G) associated with an elliptic-boundary value problem that satisfies Agmon’s conditions on the rays λ=±iτ, τ ≥0. Existence and uniqueness results are obtained for weak and strict solutions of two-point problems of the type (du/dt)−A(t) u(t) =f(t),E ₁(α)u (α)=u _α,E ₂ (β)u (β)=u _β. Here [α, β) χ- [a, b],E ₁ (α) andE ₂ (β) are spectral projections associated withA(α) andA(β) respectively, andA(α)E ₁ (α) and =A (β)E ₂ (β) are infinitesimal generators of analytic semigroups. WhenA(t) andf(t) are analytic in a convex, complex neighborhoodO of [a, b] we show that for someθ _i ,i=1,2, any solution ofdu/dt =A(t)u (t)=f(t) in [a, b] is analytic and satisfies the above equation in the setO∩{t; t ≠ a, t ≠ b, | arg (t −a) | <θ ₁, | arg (b −t) |θ ₂}. Research partially supported by N. N. F. grant at Brandeis University.     

For what filters is every reduced product saturated?

In this paper we shall characterize the filtersD such that for everyM _i,M _i,Π_i∈I M_i/D is λ-saturated (where λ>ℵ₀). The characterization is:D is λ-good,D is ℵ₀ incomplete andS(I)/D is λ-saturated.     

Illuminating high-dimensional convex sets

A setL of points in thed-spaceE ^d is said toilluminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d if for every setS _i inF and every pointx in the boundary ofS _i there is a pointv inL such thatv illuminatesx, i.e. the line segment joiningv tox intersects the union of the elements ofF in exactly {x}.The problem we treat is the size of a setS needed to illuminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d . We also treat the problem of putting these convex sets in mutually disjoint convex polytopes, each one having at most a certain number of facets.     

Matroid intersection algorithms

LetM ₁ = (E, 9₁),M ₂ = (E, 9₂) be two matroids over the same set of elementsE, and with families of independent sets 9₁, 9₂. A setI 9₁ 9₂ is said to be anintersection of the matroidsM ₁,M ₂. An important problem of combinatorial optimization is that of finding an optimal intersection ofM ₁,M ₂. In this paper three matroid intersection algorithms are presented. One algorithm computes an intersection containing a maximum number of elements. The other two algorithms compute intersections which are of maximum total weight, for a given weighting of the elements inE. One of these algorithms is primal-dual, being based on duality considerations of linear programming, and the other is primal. All three algorithms are based on the computation of an augmenting sequence of elements, a generalization of the notion of an augmenting path from network flow theory and matching theory. The running time of each algorithm is polynomial inm, the number of elements inE, and in the running times of subroutines for independence testing inM ₁,M ₂. The algorithms provide constructive proofs of various important theorems of matroid theory, such as the Matroid Intersection Duality Theorem and Edmonds' Matroid Polyhedral Intersection Theorem.Research sponsored by the Air Force Office of Scientific Research Grant 71-2076.     

Some remarks on subgroups determined by certain ideals in integral group rings

LetG be a group,ZG the integral group ring ofG andI(G) its augmentation ideal. Subgroups determined by certain ideals ofZG contained inI(G) are identified. For example, whenG=HK, whereH, K are normal subgroups ofG andH∩K⊆ζ(H), then the subgroups ofG determined byI(G)I(H)I(G), andI ³(G)I(H) are obtained. The subgroups of any groupG with normal subgroupH determined by (i)I ²(G)I(H)+I(G)I(H)I(G)+I(H)I²(G), whenH′⊆[H,G,G] and (ii)I(G)I(H)I(G) when degH ²(G/H′, T)≤1, are computed. the subgroup ofG determined byI ⁿ(G)+I(G)I(H) whenH is a normal subgroup ofG withG/H free Abelian is also obtained     

On the intersection of maximalm-convex subsets

A subsetS of a real linear spaceE is said to bem-convex providedm≧2, there exist more thanm points inS, and for eachm distinct points ofS at least one of the ( ₂ ^m ) segments between thesem points is included inS. InE, letxy denote the segment between two pointsx andy. For any pointx inSυE, letS _x ={y: xyυS}. The kernel of a setS is then defined as {xεS: S _x=S}. It is shown that the kernel of a setS is always a subset of the intersection of all maximalm-convex subsets ofS. A sufficient condition is given for the intersection of all the maximalm-convex subsets of a setS to be the kernel ofS.     

Packing,covering and decomposing of a complete uniform hypergraph into delta-systems

Anh-uniform hypergraph generated by a set of edges {E ₁,...,E _c} is said to be a delta-system Δ(p,h,c) if there is ap-element setF such that ∇F|=p andE _i⌢E _j=F,∀i≠j. The main result of this paper says that givenp, h andc, there isn ₀ such that forn≥n ₀ the set of edges of a completeh-uniform hypergraphK _n ^h can be partitioned into subsets generating isomorphic delta-systems Δ(p, h, c) if and only if . This result is derived from a more general theorem in which the maximum number of delta-systems Δ(p, h, c) that can be packed intoK _n ^h and the minimum number of delta-systems Δ(p, h, c) that can cover the edges ofK _n ^h are determined for largen. Moreover, we prove a theorem on partitioning of the edge set ofK _n ^h into subsets generating small but not necessarily isomorphic delta-systems.