Uncrossed Multiflows and Applications to Disjoint Paths
Abstract
A multiflow in a planar graph is uncrossed if the curves identified by its support paths do not cross in the plane. Recently, uncrossed flows have played a role in approximation algorithms for maximum disjoint paths in “fully-planar” instances, where the combined supply-plus-demand graph is planar. They are also used in algorithms to find low-congestion unsplittable flows for both fully-planar and single-source instances. For these two instance classes, any fractional multiflow can be converted into one that is uncrossed, which these algorithms then exploit to obtain their results.
We investigate the utility of uncrossed flow more generally and ask three key questions. First, are there other interesting planar multiflow instances that admit uncrossed flows (beyond fully-planar and single-source)? We answer affirmatively, demonstrating a new family of “pairwise-planar” instances whose fractional flows can be uncrossed. This family subsumes fully-planar but includes substantially more, such as (2-connected) fully-compliant series-parallel instances and some instances that have large clique demand graphs. Second, can we always round a fractional uncrossed flow to a “good” integral flow? We again answer positively. For maximization problems, we show any fractional uncrossed flow can be rounded to an integral flow with a constant fraction of its value. For congestion problems (where we must fully route all given demands), we give a rounding procedure that yields an integral multiflow with edge congestion 2. Consequently, we obtain constant-factor approximation algorithms for maximum disjoint paths and minimum congestion integer multiflow for pairwise-planar instances, and show such instances have a constant integral flow-multicut gap. Finally we ask, given an arbitrary planar instance, can we determine if there exists a congestion-1 uncrossed fractional flow (congestion setting) or find the maximum value uncrossed fractional flow (maximization setting)? For congestion, we show this problem is NP-hard, but finding uncrossed edge-disjoint paths is polytime solvable if the demands span a bounded number of faces. For maximization, we present a strong (almost-polynomial) inapproximability result.
Keywords and phrases:
Network Flows, Disjoint Paths, Planar Graphs, Crossing, Flow-Multicut Gap, Approximation Algorithms, Combinatorial OptimizationCategory:
APPROXFunding:
Chandra Chekuri: Supported in part by NSF grant CCF-2402667.Copyright and License:
2012 ACM Subject Classification:
Mathematics of computing Network flows ; Mathematics of computing Approximation algorithmsEditors:
Mohit Singh and Tom GurSeries and Publisher:
Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik
1 Introduction
In multicommodity flow, we are given an edge-capacitated supply graph and a set of source-sink pairs called demands or commodities. The demands are represented by a demand graph on the same node set as . Unless otherwise specified, graphs are undirected. We seek to route flow for the demands simultaneously, while respecting the capacities of the supply graph. There are two flavours of the multiflow problem. In the maximization setting, the objective is to find a flow that respects the capacities and maximizes the total sum of demands being routed. A feasible flow for needs to respect the capacities, but has freedom in the quantities of each demand that it routes. In the congestion setting, we are given target amounts for each . To be feasible for , a flow must (in addition to respecting capacities) fully route this amount for each demand. The objective is to determine whether can be satisfied in the capacities , or to find the minimum scaling factor such that can be satisfied in capacities .
Both fractional and integer versions of these problems are fundamental in combinatorial optimization (cf. [28]). Due to applications, the literature often emphasizes problems where the supply graph is planar [20]. The integer problems are hard even for planar supply graphs with 3 demand edges [33]. There exist, however, good approximation algorithms in so-called fully-planar instances where the joint supply-demand graph is planar222In this paper, if we say a multiflow instance is planar we only mean that the supply graph is planar. If we mean is planar, we will say fully-planar.. Often approximation algorithms follow a “relax-and-round” approach: relax the integer problem to its fractional version, find a fractional solution with “nice properties”, and then round the nice fractional solution to an integral solution.
A recurring “nice property” for planar multiflow is that the support paths (i.e. paths routing non-zero flow) do not cross in the plane. A multiflow satisfying this property is uncrossed (see Figure 1). It is known how to construct uncrossed multiflows for single-source ( is a star) and fully-planar instances, the latter using an algorithm of Matsumoto et al. [21]. This was recently leveraged to give constant-factor approximation algorithms for maximum edge-disjoint paths (MEDP) [15] and maximum node-disjoint paths (MNDP) [25, 24] for fully-planar instances. Very recently uncrossed flows were used to round fractional flows to unsplittable flows, routing the same demand quantities with small additive error, in both single-source [31] and fully-planar contexts [12]. In an unsplittable flow, each demand is routed on a single path.
In the above results, the uncrossed property of the fractional solution plays a key role, but the arguments are still specialized to the structure of . For example, for the fully-planar context, the uncrossed flow can be shown to be laminar: if one considers the family of cycles obtained by joining demand edges of to their support paths in , the result is a nested family of cycles in the plane. However, this same property does not hold for all instances that admit uncrossed flows. For instance, if is a cycle and consists of mutually crossing demands, then no paths within cross, but the path-plus-demand cycles are not nested. Our aim is to expand on a theory of uncrossed flows - when can we find them, and do they always admit good rounding algorithms, even outside the laminar/single-source cases? We have three motivating questions.
Question 1.
Do there exist other (interesting) families of satisfying the following property: for all capacities and demand values , if has a feasible (fractional) multiflow , then has a feasible multiflow that is uncrossed?
We say is an uncrossable layout if it satisfies the conditions of Question 1. For instance, if is fully-planar or is single-source, then is an uncrossable layout.
Question 2.
Suppose we are given a feasible fractional multiflow that is uncrossed (not assuming that the multiflow is laminar). Can we round to a “good” integer multiflow ? Specifically:
-
1.
(Congestion Setting) Given feasible uncrossed fractional multiflow for , can we compute an integer multiflow feasible for , for some constant ?
-
2.
(Maximization Setting) Given feasible uncrossed fractional multiflow for , can we compute an integer multiflow feasible for whose value is times that of , for some constant ?
The answer to Question 1 and both parts of Question 2 is: yes! First, we define a new class of and prove it gives uncrossable layouts.
Theorem 1.
Let be a planar graph with a fixed embedding. Let be such that for any pair of demands , and can be embedded inside (possibly different) faces of so they do not cross each other. Then is an uncrossable layout.
We say any satisfying this property is pairwise-planar (see Figure 6 in Section 3 for a depiction). The pairwise-planar class includes fully-planar as a subset, but includes substantially more. For instance, it contains layouts where is highly non-planar (and thus, do not admit laminar flows). It also includes the 2-connected fully-compliant333 is fully-compliant if is series-parallel and is series-parallel for every . family introduced in [7], which were not previously known to give uncrossed layouts to our knowledge. Pairwise-planar also differs from previous uncrossable layouts in an important structural sense. Namely, fully-planar and single-source are cut-sufficient (essentially, they have a Max-Flow Min-Cut theorem in the congestion setting), while some pairwise-planar are not.
As for Question 2, we prove the following results. We begin with the maximization setting.
Theorem 2.
Let be a planar maximization instance where is integral. Let be a feasible fractional flow that is uncrossed. There exists a feasible integral flow achieving an fraction of the value of . The integral flow can be computed in polynomial time.
We prove this result by establishing an “approximate integer decomposition property”, exploiting colouring results on a restricted class of string graphs (path intersection graphs). This integer decomposition also implies rounding holds for the weighted maximization version, where each has an associated weight , and a flow achieves value for each unit of -flow that it routes. Additionally, this result extends to node-capacitated multiflows (i.e. is a capacity function on nodes rather than edges).
For the congestion setting, we give a factor 2 rounding for converting a fractional uncrossed multiflow into an integral multiflow. Moreover, for an extra additive penalty we can round to an unsplittable flow.
Theorem 3.
Let be a planar congestion instance where are integral. Let be a feasible fractional multiflow that is strongly uncrossed444We defer the more technical definition of strongly uncrossed to Section 2.4. Importantly, the uncrossable layouts mentioned in this paper, including pairwise-planar, admit strongly uncrossed flows.. Then there exists both:
-
1.
an integral multiflow that is feasible for where for each , and
-
2.
an unsplittable multiflow that is feasible for where for every , where .
The integral and unsplittable multiflows can be computed in polynomial time.
Using Theorems 1, 2, and 3, we obtain constant-factor approximation algorithms for integer multiflow problems with pairwise-planar inputs.
Corollary 4.
There exist polynomial time constant-factor approximation algorithms for maximum edge-disjoint paths and maximum node-disjoint paths (and more generally, maximum integer multiflow), as well as minimum congestion integer multiflow, for inputs where is pairwise-planar.
Another interesting corollary concerns the integral flow-multicut gap, which is the ratio of the minimum capacity of a multicut (a set whose removal destroys all paths connecting demands of ) to the maximum value of an integral multiflow. Using their flow rounding algorithms, [17] [15] show the gap is constant for fully-planar , but the gap can be as large as even for planar supply graphs [14]. Combining our results with a theorem of [30], we obtain a constant gap for pairwise-planar instances.
Corollary 5.
For any maximization instance where is pairwise-planar, the minimum capacity of a multicut is at most times the maximum value of an integral multiflow.
The third key question requires slightly more motivation. If is not an uncrossable layout, it only means the structure of alone is insufficient to guarantee uncrossed solutions. However for specific capacities and demands we may still be able to find an uncrossed flow and round it. Thus it would be nice to have algorithms to determine whether (in the congestion setting) we can find a feasible fractional flow that is uncrossed, or (in the maximization setting) find the largest feasible flow that is uncrossed.
Question 3.
Suppose we are given an arbitrary planar multiflow instance. Can we solve the fractional multiflow problem if we constrain the feasible space to only allow uncrossed solutions? Specifically:
-
1.
(Congestion Setting) Given , can we determine whether there exists a feasible fractional multiflow that is uncrossed?
-
2.
(Maximization Setting) Given , can we compute a feasible fractional uncrossed multiflow whose value is (approximately) maximum amongst feasible uncrossed solutions (maximum uncrossed multiflow)?
These questions concern fractional multiflows and may feel like linear optimization problems. However the requirement of uncrossed flow paths makes these computationally much more challenging. Interestingly, the positive result of Theorem 2 can be combined with results of [8, 9] to establish strong almost-polynomial inapproximability for maximum uncrossed fractional multiflow (for both edge and node capacities).
Theorem 6.
For planar , maximum uncrossed fractional multiflow is not approximable to within a factor of for any assuming that . Moreover, there is no -approximation polynomial-time algorithm assuming that for some constant , . These results hold even when is maximum degree (or even is a wall graph) and the capacities are unit.
For the congestion setting, we prove the problem posed by Question 3 is NP-complete.
Theorem 7.
It is NP-complete to determine whether planar congestion instance has a feasible fractional uncrossed multiflow, even with unit-valued capacities and demands.
We remark that since this problem is not a linear program anymore, it is not even obvious that the problem is in NP, however we establish this as well. On the positive side, we show that finding uncrossed edge-disjoint paths can be (polytime) reduced to a node-disjoint paths instance. Hence we may find uncrossed solutions if is incident with a bounded number of faces using a result of Schrijver [27].
Theorem 8.
For instances where is planar, the edges of are incident with a bounded number of faces, and the capacities and demands are unit-valued, there is a polynomial time algorithm to find a feasible integral uncrossed multiflow for or declare none exists.
1.1 Organization of the Paper
Section 2 lays the groundwork for the theory of uncrossed flows, including detailed definitions. Section 3 discusses pairwise-planar instances, proves they admit uncrossed flows, and shows a constant integral flow-multicut gap. Section 4 covers our maximization results, both rounding (Theorem 2) and inapproximability (Theorem 6). The rounding result for congestion (Theorem 3) appears in Section 5. This manuscript includes the important aspects of each proof, though occasionally some details are deferred to the full version. The NP-completeness result (Theorem 7) and the integral uncrossed flow algorithm for a bounded number of -incident faces (Theorem 8) are deferred to the full version.
1.2 Related Work
Uncrossed flows have played a role in previous routing algorithms in planar graphs, such as Schrijver’s Homotopy Method [26] for node-disjoint paths. Most relevant are recent algorithms for maximum disjoint paths in fully-planar instances ( planar). In [17, 15], constant-factor approximation algorithms are given for maximum edge-disjoint paths, then extended to the node-disjoint setting in [25, 24]. These algorithms glue uncrossed flow paths to their respective demand edges to obtain an uncrossed (laminar) family of cycles in a planar graph. Our rounding algorithms are agnostic in the sense that they just operate on uncrossed flow paths, not assuming that demands lie within a face or that demands of a common face are non-crossing (indeed for our pairwise-planar instances, it is even possible for demands within a face to form a clique).
Uncrossed flows for fully-planar instances are typically constructed by a primal algorithm [21] that computes an uncrossed flow from scratch. We build on a different approach, taking a feasible flow (with many crossings) and iteratively decreasing total crossing (used for example in [18] to find cycles in higher-genus surfaces that cross at most once). We discuss obstacles faced in extending this to pairwise-planar in Section 3.
In [15] the initial flow is first rounded to a half-integral flow (using linear programming theory such as total unimodularity), then this half-integral flow is rounded to an integral flow using a 4-colouring of the (planar) intersection graph of the cycles. Extending to the node-disjoint setting, [25] uses a different argument, iteratively constructing a high-value solution by showing one can always find an “efficient” cycle that only intersects the other cycles on a small set of its nodes. Our rounding technique for Theorem 2 instead uses an approach based on establishing an “approximate integer decomposition property” [3, 5]. A key ingredient comes from looking at a subset of string graphs, which are the intersection graphs from curves in the plane. Specifically, we are interested in those that arise from curves that do not cross, studied for example in [11], and for which an important colouring result was proven by Fox and Pach [13]555This manuscript is unpublished, but the result is mentioned in [32] and their writeup was shared with us [23]..
The fully-planar maximum disjoint paths algorithms were extended [25, 18] to uncrossable families of cycles in higher-genus surfaces, yielding approximation algorithms for maximum disjoint paths when is embedded in a surface of genus ; the approximation ratio is polynomial in the genus . By contrast our work extends uncrossing techniques to a broader family of multiflow instances (pairwise-planar) while remaining in the plane. Some pairwise-planar instances have of arbitrarily high genus (e.g. contains a large clique), but we show nevertheless that they admit uncrossed flows in the plane in order to achieve constant-factor approximations. Results in [25] use the context of uncrossed cycle families, as defined by Goemans and Williamson [16], which is a combinatorial rather than topological definition of crossing.
The works of [17], [15] use their rounding algorithms to establish that the integral flow-multicut gap of fully-planar instances is constant. The integral flow-multicut gap can be as large as for general planar [14], so further restrictions on are needed to establish constant bounds. Other classes known to give constant integral flow-multicut gaps include: when is a tree [14], when is series-parallel [10] (note that these are less general than fully-compliant), when has fixed cyclomatic number [1], when has fixed genus [18], and when has fixed tree-width [4]. A common ingredient in these results is a bound on the fractional flow-multicut gap for -minor-free by [30, 19].
Other works using uncrossed flow come from the study of unsplittable flow in the congestion model (where specified demand quantities must be fully routed). For directed single-source planar instances ( is a star) [31], it is shown how to convert a feasible fractional uncrossed flow into an unsplittable flow that exceeds capacities by a small amount and has no increase in cost. For (undirected) fully-planar instances, [12] shows how to convert a laminar flow into an unsplittable flow with small capacity violation (no cost guarantee).
2 Uncrossed Multiflows
2.1 Multiflow Preliminaries
All graphs are undirected in this paper. Consider a supply graph and demand graph . Endpoints of edges in are terminals, and the edges themselves are demands or commodities. Together, define a layout666Sometimes in the literature, is called a multiflow topology. We avoid this term to avoid confusion with the topology of the plane. . For nodes , let denote the set of -paths. By path we always mean simple path. A multiflow is a function , where . Multiflows are fractional unless explicitly stated as integral. A multiflow can also be viewed as a collection of single-commodity flows . For , we let (the amount of flow on ). For we let (the amount of demand that is routed).
A maximization instance has the form , where are capacities. A multiflow is feasible for the instance if for every , . The objective is to maximize the value of a feasible multiflow, where the value of a multiflow is . If and we restrict to integral , this problem is the maximum edge-disjoint paths problem (MEDP). A weighted maximization instance also comes equipped with per-unit profits , in which case the value of is instead defined .
A congestion instance has the form , where are capacities and are demand values. A multiflow is feasible for the instance if for every we have and for every we have . As a decision problem, the goal is to determine whether has a feasible multiflow. As an optimization problem, the objective is to find the minimum such that has a feasible multiflow.
In either setting, we say an instance is planar if is planar. We emphasize that is not necessarily planar. We always assume a fixed embedding of planar graph .
2.2 Uncrossed Paths and Multiflows
First, we define what it means for paths to cross. Edge-disjoint paths can cross at a common node, but in general we need to consider common subpaths (see Figure 2).
Definition 9 (Crossing).
Let be a maximal shared subpath of paths and that does not include any of their endpoints. Say the ends of are and . The edges of incident with or have a clockwise ordering about in the plane. The paths cross at if the edges of and alternate clockwise about . That is, if and , the edges occur or clockwise about . Two paths are uncrossed if they do not cross at any such subpath777We emphasize that paths can only cross at maximal common subpaths that do not contain their endpoints. Both paths must have edges before and after the common subpath in order to cross. For example, if contains an endpoint of and is the maximal common subpath containing that endpoint, then and do not cross at ..
The support paths of a multiflow are the paths with . The following is the natural extension of “uncrossed” to the multiflow setting (though we discuss a stronger condition in Section 2.4).
Definition 10 (Uncrossed Multiflow).
A multiflow is uncrossed if its support paths are pairwise uncrossed.
We are interested in when a feasible multiflow can be converted into an uncrossed one that routes the same demands. Our discussion here focuses on the congestion setting, but still applies to the maximization setting (since we can define target demand values equal to whatever quantities routes). As shown in Figure 3, even if is feasible, it may not have an uncrossed feasible multiflow888In fact, it is not always possible to find an uncrossed flow with bounded congestion. One may modify the canonical grid instance [14] so it has a half-integral routing of demands, but any uncrossed multiflow incurs polynomial congestion.. However several classes do admit uncrossed solutions. We say is an uncrossable layout if for all , if has a feasible multiflow, then has a feasible uncrossed multiflow. Matsumoto et al. [21] give an algorithm that, given a feasible fully-planar ( planar) instance, produces a feasible uncrossed flow. Thus fully-planar layouts are uncrossable. It is also well-known that single-source layouts ( is a star) are uncrossable. Another uncrossable layout is given when is a cycle with parallel edges and is arbitrary, which we call ring layouts. In Section 3 we introduce pairwise-planar layouts and prove they are uncrossable.
2.3 Another View on Crossing: Parallelizations
There are more intuitive ways to think about uncrossed paths that we frequently use.
Widened Graph.
Suppose we “widen” , making its nodes into small disks and its edges into small channels. A family of pairwise uncrossed paths can have its paths drawn as curves simultaneously, each curve following the node disks and edge channels corresponding to its path, so that the curves are disjoint.
Parallelizations.
To avoid dealing with the formal topology of widened graphs, we use an equivalent notion based on “separating” the paths at each edge. Consider a family of paths and for each let . Let be obtained by replacing each with parallel copies of itself. Intuitively, the parallel edges represent the curves within the channel of .
Now, for each we decide on some one-to-one mapping from to the parallel class of in . For each , we obtain a path in whose edges are . This induces a family of edge-disjoint paths in . We call a parallelization of . If we (arbitrarily) orient each , it gives a linear ordering of . Different choices for yield different parallelizations. The family is pairwise uncrossed if and only if there is some parallelization that is pairwise uncrossed at every node of (rather than needing to consider longer shared subpaths). Using parallelizations helps us simplify subsequent definitions by assuming paths are edge-disjoint. Given a collection of paths, one can compute in polynomial time an uncrossed parallelization or find a crossing pair of paths.
Disk-Expansion.
After parallelization, we sometimes go a step closer to the widened graph idea by “expanding” a node . We draw a small disk with at its centre (small enough that its boundary intersects only , and hits each edge once). Where an edge copy intersects the boundary, we place a new node. We terminate the edges at these new nodes. For an uncrossed parallelization, it is then possible to (simultaneously) draw edges in the open interior of the disk between nodes that correspond to consecutive edges of the same path, such that the drawing is planar. An example is shown in Figure 4.
2.4 Strongly Uncrossed Multiflows
Consider an uncrossed multiflow. For any , its support paths have a clockwise ordering about (and ) given by the parallelization. We call the regions of the plane bounded between two consecutive paths sectors for this commodity (defined more formally in Section 5).
The proof of Theorem 3 uses that sectors of different commodities are non-crossing as sets - that is, we want that if are sectors of different commodities, then either or one contains the other. One might think this non-crossing property follows from Definition 10, however Figure 5 shows a counterexample999The desired non-crossing sector property does hold for uncrossed flows in leaf instances, where terminals all have degree 1. Moving terminals to leaves is a standard pre-processing operation, but is not safe for uncrossed flows - it may turn an uncrossable layout into one that is not. For example, ring instances admit uncrossed flows but Figure 3 (left) does not, even though it is obtained by adding leaves to a ring.. In the figure, no pair of flow paths cross, but the green -paths “slip between” the blue -paths to move between two distinct sectors. We define strongly uncrossed multiflows by imposing stricter restrictions on the support paths of different commodities at their terminals. Many layout classes admit strongly uncrossed flows, including fully-planar, single-source, and rings, as well as pairwise-planar.
Definition 11 (Quasicrossing, Strongly Uncrossed).
Let be a multiflow with a fixed parallelization (so we assume edge-disjoint support paths). Consider a node and the clockwise ordering of edges about . For a commodity , a type-1 -interval is (where ) such that are consecutive edges of a single support path for that transits through . A type-2 -interval is such that both terminate (different) support paths for at . Note that two paths cross at if and only if their corresponding type-1 intervals cross101010Two intervals cross if or .. We say a quasicrossing occurs at if there exists an -interval and an -interval that cross where and at least one of the intervals is type-2. If there are no crossings and no quasicrossings at any node, we say is strongly uncrossed.
2.5 Walk-Multiflows
It is standard for flows to only route on (simple) paths, since a flow walk could just be short-circuited into a flow path. Disturbingly, this operation is not benign in the uncrossed flow setting. The Keyhole Instance of Figure 3 is an example that requires the use of a non-simple flow trail to obtain an uncrossed solution. Since we would like to understand which instances have uncrossed solutions, we must consider trail-multiflows and walk-multiflows in addition to the usual path-multiflows. A trail can repeat nodes but not edges, while a walk can repeat both. Ultimately we can show our rounding results (Theorem 2, Theorem 3) and hardness results (Theorem 6, Theorem 7) presented earlier hold for all three models. The necessary modifications are minor and we defer the details to the full version.
3 Uncrossed Flows in Pairwise-Planar Instances
Here we introduce a new class of multiflow layouts and prove they are uncrossable. We assume a fixed embedding of . We say fits face of if both lie in (i.e. the demand could be drawn within the face). A layout is facial if each fits at least one face of (but demands fitting a common face may still cross each other).
Definition 12.
We say is pairwise-planar if is facial, and moreover for any pair , and can be embedded inside (possibly different) faces of so they do not cross each other.
Unlike fully-planar, we do not require simultaneous uncrossed embedding of all demands. This matters because a demand edge may fit multiple faces (a multi-faced demand). Figure 6 shows an example. However we emphasize that the embedding of is fixed and does not change as we embed different pairs of .
Clearly pairwise-planar generalizes fully-planar, but how substantial is this generalization? We briefly argue it is a much richer class. First, it is easy to construct examples where contains arbitrarily large cliques, meaning and have arbitrarily large genus (though remains planar). It also generalizes rings ( is a cycle with parallel edges, is arbitrary). This is worth remarking because fully-planar does not capture ring layouts. More broadly, pairwise-planar captures what are known as fully-compliant layouts (under mild connectivity assumptions). Introduced in [7], in such layouts is series-parallel and every satisfies that is series-parallel. In the full version, we argue the following.
Proposition 13.
If is fully-compliant and is 2-connected, then is pairwise-planar for any planar embedding of .
Pairwise-planar extends further than fully-planar and fully-compliant in another fundamental way through a property known as cut-sufficiency. For a multiflow instance , we say the cut condition holds if for every , , where denotes the edges with one end in and one end in . The cut condition is necessary, but not in general sufficient, for the existence of a feasible (fractional) multiflow. A layout is called cut-sufficient if, for all capacities and demands , the cut condition is sufficient for the existence of a feasible multiflow. The Max-Flow Min-Cut Theorem can be equivalently stated as: single-source are cut-sufficient. Understanding the relationship between the cut condition and feasibility is a fundamental question in network flows, and cut-sufficient instances tend to admit stronger integrality properties and approximation algorithms. A result of Seymour [29] shows that fully-planar are cut-sufficient, and Chekuri et al. [7] show that fully-compliant instances are cut-sufficient. However, pairwise-planar layouts need not be cut-sufficient. The quintessential examples of series-parallel layouts that are not cut-sufficient are the odd spindles111111In a spindle, where and consists of a simple -cycle between the nodes in the larger side of the partition and an edge between the two nodes in the other side. A spindle is odd if is odd. In some sense, the odd spindles characterize non-cut-sufficiency for series-parallel layouts, see [2]. [6, 2], but these are pairwise-planar.
3.1 Uncrossing Procedure
In this section we show why feasible pairwise-planar instances have uncrossed flows. We focus on congestion instances (where a feasible flow must satisfy all demands), since given a feasible flow for a maximization instance , one can define demand values and apply the congestion result. We present an inductive proof that a feasible uncrossed flow exists. It is straightforward to convert this into an algorithm, with one catch for polynomial time implementation that we explain at the end.
For fully-planar instances, [15, 12] use an algorithm by Matsumoto et al. [21] that builds an uncrossed flow from scratch starting from the zero flow. Our procedure has more in common with [18] (which concerns finding cycles in higher-genus surfaces that cross at most once) in that we begin with a (potentially highly crossing) feasible flow and “uncross” it bit-by-bit. The following is an important lemma.
Lemma 14.
Let be a planar congestion instance that is feasible. There exists a feasible flow such that every pair of support paths crosses at most once, and any pair of support paths that share a terminal do not cross.
We say a flow satisfying this property is almost-uncrossed. Proving this lemma formally is somewhat tedious, but such arguments have appeared in the literature before - the essence of the argument is in Lemma 1 of [22] and a similar method is used in [18]. Loosely, the argument goes as follows. Begin with a feasible flow . One can show that if a pair of support paths cross twice (or cross once but share a terminal), then one can re-route flow on their edges to decrease the “amount of crossing” between the two paths (“uncrossing” the two paths) and argue that this re-routing does not increase crossing with other support paths. Thus the total amount of crossing decreases, and we iterate until is uncrossed. For completeness we give a careful proof of this lemma (and precisely define “amount of crossing”) in the full version.
Lemma 14 immediately implies single-source layouts are uncrossable. With a small trick it also proves fully-planar layouts are uncrossable: augment the instance by adding leaves. That is, for each , add nodes into the interior of the face where is embedded, add supply edges , move the endpoints of the demand to , and extend the flow paths appropriately to route this instance. At first, adding leaves may actually increase the amount of crossing. However, since the demands do not cross, it can be shown that every pair of support paths that cross must cross at least twice. Then Lemma 14 allows one to conclude there exists a feasible uncrossed flow in the augmented instance. The leaves can then be contracted away without introducing any new crossing.
Extending this trick to pairwise-planar instances is not immediate. After adding leaves, it may not be the case that support paths that cross must cross at least twice. We cannot “commit” a demand to a particular face up front. Consider if a demand fits into two different faces and , but there are demands and that fit those respective faces and cross in those faces. If we add leaves into , then we can “uncross” support paths for and , however we cannot uncross support paths between and , and vice versa.
We take the following approach. Begin with a feasible flow that we want to uncross. We temporarily “commit” each demand to one of the faces it fits (if multi-faced, choose arbitrarily). We accept for now that flow paths of demands committed to the same face may cross, but compute a flow so that demands committed to different faces do not cross. In fact we aim for a more strict condition on : we show how to find so that, if we define as the multiflow corresponding to demands committed to face , the ’s are “uncoupled” from each other. Here, “uncoupled” is a structural property (defined precisely below) which guarantees that if we can uncross each separately, regardless of how we do so, we can still safely glue the resulting flows back together without introducing crossing. Then we can just focus on uncrossing each inductively/recursively. We now make this “committing” process and “uncoupled” property precise.
Definition 15 (Facial Decomposition).
Let be a facial multiflow instance. Let be the set of faces of . A facial decomposition is a collection of subgraphs of indexed by such that:
-
forms a partition of , and
-
for every face , every demand fits (but cannot necessarily all be embedded simultaneously in without crossing).
For a facial decomposition and a feasible flow , we let be the portion of used to route . Note that if is multi-faced, the facial decomposition still only puts into one of the ’s. Now we define the “uncoupled” condition and show that we can find a flow satisfying this property. We let denote the set of support paths of , and let denote the graph induced by the edges in those paths.
Definition 16 (Nested Supports Property).
Let be a facial multiflow instance, and let be a facial decomposition. For a flow and a face , we define the stellated support graph as follows: begin with the support graph , add a node into the interior of , and then for each demand add edges and , embedded (without crossing) in the face . We say satisfies the nested supports property if for every pair of distinct faces , the graph is entirely contained within a single face of the graph , and vice versa.
Lemma 17.
Let be a facial multiflow instance that is feasible. Let be a facial decomposition. There exists a feasible flow satisfying the nested supports property.
The proof of this lemma is slightly tricky to make rigorous, so we include only a sketch here and defer details to the full version.
Proof Sketch of Lemma 17.
We augment the instance by adding leaves into the faces: for every face and demand , add nodes into the face and supply edges of capacity equal to , and move the demand from to . We keep the same facial decomposition. We now invoke Lemma 14 to obtain a feasible flow that is almost-uncrossed for this new instance. It is not hard to show that for support paths associated with distinct faces, if we consider the embedded cycles obtained by joining the endpoints of the paths with their respective demand edges, that these cycles do not cross (though cycles associated with paths of the same face may cross).
Now, for each face , we let be the union of and all supply edges incident with the face itself (regardless of whether they are in the support). It is possible to argue that for distinct faces , must be contained in a single face of , and vice versa. Once this property is established, we argue the nested supports property holds for flow . Given such a flow, we show that we can focus on uncrossing each face’s flow independently.
Lemma 18.
Let be a facial multiflow instance. Let be a facial decomposition, and let be a feasible flow satisfying the nested supports property. For every , let be the capacity vector defined by and let be the demand vector restricted to . If for every , the instance has a feasible uncrossed solution , then is a feasible uncrossed solution for .
Proof.
The feasibility of is clear from the construction of the subproblems. Also observe that, by construction, still satisfies the nested supports property (since is a subgraph of for each face of ).
We prove that is uncrossed assuming each is uncrossed. It remains to check for distinct faces and , that and do not cross.
Consider two distinct faces . Let . Let be the demands routed by respectively. Suppose and cross, for the sake of contradiction. Consider the (simple) cycle in obtained as , where denotes concatenation. Since and cross, has some segment in the open exterior of and some segment in the open interior of . However, since is a simple cycle, these two segments of must lie in distinct faces of , contradicting that satisfies the nested supports property.
Using Lemma 18, we are able to reduce to finding a feasible uncrossed flow for each instance in isolation. No matter how we do this, we can safely combine the flows using the lemma. Importantly, to tackle the instance , we are allowed to re-commit multi-faced demands that were originally committed to to other faces.
Theorem 19.
Let be pairwise-planar and let be a congestion instance. If the instance is feasible, there exists a feasible uncrossed flow.
Proof.
We prove the result by induction on . If then the instance is single-source and the result follows, so suppose . Let be an arbitrary facial decomposition.
We first consider the case that at least two faces have that is non-empty. We obtain a feasible flow for that satisfies the nested supports property for by way of Lemma 17. For each face , let be defined as in the statement of Lemma 18. Each instance is feasible via the flow . Additionally, since there are at least two faces such that is non-empty, we have for every face . Hence by induction, there is a feasible uncrossed flow for each instance . Then by Lemma 18, the sum of these flows is a feasible uncrossed flow for .
Now, we consider the case where is empty for all faces except one, call it . That is, , and in particular every demand fits . If none of the demands cross within , then the layout is fully-planar and we are done. Otherwise, there exist that cross when drawn in the face . However, since is pairwise-planar, there exists another face such that at least one of these two demands, without loss of generality say , also fits . Now we define a facial decomposition as follows. We define , , and for all other faces . That is, we now view as being associated with rather than .
We obtain a feasible flow for the instance satisfying the nested supports property for this new facial decomposition by way of Lemma 17. We define capacities for each face as in the statement of Lemma 18 using the new decomposition . Each instance is feasible. Additionally, each satisfies that , and thus has a feasible uncrossed flow by induction. Then the sum of these flows is a feasible uncrossed flow for by Lemma 18.
With a little extra effort, we can modify Lemma 18 and Theorem 19 to show that pairwise-planar instances admit strongly uncrossed flows.
It is straightforward to convert this inductive argument into a polynomial time algorithm, provided we have a polynomial time algorithm to compute a feasible almost-uncrossed flow, as in Lemma 14. However, this is somewhat tricky. To prove Lemma 14, we re-route flow on twice-crossing paths to reduce the total amount of crossing, but the amount of progress depends on the flow values of the crossing paths and could be very small. We defer the details to the full version, but one can efficiently compute an almost-uncrossed flow that is approximately feasible - for any , in polynomial time we can find an almost-uncrossed flow that is feasible for . The details are similar to the uncrossing algorithm in [18]. Essentially, by judiciously rounding each path’s flow value, we ensure the values are common multiples of a small but sufficiently large fraction to ensure each uncrossing step makes significant progress. We summarize the final result below.
Theorem 20.
Let be pairwise-planar and let be a congestion instance. Let be any constant. If the instance is feasible, then there exists a strongly uncrossed flow that is feasible for . The flow can be computed in polynomial time.
Note that is feasible for , so this approximate guarantee is useful for maximization as well as congestion. Combining this theorem with our rounding results Theorem 2 and Theorem 3, we obtain Corollary 4.
3.2 Integral Flow-Multicut Gap
In this subsection we prove Corollary 5. Here we are concerned with maximization instances . A multicut is a set of supply edges such that does not contain an -path for any . The minimum capacity of a multicut is at least the maximum value of a (fractional) multiflow. The ratio of these quantities is the (fractional) flow-multicut gap121212This is different from the similarly named flow-cut gap (cf. [7]), which is defined for congestion instances and relates the minimum congestion value to sparsity of cuts (not necessarily multicuts).. The integral flow-multicut gap is the ratio of the minimum capacity of a multicut to the maximum value of an integral multiflow.
An immediate corollary of Theorems 19 and 2 is that for pairwise-planar , the integral flow-multicut gap is bounded by times the (fractional) flow-multicut gap. We combine this with the following result by Tardos and Vazirani [30] to conclude Corollary 5.
Theorem 21 (Tardos and Vazirani [30]).
For any maximization instance where is planar, the (fractional) flow-multicut gap is bounded by .
4 Maximization Setting: Rounding and Hardness
In this section, we prove Theorem 2 and Theorem 6, which cover our rounding and inapproximability results for maximum uncrossed multiflow.
4.1 Uncrossed String Graphs and Approximate Integer Decomposition
First we prove Theorem 2. Our approach is to establish a so-called approximate integer decomposition property [3, 5] for uncrossed multiflows. The outline of the strategy is as follows. Suppose we are given an uncrossed multiflow , which achieves a value of . Imagine scaling by a positive integer such that is integral. Of course, may not be feasible. However suppose we are able to show that can be decomposed as the sum of a small number of feasible integral flows. That is where each is integral and feasible. At least one of the flows achieves a fraction of the value of , and hence a fraction of the value of .
How can we achieve such a decomposition? Suppose (for simplicity) that sends 1 unit of flow along paths . Furthermore suppose that each edge of has unit capacity and hence each appears on at most paths. Our goal then is to partition the paths into classes such that every edge appears at most once in each class; the classes then define the flows . Equivalently, we seek to partition the paths so that paths in the same class do not share an edge. Phrased this way, we can recognize this as a graph colouring problem on the edge-intersection graph of .
The edge-intersection graph of has node set , and an edge between distinct if there exists . The load of is the number of paths in which occurs, and the load of is the maximum load of an edge . Graphs constructed in this way are a special type of the well-studied family of string graphs, which are the intersection graphs of curves in the plane.
Definition 22 (Uncrossed String Graph, Realization).
An uncrossed string graph is the edge-intersection graph of a family of uncrossed paths in a planar graph . We say is a realization of .
Uncrossed string graphs have been studied before for their own sake [11, 32]. Given that has a load realization, we want that its chromatic number is some small function of , ideally . This question is strongly related to the concept of a -bounded graph family. A family of graphs is -bounded if there exists a function such that for all , , where is the clique number of . It is worth noting that general string graphs are not -bounded, and it is not obvious that uncrossed string graphs should be. An bound was conjectured originally in [11], and proven by Fox and Pach [13].
Theorem 23 (Fox and Pach).
Let be an uncrossed string graph with realization such that each edge has load at most . Then .
The result of Fox and Pach has not been published, however the proof is elegant and short. It establishes via a probabilistic proof (similar to a standard proof giving a bound on the crossing number of a graph) that has at most edges. Hence a greedy colouring procedure that removes the minimum degree vertex (which has degree at most ) and colours the rest of the graph inductively obtains a colouring. We were not initially aware of Fox and Pach’s result and independently proved a weaker bound that . For the sake of completeness we present this proof in the full version.
We now use the colouring result to establish an approximate integer decomposition property and prove a generalization of Theorem 2 with weighted profits on .
Theorem 24.
There exists a universal constant such that the following holds. Let be a planar maximization instance where is integral, equipped with per-unit profits for . Let be a feasible uncrossed multiflow. There exists a feasible integral multiflow that is uncrossed and achieves value . This solution can be computed in polynomial time.
Proof.
We first present the case where the capacities are unit-valued . We show how to handle general capacities in the full version - while not hard, it requires some care to handle polynomial time aspects.
Let . Let be the family of support paths for . Since , we have that for each . Now, let be a positive integer such that is integral. Since is integral, for each we have that where is a positive integer. By treating each as distinct paths, we may assume that each path routes exactly units of flow. Then, since by feasibility, at most paths use each edge of .
Let be the edge-intersection graph of , which has load at most . By Theorem 23, is -colourable where . Now for each colour class , we let denote the flow obtained by sending one unit of flow on each path in that colour class, and zero flow on all other paths. Then is integral and satisfies that for each , and since each path’s flow was blown up by a factor of . Since the value of is , at least one of the flows has a value of . Since , then this flow has value times that of , as desired.
However, this proof is existential thus far, and does not immediately give a polynomial time algorithm because could be very large. To fix this, we first have a pre-processing step where we convert into a feasible flow that uses a subset of ’s support paths (so that it remains uncrossed) such that each value is a multiple of , and so that is a large fraction of . We then run the above procedure on instead of , giving a polynomial time algorithm. We prove the following.
Lemma 25.
Let be any constant. There exists a positive constant such that the following holds. Let be a unit-capacity planar maximization instance on nodes, equipped with per-unit profits for . Let be a feasible multiflow such that . There exists a multiflow satisfying:
-
1.
is feasible,
-
2.
the support paths of are a subset of the support paths of ,
-
3.
, and
-
4.
for every path , is a multiple of .
There is a polynomial time algorithm that computes such an .
We prove this in the full version using a randomized rounding and re-scaling argument (which can be de-randomized to give a deterministic algorithm). The two conditions that and are only minor technicalities, as we argue in that version.
It is straightforward to generalize this to the node-capacitated setting - the colouring and integer decomposition property proceed in exactly the same way.
4.2 Inapproximability of Maximum Uncrossed Fractional Multiflow
Next we prove Theorem 6 on the inapproximability of maximum uncrossed (fractional) multiflow. We make use of a strong inapproximability result given by Chuzhoy, Kim, and Nimavat for maximum edge-disjoint paths (MEDP) and maximum node-disjoint paths (MNDP) in planar graphs; i.e. maximum integer multiflow for unit capacities. One minor technicality is that in their formulation, a feasible solution is only allowed to route one unit of flow for each demand. We call these problems capped MEDP and capped MNDP respectively.
Theorem 26 (Theorems 1.1 and 1.2, [9]).
For every constant , there is no -approximation polynomial-time algorithm for capped MEDP or capped MNDP, assuming that . Moreover, there is no -approximation polynomial-time algorithm for capped MEDP or capped MNDP, assuming that for some constant , . These results hold even when the input graph is a maximum degree planar graph, or even if is a wall graph.
We now prove Theorem 6 which relies on this result. We focus on the edge-capacitated version (the node-capacitated version is similar).
Proof of Theorem 6.
We give a polytime reduction from capped MEDP in wall graphs to maximum uncrossed multiflow in wall graphs, that preserves the approximation ratio up to a constant factor. For an instance of the capped MEDP problem where is a wall graph (which is planar and has maximum degree 3), define the following quantities.
-
Let denote the maximum number of demands in which can be routed on edge-disjoint paths in (i.e. the optimal value for capped MEDP).
-
Let denote the maximum value of a (fractional) uncrossed multiflow for .
Observe that any capped MEDP solution for is a feasible (integral) uncrossed multiflow for . To see this, consider a collection of edge-disjoint paths that form a capped MEDP solution. Recall from Section 2.2 that two edge-disjoint paths cross only if they cross at a node (rather than a longer common subpath). Since has maximum degree 3, a node crossing is not possible. Thus we have .
Suppose we have a -approximation algorithm for maximum uncrossed (fractional) multiflow in wall graphs. We obtain an approximation algorithm for capped MEDP as follows. We run our -approximation algorithm for maximum uncrossed multiflow on to obtain flow whose value is at least . We apply the polytime algorithm from Theorem 24 to compute a feasible uncrossed integral multiflow whose value is that of . It may still not be a valid capped MEDP solution, since it may route more than one flow path for the same commodity. However, since has maximum degree 3, it routes on at most 3 paths for each commodity, so by selecting exactly one path for each commodity we obtain a capped MEDP solution whose value is at least that of . Thus this algorithm outputs a capped MEDP solution whose value is at least , and is thus a -approximation algorithm.
5 Congestion Setting: Rounding
In this section, we focus on planar congestion instances where the demands must be fully routed. We show Theorem 3, which states that we can convert (fractional) strongly uncrossed multiflows into integral flows that violate the capacities by a factor of at most 2, and if we accept an additional additive error of less than the flow can be made unsplittable. Section 5.1 presents the relevant properties of strongly uncrossed flows, and Section 5.2 gives the proof of Theorem 3.
5.1 Clockwise Orderings and Sectors
Let be a strongly uncrossed multiflow for planar congestion instance . Let be the set of support paths, and let be the support paths routing demand . Fix a strongly uncrossed parallelization . We parallelize the edges and perform disk-expansion at each node (see Section 2.2) so the paths become node-disjoint. Then, for each commodity , we add a node and edges into the disk corresponding to to join the endpoints of the paths for , and similarly for the disk of . This can be done in a planar fashion for all demands simultaneously since the flow is strongly uncrossed (see Section 2.4 and Figure 7). We denote the new graph . For , we let be its corresponding path in . For , and are internally node-disjoint paths that share their endpoints. For routing different demands, and are (completely) node-disjoint.
Consider a commodity . We use the notation to mean the subgraph of induced by the paths . In , the paths of have a clockwise cyclic ordering about , say . Informally, a sector is the region between consecutive paths in the clockwise ordering. We make this more precise as follows.
Consider two paths and in . Orient from to , and orient from to . The directed curve , obtained by concatenating these oriented curves, is a simple closed (Jordan) curve, and partitions the plane into two regions. We define to be the set of points in such that is “to the right” of ; that is, if we draw a directed curve from to (avoiding except at the extremity), it hits from the right. We let denote the closed region . We analogously define and by taking the opposite orientation. Any curve that does not cross and is internally disjoint from and either stays entirely within or stays entirely within .
Now, for our clockwise-ordered family of paths , we refer to for (addition modulo ) as the open sectors of , and define the closed sectors similarly using . The open sectors partition . One sector contains the infinite face of ; we call this the outer sector of , and the others the inner sectors of . The outer paths of are the two paths whose corresponding paths define the outer sector of .
Now consider an edge of the original graph that appears in . If lies in any outer path of , it is an outer edge of , otherwise it is an inner edge of . For our congestion result, we exploit the following key properties.
Lemma 27.
Let be a strongly uncrossed multiflow, with a fixed strongly uncrossed parallelization . For distinct , the sets of inner edges of and are disjoint.
Proof.
To prove the result, we show that if an edge is shared between the two single-commodity flows in , then it is an outer edge for one of the commodities.
Claim 28.
is entirely contained within a single sector of , and is entirely contained within a single sector of .
Proof.
By symmetry, it suffices to prove the first part. Recall that in , two paths for distinct commodities are completely disjoint, so each individual lies in at most one sector of . However, all paths of share common terminals in , so it must be the same sector for all of .
Claim 29.
Either is contained in the outer sector of , or is contained in the outer sector of .
Proof.
By the previous claim and by symmetry, it suffices to show that if is contained within an inner sector of , then is contained within the outer sector of . Suppose is in the inner sector of defined by paths and . Since is an inner sector, it is bounded, which means is contained in the interior of the curve rather than the exterior. This implies that and are contained within the infinite face of , and so therefore are in the outer sector of . Since the entirety of is within the same sector of , it is within the outer sector of .
Now, without loss of generality, suppose that is contained within the outer sector of . Then and both contain one of the copies of the shared edge . The copy belonging to is contained in the infinite face of , and (by how is constructed) so too is the copy belonging to . So then is an outer edge of , not an inner edge.
Now, associating the circular ordering to corresponding to the clockwise ordering of , we prove the second key property.
Lemma 30.
Suppose that in , share an edge . One of the following holds:
-
every path between and in the circular ordering also uses , or
-
every path between and in the circular ordering also uses .
Proof.
In , consider subdividing the copies of belonging to and by adding one node into each edge. Then add an edge between the two new nodes, adding such that it only crosses copies of . The new edge either separates or it separates , where by separates we mean that any path of that is within the sector must cross . The paths between and in the clockwise ordering all lie in , and the paths between and in the clockwise ordering all lie in . If a path crosses , then it means that it uses a copy of , and hence its corresponding path in also uses . The result follows.
5.2 Main Congestion Argument
We are now ready to prove Theorem 3.
Proof of Theorem 3.
First, we show how to prove Item 2 (unsplittable flow), since Item 1 ultimately follows from it. Let be a feasible strongly uncrossed flow with a fixed strongly uncrossed parallelization . Recall that we let and let be the single-commodity flow for .
Consider a commodity . Let be the paths of , ordered according to the cyclic clockwise ordering of their corresponding paths in . Re-index so that and are the outer paths. Let be the smallest index such that . We define , and call it the central path for .
Claim 31.
If and is an outer edge for (i.e. it lies in or ), then .
Proof.
Since is an outer edge, it is in either or , in addition to . From Lemma 30 we have that either for all or for all . In the former case, . For the latter case, , where the last inequality follows since by definition of .
To obtain an unsplittable flow , for each we route units of flow along the path . For the congestion bound, consider an arbitrary edge . We will bound the amount of flow through . Let , so . Define and also . These sets partition , so . We know that from Lemma 27. Additionally, by Claim 31, for each we have that . We now split into two cases.
Case 1: . Then,
Case 2: . Then , so the commodities of saturate in . It follows that . Hence,
This concludes the proof of Item 2. The above is easily turned into a polynomial time algorithm. We show how to prove Item 1 from Item 2 in the full version.
References
- [1] Cédric Bentz. Disjoint paths in sparse graphs. Discrete Applied Mathematics, 157(17):3558–3568, October 2009. doi:10.1016/j.dam.2009.03.009.
- [2] Amit Chakrabarti, Lisa Fleischer, and Christophe Weibel. When the cut condition is enough: A complete characterization for multiflow problems in series-parallel networks. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 19–26. ACM, 2012. doi:10.1145/2213977.2213980.
- [3] Chandra Chekuri, Marcelo Mydlarz, and F Bruce Shepherd. Multicommodity demand flow in a tree and packing integer programs. ACM Transactions on Algorithms (TALG), 3(3):27, 2007. doi:10.1145/1273340.1273343.
- [4] Chandra Chekuri, Guyslain Naves, and F Bruce Shepherd. Maximum edge-disjoint paths in k-sums of graphs. In International Colloquium on Automata, Languages, and Programming, pages 328–339. Springer, 2013. doi:10.1007/978-3-642-39206-1_28.
- [5] Chandra Chekuri and F Bruce Shepherd. Approximate integer decompositions for undirected network design problems. SIAM Journal on Discrete Mathematics, 23(1):163–177, 2009. doi:10.1137/040617339.
- [6] Chandra Chekuri, F Bruce Shepherd, and Christophe Weibel. Flow-cut gaps for integer and fractional multiflows. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1198–1208. Society for Industrial and Applied Mathematics, 2010. doi:10.1137/1.9781611973075.96.
- [7] Chandra Chekuri, F Bruce Shepherd, and Christophe Weibel. Flow-cut gaps for integer and fractional multiflows. Journal of Combinatorial Theory, Series B, 103(2):248–273, 2013. doi:10.1016/j.jctb.2012.11.002.
- [8] Julia Chuzhoy, David HK Kim, and Rachit Nimavat. Almost polynomial hardness of node-disjoint paths in grids. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1220–1233, 2018.
- [9] Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat. Almost polynomial hardness of node-disjoint paths in grids. Theory of Computing, 17(6):1–57, 2021. doi:10.4086/toc.2021.v017a006.
- [10] Denis Cornaz. Max-multiflow/min-multicut for G + H series-parallel. Discrete Mathematics, 311(17):1957–1967, September 2011. doi:10.1016/j.disc.2011.05.025.
- [11] Louis Esperet, Daniel Gonçalves, and Arnaud Labourel. Coloring a set of touching strings. Electronic Notes in Discrete Mathematics, 34:213–217, August 2009. doi:10.1016/j.endm.2009.07.035.
- [12] David Alemán Espinosa, Nikhil Kumar, Joseph Poremba, and Bruce Shepherd. Unsplittable flow cut gap in undirected graphs. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1570–1605. SIAM, 2026. doi:10.1137/1.9781611978971.57.
- [13] Jacob Fox and János Pach. Touching Strings. Unpublished manuscript, 2012.
- [14] N. Garg, V. V. Vazirani, and M. Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18(1):3–20, May 1997. doi:10.1007/BF02523685.
- [15] Naveen Garg, Nikhil Kumar, and András Sebő. Integer plane multiflow maximisation: one-quarter-approximation and gaps. Mathematical Programming, 195(1):403–419, 2022. doi:10.1007/S10107-021-01700-8.
- [16] Michel X Goemans and David P Williamson. Primal-dual approximation algorithms for feedback problems in planar graphs. Combinatorica, 1(18):37–59, 1998. doi:10.1007/PL00009810.
- [17] Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Kevin Schewior, and Jens Vygen. An approximation algorithm for fully planar edge-disjoint paths. SIAM Journal on Discrete Mathematics, 35(2):752–769, 2021. doi:10.1137/20M1319401.
- [18] Chien-Chung Huang, Mathieu Mari, Claire Mathieu, and Jens Vygen. Approximating maximum integral multiflows on bounded genus graphs. Discrete & Computational Geometry, 70(4):1266–1291, 2023. doi:10.1007/S00454-023-00552-7.
- [19] Philip Klein, Serge A. Plotkin, and Satish Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, STOC ’93, pages 682–690, New York, NY, USA, 1993. ACM. doi:10.1145/167088.167261.
- [20] Bernhard Korte, Làszlo Lovàsz, Hans Jürgen Prömel, and Alexander Schrijver. Paths, flows, and VLSI-layout. Springer-Verlag, 1990.
- [21] Kazuhiko Matsumoto, Takao Nishizeki, and Nobuji Saito. Planar multicommodity flows, maximum matchings and negative cycles. SIAM Journal on Computing, 15(2):495–510, 1986. doi:10.1137/0215034.
- [22] Guyslain Naves. The hardness of routing two pairs on one face. Mathematical Programming, 131(1-2):49–69, February 2012. doi:10.1007/s10107-010-0343-0.
- [23] Janos Pách. personal communication.
- [24] Niklas Schlomberg. An improved integrality gap for disjoint cycles in planar graphs. arXiv preprint, 2024. arXiv:2404.17813.
- [25] Niklas Schlomberg, Hanjo Thiele, and Jens Vygen. Packing cycles in planar and bounded-genus graphs. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2069–2086. SIAM, 2023. doi:10.1137/1.9781611977554.CH79.
- [26] Alexander Schrijver. Homotopic routing methods. Paths, Flows, and VLSI-layout, pages 329–371, 1990.
- [27] Alexander Schrijver. Disjoint homotopic paths and trees in a planar graph. Discrete & Computational Geometry, 6:527–574, 1991. doi:10.1007/BF02574704.
- [28] Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003.
- [29] Paul D Seymour. Matroids and multicommodity flows. European Journal of Combinatorics, 2(3):257–290, 1981. doi:10.1016/S0195-6698(81)80033-9.
- [30] Éva Tardos and Vijay V. Vazirani. Improved bounds for the max-flow min-multicut ratio for planar and K-free graphs. Information Processing Letters, 47(2):77–80, August 1993. doi:10.1016/0020-0190(93)90228-2.
- [31] Vera Traub, Laura Vargas Koch, and Rico Zenklusen. Single-source unsplittable flows in planar graphs. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 639–668. SIAM, 2024. doi:10.1137/1.9781611977912.24.
- [32] Wouter Cames Van Batenburg, Louis Esperet, and Tobias Müller. Coloring Jordan Regions and Curves. SIAM Journal on Discrete Mathematics, 31(3):1670–1684, January 2017. doi:10.1137/16M1092726.
- [33] Jens Vygen. Np-completeness of some edge-disjoint paths problems. Discrete Applied Mathematics, 61(1):83–90, 1995. doi:10.1016/0166-218X(93)E0177-Z.
