Rerouting Planar Curves and Disjoint Paths Takehiro ItoYuni IwamasaNaonori KakimuraYusuke Kobayashi Shun-ichi Maezawauni2016Yuta NozakiYoshio OkamotoKenta Ozeki

2025-04-29 0 0 1.54MB 38 页 10玖币

侵权投诉

Rerouting Planar Curves and Disjoint Paths∗

Takehiro Ito†Yuni Iwamasa‡Naonori Kakimura§Yusuke Kobayashi¶

Shun-ichi Maezawa‖Yuta Nozaki∗∗ Yoshio Okamoto†† Kenta Ozeki‡‡

Abstract

In this paper, we consider a transformation of kdisjoint paths in a graph. For a graph

and a pair of kdisjoint paths Pand Qconnecting the same set of terminal pairs, we aim to

determine whether Pcan be transformed to Qby repeatedly replacing one path with another

path so that the intermediates are also kdisjoint paths. The problem is called Disjoint

Paths Reconfiguration. We ﬁrst show that Disjoint Paths Reconfiguration is

PSPACE-complete even when k= 2. On the other hand, we prove that, when the graph

is embedded on a plane and all paths in Pand Qconnect the boundaries of two faces,

Disjoint Paths Reconfiguration can be solved in polynomial time. The algorithm is

based on a topological characterization for rerouting curves on a plane using the algebraic

intersection number. We also consider a transformation of disjoint s-tpaths as a variant. We

show that the disjoint s-tpaths reconﬁguration problem in planar graphs can be determined

in polynomial time, while the problem is PSPACE-complete in general.

1 Introduction

1.1 Disjoint Paths and Reconﬁguration

The disjoint paths problem is a classical and important problem in algorithmic graph theory and

combinatorial optimization. In the problem, the input consists of a graph G= (V, E) and 2k

distinct vertices s1, . . . , sk, t1, . . . , tk, called terminals, and the task is to ﬁnd kvertex-disjoint

paths P1, . . . , Pksuch that Piconnects siand tifor i= 1, . . . , k if they exist. A tuple P=

(P1, . . . , Pk) of paths satisfying this condition is called a linkage. The disjoint paths problem has

attracted attention since 1980s because of its practical applications to transportation networks,

network routing [52], and VLSI-layout [21, 33]. When the number kof terminal pairs is part of

the input, the disjoint paths problem was shown to be NP-hard by Karp [28], and it remains

NP-hard even for planar graphs [34]. For the case of k= 2, polynomial-time algorithms were

presented in [50, 51, 56], while the directed variant was shown to be NP-hard [20]. Later, for

∗This work was supported by JSPS KAKENHI Grant Numbers JP18H05291, JP20K11692, JP20K14317,

JP20H05793, JP20H05795, JP20K23323, JP21H03397, JP22K17854.

†Graduate School of Information Sciences, Tohoku University, Japan, takehiro@tohoku.ac.jp

‡Graduate School of Informatics, Kyoto University, Japan, iwamasa@i.kyoto-u.ac.jp

§Faculty of Science and Technology, Keio University, Japan, kakimura@math.keio.ac.jp

¶Research Institute for Mathematical Sciences, Kyoto University, Japan, yusuke@kurims.kyoto-u.ac.jp

‖Department of Mathematics, Tokyo University of Science, Japan, maezawa.mw@gmail.com

∗∗Graduate School of Advanced Science and Engineering, Hiroshima University, Japan,

nozakiy@hiroshima-u.ac.jp

††Graduate School of Informatics and Engineering, The University of Electro-Communications, Japan,

okamotoy@uec.ac.jp

‡‡Faculty of Environment and Information Sciences, Yokohama National University, Japan,

ozeki-kenta-xr@ynu.ac.jp

arXiv:2210.11778v1 [cs.DS] 21 Oct 2022

the case when the graph is undirected and kis a ﬁxed constant, Robertson and Seymour [47]

gave a polynomial-time algorithm based on the graph minor theory, which is one of the biggest

achievements in this area. Although the setting of the disjoint paths problem is quite simple

and easy to understand, a deep theory in discrete mathematics is required to solve the problem,

which is a reason why this problem has attracted attention in the theoretical study of algorithms.

An interesting special case is the problem in planar graphs. In the early stages of the study

of the disjoint paths problem, for the case when Gis embedded on a plane and all the terminals

are on one face or two faces, polynomial-time algorithms were given in [45, 53, 54]. In the series

of graph minor papers, the disjoint paths problem on a plane or on a ﬁxed surface was solved for

ﬁxed k[46]. For the planar case, faster algorithms were presented in [1, 43, 44]. The directed

variant of the problem can be solved in polynomial time if the input digraph is planar and kis

a ﬁxed constant [14, 49].

In this paper, we consider a transformation of linkages in a graph. Roughly, in a transforma-

tion, we pick up one path among the kpaths in a linkage, and replace it with another path to ob-

tain a new linkage. To give a formal deﬁnition, suppose that Gis a graph and s1, . . . , sk, t1, . . . , tk

are distinct terminals. For two linkages P= (P1, . . . , Pk) and Q= (Q1, . . . , Qk), we say that

Pis adjacent to Qif there exists i∈ {1, . . . , k}such that Pj=Qjfor j∈ {1, . . . , k} \ {i}and

Pi6=Qi. We say that a sequence hP1,P2,...,P`iof linkages is a reconﬁguration sequence from

P1to P`if Piand Pi+1 are adjacent for i= 1, . . . , ` −1. If such a sequence exists, we say that

P1is reconﬁgurable to P`. In this paper, we focus on the following reconﬁguration problem,

which we call Disjoint Paths Reconfiguration.

Disjoint Paths Reconfiguration

Input. A graph G= (V, E), distinct terminals s1, . . . , sk, t1, . . . , tk, and two linkages Pand

Question. Is Preconﬁgurable to Q?

The problem can be regarded as the problem of deciding the reachability between linkages

via rerouting paths. Such a problem falls in the area of combinatorial reconﬁguration; see

Section 1.3 for prior work on combinatorial reconﬁguration. Note that Disjoint Paths Re-

configuration is a decision problem that just returns “YES” or “NO” and does not necessarily

ﬁnd a reconﬁguration sequence when the answer is YES.

Although our study is motivated by theoretical interest in the literature of combinatorial

reconﬁguration, the problem can model rerouting problem in a telecommunication network as

follows. Suppose that a linkage represents routing in a telecommunication network, and we

want to modify linkage Pto another linkage Qwhich is better than Pin some sense. If we

can change only one path in a step in the network for some technical reasons, and we have to

keep a linkage in the modiﬁcation process, then this situation is modeled as Disjoint Paths

Reconfiguration.

We also study a special case of the disjoint paths problem when s1=··· =skand t1=

··· =tk, which we call the disjoint s-tpaths problem. In the problem, for a graph and two

terminals sand t, we seek for kinternally vertex-disjoint (or edge-disjoint) paths connecting s

and t. It is well-known that the disjoint s-tpaths problem can be solved in polynomial time.

The study of disjoint s-tpaths was originated from Menger’s min-max theorem [37] and the

max-ﬂow algorithm by Ford and Fulkerson [19]. Faster algorithms for ﬁnding maximum disjoint

s-tpaths or a maximum s-tﬂow have been actively studied in particular for planar graphs; see

e.g. [16, 27, 29, 59].

In the same way as Disjoint Paths Reconfiguration, we consider a reconﬁguration of

internally vertex-disjoint s-tpaths. Let G= (V, E) be a graph with two distinct terminals s

and t. We say that a set P={P1, . . . , Pk}of kpaths in Gis an s-tlinkage if P1, . . . , Pkare

internally vertex-disjoint s-tpaths. Note that Pis not a tuple but a set, that is, we ignore the

ordering of the paths in P. We say that s-tlinkages Pand Qare adjacent if Q= (P \P)∪{Q}

for some s-tpaths Pand Qwith P6=Q. We deﬁne the reconﬁgurability of s-tlinkages in the

same way as linkages. We consider the following problem.

Disjoint s-tPaths Reconfiguration

Input. A graph G= (V, E), distinct terminals sand t, and two s-tlinkages Pand Q.

Question. Is Preconﬁgurable to Q?

1.2 Our Contributions

Since ﬁnding disjoint s-tpaths is an easy combinatorial optimization problem, one may expect

that Disjoint s-tPaths Reconfiguration is also tractable. However, this is not indeed the

case. We show that Disjoint s-tPaths Reconfiguration is PSPACE-hard even when k= 2.

Theorem 1.1. The Disjoint s-tPaths Reconfiguration is PSPACE-complete even when

k= 2 and the maximum degree of Gis four.

Note that Disjoint s-tPaths Reconfiguration can be easily reduced to Disjoint Paths

Reconfiguration by splitting each of sand tinto kterminals. Thus, this theorem implies

the PSPACE-hardness of Disjoint Paths Reconfiguration with k= 2.

In this paper, we mainly focus on the problems in planar graphs. To better understand Dis-

joint Paths Reconfiguration in planar graphs, we show a topological necessary condition.

Topological conditions play important roles in the disjoint paths problem. If there exist

disjoint paths connecting terminal pairs in a graph embedded on a surface Σ, then obviously

there must exist disjoint curves on Σ connecting them. For example, when terminals s1, s2, t1

and t2lie on the outer face Fin a plane graph Gin this order, there exist no disjoint curves

connecting the terminal pairs in the disk Σ = R2\F, and hence we can conclude that Gcontains

no disjoint paths. Such a topological condition is used to design polynomial-time algorithms for

the disjoint paths problem with k= 2 [50, 51, 56], and to deal with the problem on a disk or a

cylinder [45]. When Σ is a plane (or a sphere), we can always connect terminal pairs by disjoint

curves on Σ, and hence nothing is derived from the above argument. Indeed, Robertson and

Seymour [46] showed that if the input graph is embedded on a surface and the terminals are

mutually “far apart,” then desired disjoint paths always exist.

In contrast, as we will show below in Theorem 1.2, there exists a topological necessary

condition for the reconﬁgurability of disjoint paths. Thus, even when the terminals are mutually

far apart, the reconﬁguration of disjoint paths is not always possible. This shows a diﬀerence

between the disjoint paths problem and Disjoint Paths Reconfiguration.

In order to formally discuss the topological necessary condition, we consider the reconﬁgu-

ration of curves on a surface. Suppose that Σ is a surface and let s1, . . . , sk, t1, . . . , tkbe distinct

points on Σ. By abuse of notation, we say that P= (P1, . . . , Pk) is a linkage if it is a collection

of disjoint simple curves on Σ such that Piconnects siand ti. We also deﬁne the adjacency

and reconﬁguration sequences for linkages on Σ in the same way as linkages in a graph. Then,

the reconﬁgurability between two linkages on a plane can be characterized with a word wjas-

sociated to Qjwhich is an element of the free group Fkgenerated by x1, . . . , xkas follows; see

Section 3 for the deﬁnition of wj.

Theorem 1.2. Let P= (P1, . . . , Pk)and Q= (Q1, . . . , Qk)be linkages on a plane (or a

sphere). Then, Pis reconﬁgurable to Qif and only if wj∈ hxjifor any j∈ {1, . . . , k}, where

hxjidenotes the subgroup generated by xj.

Figure 1: (Left) An example on the plane where (P1, P2) is not reconﬁgurable to (Q1, Q2). (Right) An example

in a graph where the condition in Theorem 1.2 holds but (P1, P2) is not reconﬁgurable to (Q1, Q2).

See Figure 1 (left) for an example. It is worth noting that, if k= 2 and Σ is a connected

orientable closed surface of genus g≥1, then such a topological necessary condition does not

exist, i.e., the reconﬁguration is always possible; see Appendix A.

For a graph embedded on a plane, we can identify paths and curves. Then, Theorem 1.2 gives

a topological necessary condition for Disjoint Paths Reconfiguration in planar graphs.

However, the converse does not necessarily hold: even when the condition in Theorem 1.2 holds,

an instance of Disjoint Paths Reconfiguration may have no reconﬁguration sequence.

See Figure 1 (right) for a simple example. The polynomial solvability of Disjoint Paths

Reconfiguration in planar graphs is open even for the case of k= 2.

With the aid of the topological necessary condition, we design polynomial-time algorithms

for special cases, in which all the terminals are on a single face (called one-face instances), or

s1, . . . , skare on some face and t1, . . . , tkare on another face (called two-face instances). Note

that one/two-face instances have attracted attention in the disjoint paths problem [45, 53, 54],

in the multicommodity ﬂow problem [39, 40], and in the shortest disjoint paths problem [8,

13, 15, 31]. We show that any one-face instance of Disjoint Paths Reconfiguration has a

reconﬁguration sequence (Proposition 4.1). Moreover, we prove a topological characterization

for two-face instances of Disjoint Paths Reconfiguration (Theorem 4.2), which leads to a

polynomial-time algorithm in this case.

Theorem 1.3. When the instances are restricted to two-face instances, Disjoint Paths Re-

configuration can be solved in polynomial time.

Based on this theorem, we give a polynomial-time algorithm for Disjoint s-tPaths Re-

configuration in planar graphs.

Theorem 1.4. There is a polynomial-time algorithm for Disjoint s-tPaths Reconfigura-

tion in planar graphs.

Note that the number kof paths in Theorems 1.3 and 1.4 can be part of the input.

It is well known that Ghas an s-tlinkage of size kif and only if Ghas no s-tseparator

of size k−1 (Menger’s theorem). The characterization for two-face instances (Theorem 4.2)

implies the following theorem, which is interesting in the sense that one extra s-tconnectivity

is suﬃcient to guarantee the existence of a reconﬁguration sequence.

Theorem 1.5. Let G= (V, E)be a planar graph with distinct vertices sand t, and let Pand

Qbe s-tlinkages. If there is no s-tseparator of size k, then Pis reconﬁgurable to Q.

As mentioned above, the polynomial solvability of Disjoint Paths Reconfiguration in

planar graphs is open even for the case of k= 2. On the other hand, when kis not bounded,

Disjoint Paths Reconfiguration is PSPACE-complete as the next theorem shows.

Theorem 1.6. The Disjoint Paths Reconfiguration is PSPACE-complete when the graph

Gis planar and of bounded bandwidth.

Here, we recall the deﬁnition of the bandwidth of a graph. Let G= (V, E) be an undirected

graph. Consider an injective map π:V→Z. Then, the bandwidth of πis deﬁned as max{|π(u)−

π(v)| | {u, v} ∈ E}. The bandwidth of Gis deﬁned as the minimum bandwidth of all injective

maps π:V→Z.

1.3 Related Work

Combinatorial reconﬁguration is an emerging ﬁeld in discrete mathematics and theoretical com-

puter science. In typical problems of combinatorial reconﬁguration, we consider two discrete

structures, and ask whether one can be transformed to the other by a sequence of local changes.

See surveys of Nishimura [38] and van den Heuvel [57].

Path reconﬁguration problems have been studied in this framework. The apparently ﬁrst

problem is the shortest path reconﬁguration, introduced by Kaminski et al. [26]. In this prob-

lem, we are given an undirected graph with two designated vertices s,tand two s-tshortest

paths Pand Q. Then, we want to decide whether Pcan be transformed to Qby a sequence

of one-vertex changes in such a way that all the intermediate s-tpaths remain the shortest.

Bonsma [6] proved that the shortest path reconﬁguration is PSPACE-complete, but polynomial-

time solvable when the input graph is chordal or claw-free. Bonsma [7] further proved that the

problem is polynomial-time solvable for planar graphs. Wrochna [60] proved that the problem

is PSPACE-complete even for graphs of bounded bandwidth. Gajjar et al. [22] proved that the

problem is polynomial-time solvable for circle graphs, circular-arc graphs, permutation graphs

and hypercubes. They also considered a variant where a change can involve ksuccessive ver-

tices; in this variant they proved that the problem is PSPACE-complete even for line graphs.

Properties of the adjacency relation in the shortest path reconﬁguration have also been stud-

ied [4, 5].

Another path reconﬁguration problem has been introduced by Amiri et al. [3] who were

motivated by a problem in software deﬁned networks. In their setup, we are given a directed

graph with edge capacity and two designated vertices s, t. We are also given kpairs of s-

tpaths (Pi, Qi), i= 1,2, . . . , k, where the number of paths among P1, P2, . . . , Pk(and among

Q1, Q2, . . . , Qkrespectively) traversing an edge is at most the capacity of the edge. The problem

is to determine whether one set of paths can be transformed to the other set of paths by a

sequence of the following type of changes: specify one vertex vand then switch the usable

outgoing edges at vfrom those in the Pito those in the Qi. In each of the intermediate

situations, there must be a unique path through usable edges in Pi∪Qifor each i. See [3]

for the precise problem speciﬁcation. Amiri et al. [3] proved that the problem is NP-hard even

when k= 2. For directed acyclic graphs, they also proved that the problem is NP-hard (for

unbounded k) but ﬁxed-parameter tractable with respect to k. A subsequent work [2] studied

an optimization variant in which the number of steps is to be minimized when a set of “disjoint”

changes can be performed simultaneously.

Matching reconﬁguration in bipartite graphs can be seen as a certain type of disjoint paths

reconﬁguration problems. In matching reconﬁguration, we are given two matchings (with extra

properties) and want to determine whether one matching can be transformed to the other

matching by a sequence of local changes. There are several choices for local changes. One of

the most studied local change rules is the token jumping rule, where we remove one edge and

add one edge at the same time. Ito et al. [24] proved that the matching reconﬁguration (under

the token jumping rule) can be solved in polynomial time.1

1The theorem by Ito et al. [24] only gave a polynomial-time algorithm for a diﬀerent local change, the so-called

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ReroutingPlanarCurvesandDisjointPaths*TakehiroItoYuniIwamasaNaonoriKakimura§YusukeKobayashi¶Shun-ichiMaezawaYutaNozaki**YoshioOkamotoKentaOzekiAbstractInthispaper,weconsideratransformationofkdisjointpathsinagraph.ForagraphandapairofkdisjointpathsPandQconnectingthesamesetofterminalpairs,weaimt...

展开>> 收起<<

Rerouting Planar Curves and Disjoint Paths Takehiro ItoYuni IwamasaNaonori KakimuraYusuke Kobayashi Shun-ichi Maezawauni2016Yuta NozakiYoshio OkamotoKenta Ozeki.pdf

共38页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Rerouting Planar Curves and Disjoint Paths Takehiro ItoYuni IwamasaNaonori KakimuraYusuke Kobayashi Shun-ichi Maezawauni2016Yuta NozakiYoshio OkamotoKenta Ozeki

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: