Sequentially Swapping Tokens Further on Graph Classes

2025-05-03 0 0 888.27KB 24 页 10玖币

侵权投诉

Sequentially Swapping Tokens: Further on Graph Classes?,??

Hironori Kiyaa, Yuto Okadab, Hirotaka Onob, Yota Otachib,∗

aKyushu University, Fukuoka, Japan

bNagoya University, Nagoya, Japan

Abstract

We study the following variant of the 15 puzzle. Given a graph and two token placements on the

vertices, we want to ﬁnd a walk of the minimum length (if any exists) such that the sequence of

token swappings along the walk obtains one of the given token placements from the other one.

This problem was introduced as Sequential Token Swapping by Yamanaka et al. [JGAA

2019], who showed that the problem is intractable in general but polynomial-time solvable for

trees, complete graphs, and cycles. In this paper, we present a polynomial-time algorithm for

block-cactus graphs, which include all previously known cases. We also present general tools

for showing the hardness of the problem on restricted graph classes such as chordal graphs and

chordal bipartite graphs. We also show that the problem is hard on grids and king’s graphs,

which are the graphs corresponding to the 15 puzzle and its variant with relaxed moves.

Keywords: Sequential token swapping, The (generalized) 15 puzzle, Block-cactus graph, Grid

graph, King’s graph

1. Introduction

Let G= (V, E) be an undirected graph and f, f0:V→ {1, . . . , c}be colorings of G.1We

call a sequence hf1, . . . , fpiof colorings of Gaswapping sequence of length p−1 from fto f0if

f1=f,fp=f0, and there is a walk hw1, w2, . . . , wpisuch that for 2 ≤i≤p,fiis obtained from

fi−1by swapping the colors of wi−1and wi; that is, fi(wi) = fi−1(wi−1), fi(wi−1) = fi−1(wi),

and fi(v) = fi−1(v) for v /∈ {wi−1, wi}. See Fig. 1. Now the problem can be formulated as

follows.

Problem: Sequential Token Swapping

Input: A graph G= (V, E), colorings f, f0of G, and an integer k.

Question: Is there a swapping sequence of length at most kfrom fto f0?

We assume that fand f0color the same number of vertices for each color since otherwise

it becomes a trivial no-instance. We also assume that the input graph Gis connected as a

swapping sequence aﬀects only one connected component.

?A preliminary version appeared in the proceedings of the 48th International Conference on Current Trends

in Theory and Practice of Computer Science (SOFSEM 2023), Lecture Notes in Computer Science 13878 (2023)

222–235.

??Partially supported by JSPS KAKENHI Grant Numbers JP17H01698, JP17K19960, JP18H04091,

JP20H05793, JP20H05967, JP21K11752, JP21K19765, JP21K21283, JP22H00513.

∗Corresponding author.

Email addresses: h-kiya@econ.kyushu-u.ac.jp (Hironori Kiya), okada.yuto.b3@s.mail.nagoya-u.ac.jp

(Yuto Okada), ono@nagoya-u.jp (Hirotaka Ono), otachi@nagoya-u.jp (Yota Otachi)

1By a coloring, we mean a mapping from the vertex set to a color set, which is not necessarily a proper

coloring.

Preprint submitted to Journal of Computer and System Sciences March 10, 2023

arXiv:2210.02835v3 [cs.DS] 9 Mar 2023

Figure 1: An example of a swapping sequence.

The intuition behind its name, Sequential Token Swapping, is as follows: we consider

a coloring as an assignment of colored tokens (or pebbles) to the vertices; we proceed along a

walk; and when we visit an edge in the walk, we swap the tokens on the endpoints. For the

ease of presentation, we often use the concept of tokens in this paper. For example, we call the

token on the ﬁrst vertex of the walk the moving token as it will always be the one exchanged

during the swapping sequence. In other words, fi(wi) = f1(w1) holds for all i.

Yamanaka et al. [1] introduced Sequential Token Swapping as a variant of the (general-

ized) 15 puzzle (Fig. 2), in which the ﬁrst and last vertices in a swapping sequence are given as

part of input. They showed that Sequential Token Swapping is polynomial-time solvable

in some restricted cases such as trees, complete graphs, and cycles. They also showed that

there is a constant ε > 0 such that the shortest length of a swapping sequence is NP-hard to

approximate within a factor 1 + ε.

Our results. We unify and extend the positive results in [1] by showing that Sequential

Token Swapping is polynomial-time solvable on block-cactus graphs, which include the classes

of trees, complete graphs, and cycles. To this end, we ﬁrst show that Sequential Token

Swapping on a graph is reducible to a generalized problem (called Sub-STS) on its biconnected

components, which may be of independent interest. We then show that the generalized problem

Sub-STS can be solved in polynomial time on complete graphs and cycles. As a byproduct, we

also show that the generalized 15 puzzle is polynomial-time solvable on the same graph class.

To complement the positive results, we show negative results on several classes of graphs. We

ﬁrst present two general tools for showing the NP-hardness of Sequential Token Swapping

on restricted graph classes. One is for the few-color case, where we use only a ﬁxed number

of colors, and the other is for the colorful case, where we use a unique color for each vertex.

The graph classes covered by the general tools include chordal graphs and chordal bipartite

graphs. We also show the hardness on grids and king’s graphs that play important roles in the

connection to puzzles [2] and video games [3]. For them, our general tools cannot be applied,

but similar ideas can be tailored. Also for split graphs, our general tools cannot be applied, but

the NP-completeness of the few-color case follows as a corollary to some discussions for grid-like

graphs. The complexity of the colorful case on split graphs remains unsettled.

Related results. Sequential Token Swapping can be seen as a variant of the famous 15

puzzle. The 15 puzzle is played on a 4 ×4 board with 16 cells. On the board, there are 15 pieces

numbered from 1 to 15 and one vacant cell. In each turn, we can slide an adjacent piece to the

vacant cell. The goal is to place the pieces at the right positions (see Fig. 2). By regarding

the vacant cell (instead of an adjacent piece) as the piece moving in each step, we can see the

sliding process in the 15 puzzle as a swapping sequence on the 4 ×4 grid that starts at the

vacant cell. If we deﬁne the generalized 15 puzzle as the same problem considered on general

graphs with arbitrary colorings, then it is almost the same as Sequential Token Swapping,

and the diﬀerence is whether the ﬁrst and last vertices in the walk corresponding to a swapping

sequence are speciﬁed in the input (for the generalized 15 puzzle) or not (for Sequential

Token Swapping).

...

Figure 2: The 15 puzzle. Each step can be seen as a move of the vacant cell.

The generalized 15 puzzle has been extensively studied with respect to the “reachability”,

i.e., under the setting where the question is the existence of a swapping sequence (not the

minimum length). It was shown by Johnson and Story [2] that the reachability in the original

15 puzzle can be decided from the parity of the total distance from the initial to ﬁnal token

placements. This was later generalized further and a characterization of the reachability was

given. For example, it is easy to see that the characterization given by Trakultraipruk [4] is

polynomial-time testable. On the other hand, the problem of ﬁnding a swapping sequence of

the minimum length has been studied only for a couple of cases. It was shown by Ratner and

Warmuth [5] that the generalized 15 puzzle is NP-complete on n×ngrids, in which case the

problem is called the (n2−1) puzzle. A short proof for the same result was presented later by

Demaine and Rudoy [6].

Although Sequential Token Swapping is quite close to the generalized 15 puzzle, its

concept comes also from its non-sequential variant Token Swapping, which does not ask for

the existence of a walk consistent with a swapping sequence but allows to swap the tokens on

the endpoints of any edge in each step. The complexity of Token Swapping has shown to

be quite diﬀerent from its sequential variant. For example, it is recently shown that Token

Swapping is NP-complete even on trees [7].

The generalized 15 puzzle and (Sequential) Token Swapping are sometimes considered

in combinatorial reconﬁguration as well. See the surveys [8, 9] for the background and related

results in this context.

2. Preliminaries

We use standard terminologies for graphs (see e.g., [10] for the terms not deﬁned here).

Let G= (V, E) be an undirected graph. For S⊆V, the subgraph of Ginduced by Sis

denoted by G[S]. A sequence W=hw1, . . . , w|W|iof vertices is a walk of length |W|−1 in Gif

{wi, wi+1} ∈ Efor 1 ≤i < |W|. A vertex of a connected graph is a cut vertex if the removal of

the vertex makes the graph disconnected. A connected graph is biconnected if it contains no cut

vertex. A maximal induced biconnected subgraph of a graph is called a biconnected component

of the graph. Let BGdenote the set of biconnected components of G. It is known that BGcan

be computed in linear time [11].

A graph is a cactus if each biconnected component is a cycle or a 2-vertex complete graph.

A graph is a block graph if each biconnected component is a complete graph. A graph is a

block-cactus graph if each biconnected component is a cycle or a complete graph. A chordal

graph is a graph with no induced cycle of length 4 or more. A chordal bipartite graph is a

bipartite graph with no induced cycle of length 6 or more. A graph is a split graph if its vertex

set can be partitioned into a clique and an independent set.

The h×wgrid has the vertex set V={1, . . . , h}×{1, . . . , w}and the edge set {{(x, y),(x0, y0)} |

(x, y),(x0, y0)∈V, |x−x0|+|y−y0|= 1}. A graph is a grid if it is the h×wgrid

for some integers hand w. A graph is a grid graph if it is an induced subgraph of some

grid. We say that a grid graph G= (V, E) is given with a grid representation if V⊆Z2

and E={{(x, y),(x0, y0)} | (x, y),(x0, y0)∈V, |x−x0|+|y−y0|= 1}. The h×wking’s

graph is obtained from the h×wgrid by adding all diagonal edges of the unit squares (4-

cycles) in the grid; that is, the vertex set is V={1, . . . , h}×{1, . . . , h}and the edges set is

{{(x, y),(x0, y0)} | (x, y),(x0, y0)∈V, max{|x−x0|,|y−y0|} = 1}. A graph is a king’s graph if

it is the h×wking’s graph for some integers hand w. We call a vertex (x, y) of a king’s graph

even if x+yis even and odd if x+yis odd. In passing, the name of a king’s graph comes from

the legal moves of the king chess piece on a chessboard.

As mentioned in Section 1, the generalized 15 puzzle can be seen as a variant of Sequential

Token Swapping with the ﬁrst and last vertices speciﬁed. In the following, we call it (s,t)-

STS.

Problem: (s,t)-STS

Input: A graph G= (V, E), colorings f, f0of G,s, t ∈V, and an integer k.

Question: Is there a swapping sequence of length at most kfrom fto f0such that the corre-

sponding walk starts at sand ends at t?

Note that sand tin an instance of (s,t)-STS are not necessarily distinct.

3. Polynomial-time algorithm for block-cactus graphs

In this section, we present a polynomial-time algorithm for Sequential Token Swapping

on block-cactus graphs. We prove the following theorem.

Theorem 3.1 Sequential Token Swapping on block-cactus graphs can be solved in O(n3)

time, where nis the number of vertices.

Note that although Theorem 3.1 is stated for Sequential Token Swapping, which is a

decision problem, the algorithm presented below actually solves the optimization version of the

problem in the same running time. That is, it computes the minimum length of a swapping

sequence from fto f0in O(n3) time.

The main part of the algorithm is the subroutine for solving (s,t)-STS. Given that subrou-

tine, the algorithm just tries all pairs of vertices as the ﬁrst and last vertices. In the following,

we focus on this subroutine.

We show that the problem on a graph can be reduced to a generalized problem on its

biconnected components. Then it suﬃces to show that the generalized problem can be solved

in polynomial time on complete graphs and cycles. We prove this in a way similar to Yamanaka

et al. [1] but the proofs here are much more involved because of the generality of the problem.

3.1. Reduction to a generalized problem on biconnected components

We generalize (s,t)-STS by adding a subset Pof vertices to be visited as follows.

Problem: Sub-STS

Input: A graph G= (V, E), colorings f, f0of G,s, t ∈V, and P⊆V.

Task: Find the minimum length of a swapping sequence from fto f0(if any exists) such that

the corresponding walk W=hw1, w2, . . . , w|W|isatisﬁes that w1=s,w|W|=t, and

P⊆ {w1, w2, . . . , w|W|}.

Figure 3: Cut vertices c1, c2and the corresponding subgraphs G1, G2.

Let λ(G, f, f0, s, t, P ) denote the answer for the instance hG, f, f0, s, t, P iof Sub-STS. We

set it to ∞if no swapping sequence from fto f0exists. Note that λ(G, f, f0, s, t, ∅) is the

minimum ksuch that hG, f, f0, s, t, kiis a yes-instance of (s,t)-STS.

Let hG, f, f0, s, t, kibe an instance of (s,t)-STS and let Hbe a biconnected component

of G. Let us see how a solution to this instance passes through H. If s /∈V(H), then the

ﬁrst vertex visited in His the cut vertex closest to s. Similarly, if t /∈V(H), then the last

vertex visited in His the cut vertex closest to t. Also, a cut vertex uof Gbelonging to Hhas

to be visited if at least one vertex in His visited and there is a vertex v /∈V(H) such that

f(v)6=f0(v) and uis the closest vertex in Hto v. With these observations, we construct an

instance hH, fH, f0

H, sH, tH, PHiof Sub-STS as follows, where cvis the cut vertex in Hthat

separates vand V(H).

•Set fH=f|V(H). If s /∈V(H), then update fHas fH(cs):=f(s).

•Set f0

H=f0|V(H). If t /∈V(H), then update f0

Has f0

H(ct):=f(s).

•Set sH=sif s∈V(H). Otherwise, set sH=cs.

•Set tH=tif t∈V(H). Otherwise, set tH=ct.

•Set PHto the set of cut vertices cvof Gbelonging to V(H) such that cvseparates vand

Hfor some v /∈V(H) with f(v)6=f0(v).

The following lemma says that this instance correctly captures how a solution to (s,t)-STS on

Gaﬀects H.

Lemma 3.2 For a graph G, colorings f, f0of G, and s, t ∈V,

λ(G, f, f0, s, t, ∅) = X

H∈BG

λ(H, fH, f0

H, sH, tH, PH).

Proof. We use induction on |BG|, the number of biconnected components of G. If |BG|=

1, then the unique biconnected component is Gitself and thus the statement holds. In the

following, we assume that |BG|=b+ 1 for some b≥1 and that the statement holds for all

graphs with at most bbiconnected components.

Let S∈ BGbe an arbitrary biconnected component that contains s. Since |BG|=b+ 1 ≥2,

the biconnected component Shas at least one cut vertex. Let c1, . . . , cabe the cut vertices of G

in H. Let G1, . . . , Gabe the nontrivial connected components of G−E(S) such that ci∈V(Gi)

for each i(see Fig. 3).

For each Gi, we set f(i),f0(i),s(i), and t(i)as follows.

•Set f(i)=f|V(Gi), and then update it as f(i)(ci):=f(s).

•Set f0(i)=f0|V(Gi). If t /∈V(Gi), then update it as f0(i)(ci):=f(s).

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

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

10 玖币 0人已下载

立即下载

摘要：

SequentiallySwappingTokens:FurtheronGraphClasses?;??HironoriKiyaa,YutoOkadab,HirotakaOnob,YotaOtachib,aKyushuUniversity,Fukuoka,JapanbNagoyaUniversity,Nagoya,JapanAbstractWestudythefollowingvariantofthe15puzzle.Givenagraphandtwotokenplacementsonthevertices,wewanttondawalkoftheminimumlength(ifanyex...

展开>> 收起<<

Sequentially Swapping Tokens Further on Graph Classes.pdf

共24页,预览5页

还剩页未读，继续阅读

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

Sequentially Swapping Tokens Further on Graph Classes

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: