Abstract. A Robinson space is a dissimilarity space [Formula: see text] (i.e., a set [Formula: see text] of size [Formula: see text] and a dissimilarity [Formula: see text] on [Formula: see text]) for which there exists a total order [Formula: see text] on [Formula: see text] such that [Formula: see text] implies that [Formula: see text]. Recognizing if a dissimilarity space is Robinson has numerous applications in seriation and classification. An mmodule of [Formula: see text] (generalizing the notion of a module in graph theory) is a subset [Formula: see text] of [Formula: see text] which is not distinguishable from the outside of [Formula: see text]; i.e., the distance from any point of [Formula: see text] to all points of [Formula: see text] is the same. If [Formula: see text] is any point of [Formula: see text], then [Formula: see text], and the maximal-by-inclusion mmodules of [Formula: see text] not containing [Formula: see text] define a partition of [Formula: see text], called the copoint partition. In this paper, we investigate the structure of mmodules in Robinson spaces and use it and the copoint partition to design a simple and practical divide-and-conquer algorithm for recognition of Robinson spaces in optimal [Formula: see text] time.

Gomory--Hu (GH) trees are a classical sparsification technique for graph connectivity. For an edge-capacitated undirected graph $G=(V,E)$ and subset $Z \subseteq V$ of terminals, a GH tree is an edge-capacitated tree $T=(Z,E(T))$ such that for every $u,v \in Z$, the value of the minimum capacity $uv$ cut in $G$ is the same as in $T$. It is well-known that there does not always exist a GH tree which is a subgraph (or minor if $Z \neq V$) of $G$. We characterize those graph-terminal pairs $(G,Z)$ which always admit such a tree. We show that these are the graphs which have no terminal-$K_{2,3}$ minor, that is, a $K_{2,3}$ minor whose nodes each corresponds to a terminal. We then show that the pairs $(G,Z)$ which forbid such $K_{2,3}$ terminal-minors arise, roughly speaking, from so-called Okamura--Seymour instances, planar graphs whose outside face contains all terminals. One consequence is a result on cut-sufficient pairs $(G,H)$, that is, multiflow instances where the cut condition is sufficient to guarantee a multiflow for any capacity/demand weights on $G/H$. Our results characterize the pairs $(G,Z)$ where $G$ is a graph, $Z \subseteq V(G)$, such that $(G,H)$ is cut-sufficient for any demand graph $H$ on $Z$.

The Directed Steiner Tree (DST) problem is a cornerstone problem in network design. We focus on the generalization of the problem with higher connectivity requirements. The problem with one root and two sinks is APX-hard. The problem with one root and many sinks is as hard to approximate as the directed Steiner forest problem, and the latter is well known to be as hard to approximate as the label cover problem. Utilizing previous techniques, we strengthen these results and extend them to undirected graphs. Specifically, we give an Ω( k ϵ ) hardness bound for the rooted k -connectivity problem in undirected graphs. As a consequence, we obtain an Ω( k ϵ ) hardness bound for the undirected subset k -connectivity problem. Additionally, we give a result on the integrality ratio of the natural linear programming relaxation of the directed rooted k -connectivity problem.

We consider the approximability of the maximum edge-disjoint paths problem (MEDP) in undirected graphs, and in particular, the integrality gap of the natural multicommodity flow based relaxation for it. The integrality gap is known to be \(\Omega(\sqrt{n})\) even for planar graphs [11] due to a simple topological obstruction and a major focus, following earlier work [14], has been understanding the gap if some constant congestion is allowed. In planar graphs the integrality gap is O (1) with congestion 2 [19,5]. In general graphs, recent work has shown the gap to be O (polylog( n )) [8,9] with congestion 2. Moreover, the gap is Ω(log Ω( c ) n ) in general graphs with congestion c for any constant c ≥ 1 [1]. It is natural to ask for which classes of graphs does a constant-factor constant-congestion property hold. It is easy to deduce that for given constant bounds on the approximation and congestion, the class of “nice” graphs is minor-closed. Is the converse true? Does every proper minor-closed family of graphs exhibit a constant-factor constant-congestion bound relative to the LP relaxation? We conjecture that the answer is yes. One stumbling block has been that such bounds were not known for bounded treewidth graphs (or even treewidth 3). In this paper we give a polytime algorithm which takes a fractional routing solution in a graph of bounded treewidth and is able to integrally route a constant fraction of the LP solution’s value. Note that we do not incur any edge congestion. Previously this was not known even for series parallel graphs which have treewidth 2. The algorithm is based on a more general argument that applies to k -sums of graphs in some graph family, as long as the graph family has a constant-factor constant-congestion bound. We then use this to show that such bounds hold for the class of k -sums of bounded genus graphs. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

The Directed Steiner Tree (DST) problem is a cornerstone problem in network design. We focus on the generalization of the problem with higher connectivity requirements. The problem with one root and two sinks is APX-hard. The problem with one root and many sinks is as hard to approximate as the directed Steiner forest problem, and the latter is well known to be as hard to approximate as the label cover problem. Utilizing previous techniques (due to others), we strengthen these results and extend them to undirected graphs. Specifically, we give an Ω(k∊) hardness bound for the rooted k-connectivity problem in undirected graphs; this addresses a recent open question of Khanna. As a consequence, we also obtain the Ω(k∊) hardness of the undirected subset k-connectivity problem. Additionally, we give a result on the integrality ratio of the natural linear programming relaxation of the directed rooted k-connectivity problem.