Romeo and Juliet Meeting in Forest Like Regions

2025-05-03 0 0 2.2MB 29 页 10玖币

侵权投诉

Neeldhara Misra !Ï

Indian Institute of Technology, Gandhinagar, India

Manas Mulpuri !

Indian Institute of Technology, Gandhinagar, India

Prafullkumar Tale !Ï

Indian Institute of Science Education and Research, Pune, India

Gaurav Viramgami !

Indian Institute of Technology, Gandhinagar, India

Abstract

The game of rendezvous with adversaries is a game on a graph played by two players: Facilitator

and Divider. Facilitator has two agents and Divider has a team of

k≥

1agents. While the initial

positions of Facilitator’s agents are ﬁxed, Divider gets to select the initial positions of his agents.

Then, they take turns to move their agents to adjacent vertices (or stay put) with Facilitator’s goal

to bring both her agents at same vertex and Divider’s goal to prevent it. The computational question

of interest is to determine if Facilitator has a winning strategy against Divider with

agents. Fomin,

Golovach, and Thilikos [WG, 2021] introduced this game and proved that it is

PSPACE

-hard and

co-W[2]-hard parameterized by the number of agents.

This hardness naturally motivates the structural parameterization of the problem. The authors

proved that it admits an

FPT

algorithm when parameterized by the modular width and the number

of allowed rounds. However, they left open the complexity of the problem from the perspective of

other structural parameters. In particular, they explicitly asked whether the problem admits an

FPT

-algorithm with respect to the treewidth of the input graph. We answer this question

in the negative and show that Rendezvous is

-hard even for graphs of constant treewidth.

Further, we show that the problem is

-W[1]-hard when parameterized by the feedback vertex set

number and the number of agents, and is unlikely to admit a polynomial kernel when parameterized

by the vertex cover number and the number of agents. Complementing these hardness results, we

show that the Rendezvous is

FPT

when parameterized by both the vertex cover number and the

solution size. Finally, for graphs of treewidth at most two and girds, we show that the problem can

be solved in polynomial time.

2012 ACM Subject Classiﬁcation

Mathematics of computing

→

Discrete mathematics; Theory of

computation →Design and analysis of algorithms

Keywords and phrases

Games on Graphs, Dynamic Separators, W[1]-hardness, Structural Paramet-

ersization, Treewidth

Related Version

A shorter version of this work has been accepted for presentation at the 42nd

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer

Science (FSTTCS), 2022.

Funding

Neeldhara Misra: The author is grateful for support from DST-SERB and IIT Gandhinagar.

This work was partially supported by the ECR grant ECR/2018/002967.

Prafullkumar Tale: Part of the work was carried out when the author was a Post-Doctoral Researcher

at CISPA Helmholtz Center for Information Security, Germany, supported by the European Research

Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.

Acknowledgements We are grateful for feedback from anonymous reviewers.

arXiv:2210.02582v1 [cs.DS] 5 Oct 2022

2 Romeo and Juliet Meeting in Forest Like Regions

1 Introduction

The game of rendezvous with adversaries on a graph — Rendezvous — is a natural dynamic

version of the problem of ﬁnding a vertex cut between two vertices

and

introduced by

Fomin, Golovach, and Thilikos [

]. The game is played on a ﬁnite undirected connected

graph

by two players: Facilitator and Divider. Facilitator has two agents Romeo and

Juliet that are initially placed in designated vertices

and

. Divider, on the other

hand, has a team of

k≥

1agents

D1, . . . , Dk

that are initially placed in some vertices of

(

)

\{s, t}

chosen by him. We note that a single vertex can accommodate multiple agents

of Divider.

Then the players make their moves by turn, starting with Facilitator. At every move, each

player moves some of his/her agents to adjacent vertices or keeps them in their old positions.

No agent can be moved to a vertex that is currently occupied by adversary’s agents. Both

players have complete information about

and the positions of all the agents. Facilitator

aims to ensure that Romeo and Juliet meet; that is, they are in the same vertex. The task

of Divider is to prevent the rendezvous of Romeo and Juliet by maintaining

D1, . . . , Dk

positions that block the possibility to meet. Facilitator wins if Romeo and Juliet meet, and

Divider wins if they succeed in preventing the meeting of Romeo and Juliet forever. This

setup naturally leads to the following computational question.

Rendezvous

Input: A graph Gwith two given vertices sand t, and a positive integer k.

Question:

Can Facilitator win on

starting from

and

against Divider with

agents?

We will often refer to

, the number of agents employed by Divider to keep Romeo and

Juliet separated, as the “solution size” for this problem.

Known Results

Fomin, Golovach, and Thilikos [

] initiated an extensive study of the computational complexity

of Rendezvous. They concluded that the problem is

PSPACE

-hard and

-W[2]-hard

when

parameterized by the number of Divider’s agents, while also demonstrating an

(

)

|O(k)

algorithm based on backtracking stages over the game arena. They also show that the

problem admits polynomial time algorithms on chordal graphs and

-free graphs. A related

problem considered is Rendezvous in Time, which asks if Facilitator can force a win in at

most

steps. It turns out that Rendezvous in Time is co-NP-complete even for

= 2

and is

FPT

when parameterized by

and the neighborhood diversity of the graph. The

latter is an ILP-based approach and uses the fact that Integer Linear Programming

Feasibility is

FPT

in the number of variables. We refer readers to [

], and references within,

for more related problems.

The smallest number of agents that Divider needs to use to win on a graph

is called

the “dynamic” separation number of

. We denote this by

(

s, t

). Note that if

and

are adjacent or

, then

(

s, t

) := +

∞

. The “static” separation number between

and

, the original positions of Facilitator’s agents, is simply the smallest size of a (

s, t

)-vertex

1We refer the reader to Section 2 for the deﬁnitions of these complexity classes.

Misra, Mulpuri, Tale, and Viramgami 3

cut, i.e, a subset of vertices whose removal disconnects

and

. We use

λG

(

s, t

)to denote

the minimum size of a vertex (

s, t

)-separator in

. It is clear that

(

s, t

)

≤λG

(

s, t

), since

positioning

λG

(

s, t

)many guards on the vertices of a (

s, t

)-vertex allows Divider to win the

game right away. It turns out that

(

s, t

) = 1 if and only if

λG

(

s, t

) = 1. However, there

are examples of graphs where

(

s, t

)is arbitrarily smaller than

λG

(

s, t

)[

]. The results

in [

] for chordal graphs and

-free graphs are based on the fact that in these graphs, it

turns out that dG(s, t) = λG(s, t).

Our Contributions

Given that the problem is hard in the solution size, often regarded the “standard” parameter,

a natural approach is to turn to structural parameters of the input graph. One of the most

popular structural parameters in the context of graphs is treewidth, which is a measure of

how “tree-like” a graph is. XP and FPT algorithms parameterized by treewidth are natural

generalizations of tractability on trees. Indeed, Rendezvous is easy to solve on trees because

λG

(

s, t

) = 1 for any distinct

and

when

is a tree and

st /∈E

(

). The complexity of

Rendezvous parameterized by treewidth, however, is wide open — in particular it is not

even known if the problem is in XP parameterized by treewidth.

Interestingly, it was pointed out in [

] that if the initial positions

and

are not is

the same bag of a tree decomposition of width

, then the upper bound for the dynamic

separation number by

λG

(

s, t

)together with the XP algorithm for the standard parameter

can be employed to solve the problem in

nO(w)

time. Thus, the question that was left open

by Fomin, Golovach, and Thilikos was if the problem can be solved in the same time if

and

are in the same bag. Our ﬁrst contribution is to answer this question in the negative by

showing that Rendezvous is in fact

-hard even for graphs of constant treewidth. In

fact, we show more:

ITheorem 1. Rendezvous is co-NP-hard even when restricted to:

graphs whose feedback vertex set number is at most 14, or

graphs whose pathwidth is at most 16.

In particular, Rendezvous is co-para-NP-hard parameterized by treewidth.

We obtain this hardness by a non-trivial reduction from the 3-Dimensional Matching

problem. In the backdrop of this somewhat surprising result, we are motivated to pursue the

question of the complexity of Rendezvous for larger parameters. It turns out that even

augmenting the feedback vertex set number or the pathwidth with the solution size is not

enough. Speciﬁcally, we show that the problem is unlikely to admit an

FPT

-algorithm even

when parameterized by these combined parameters.

ITheorem 2. Rendezvous is co-W[1]-hard when parameterized by:

the feedback vertex set number and the solution size, or

the pathwidth and the solution size.

This result is shown by a parameter preserving reduction from the (Monotone) NAE-

Integer-3-Sat problem, which was shown to be W[1]-hard when parameterized by the

number of variables by Bringmann et al. [

]. Note that with this, we have a reasonably

complete understanding of Rendezvous in the combined parameter. Indeed, recall that the

problem is

-W[1]-hard and

parameterized by the solution size alone, and

-para-

-hard

parameterized by the feedback vertex set number alone as shown above.

Given the above hardness, we consider Rendevous parameterized by the vertex cover

number, a larger parameter compared to both the feedback vertex set number and pathwidth.

4 Romeo and Juliet Meeting in Forest Like Regions

The status of Rendevous with respect to the vertex cover parameterization was also left

open in [

]. We see that the problem admits a natural exponential kernel in this parameter

when combined with the solution size, and is hence FPT in the combined parameter; however

this kernel cannot be improved to a polynomial kernel under standard complexity-theoretic

assumptions.

ITheorem 3.

Rendezvous is

FPT

when parameterized by the vertex cover number of the

input graph and the solution size. Moreover, the problem does not admit a polynomial kernel

when parameterized by the vertex cover number and the solution size unless

NP⊆co

/poly.

We brieﬂy describe the intuition for the exponential kernel with respect to the vertex

cover number. Suppose the graph

has a vertex cover

, where

|X| ≤ `

, and, one may

assume, without loss of generality, that

s, t ∈X

. Further, for any

Y⊆X

, let

denote the

set of all vertices in

G\X

whose neighborhood in

is exactly

. It is not hard to see that

|IY|> k

, then one might as well “curtail” the set to

+ 1 vertices without changing the

instance. This leads to an exponential kernel in the combined parameter. It is also true that

is bounded, without loss of generality, by

and the size of the common neighbhorhood of

and

to begin with; however, it is unclear if

can always be bounded by some function of

the vertex cover alone. The kernelization lower bound follows from observing the structure

of the reduced instance in the reduction used in [

] to prove that problem is

-W[2]-hard

when parameterized by the solution size.

Finally, we present polynomial time algorithms on two restricted cases.

ITheorem 4.

Rendezvous can be solved in polynomial time on the classes of treewidth at

most two graphs and grids.

Recall that the polynomial time algorithm on the classes of trees, chordal graphs, and

-free graphs is obtained by proving that the size of dynamic separator is same as that of

separator. In case of grids, we present a winning strategy for Divider for any non-trivial

instances. This makes grids unique graph class in which the problem admits polynomial time

algorithm even when dynamic separator can be smaller than separator.

Organization of the paper.

After presenting technical preliminaries in Section 2, we

ﬁrst describe the proof of Theorem 1 in Section 3, along with a separate discussion focused

on the intuition for the proof. We present Theorem 2 in Section 4. The proof of Theorem 3

can be found in Section 5. The polynomial time results are presented in Section 6.

2 Preliminaries

For a positive integer

, we denote the set

{

, . . . , q}

by [

]. We use

to denote the

collection of all non-negative integers.

Graph theory

We use standard graph-theoretic notation, and we refer the reader to [

] for any undeﬁned

notation. For an undirected graph

, sets

(

)and

(

)denote its set of vertices and

edges, respectively. We denote an edge with two endpoints

u, v

. Unless otherwise

speciﬁed, we use

to denote the number of vertices in the input graph

of the problem

under consideration. Two vertices

u, v

(

)are adjacent if there is an edge

. The

open neighborhood of a vertex

, denoted by

(

), is the set of vertices adjacent to

. The

closed neighborhood of a vertex v, denoted by NG[v], is the set NG(v)∪ {v}. We say that a

vertex

is a pendant vertex if

|NG

(

)

= 1. The degree of a vertex

, denoted by

degG

(

), is

Misra, Mulpuri, Tale, and Viramgami 5

equal to the number of vertices in the open neighbourhood of

, i.e.,

degG

(

) =

|NG

(

)

. We

omit the subscript in the notation for neighborhood if the graph under consideration is clear.

For a subset

(

), we deﬁne

[

] =

Sv∈SN

[

]and

(

) =

[

]

. For a subset

Fof edges, we denote by V(F)the collection of endpoints of edges in F. For a subset Sof

(

)(resp. a subset

(

)), we denote the graph obtained by deleting

(resp. deleting

) from

G−S

(resp. by

G−F

). We denote the subgraph of

induced on the set

by G[S].

A graph is connected if there is a path between every pair of distinct vertices. A subset

S⊆V(G)is said to be a connected set if G[S]is connected.

Asimple path, denoted by

[

u, v, d

], is a non-empty graph

of the form

(

) =

{u, x1, . . . , xd, v}

, and

(

) =

{ux1, x1x2, . . . , xd−1xd, xdv}

, where

, and all

’s are

distinct. The vertices

{x1, x2, . . . , xd}

are the internal vertices of

[

u, v, d

], and the vertices

{xi

deg

(

)

, i ∈

[

]

}

, i.e., internal vertices whose degree is strictly greater than 2are

the branching points of

[

u, v, d

]. We use

[

u, v, d1

]

◦P

[

v, w, d2

]to denote the unique simple

path from uto wthat contains vand has d1+d2+ 1 many internal vertices.

A set of vertices

is said to be an independent set if no two vertices in

are adjacent.

For a graph

, a set

X⊆V

(

)is said to be a vertex cover if

(

)

is an independent

set. A set of vertices

is said to be a clique if any two vertices in

are adjacent. A vertex

cover

is a minimum vertex cover if for any other vertex cover

, we have

|X| ≤ |Y|

We denote by

(

)the size of a minimum vertex cover of a graph

. For a graph

, a set

X⊆V

(

)is said to be a feedback vertex set if

(

)

is does not contain a cycle. We

denote by fvs(G)the size of a minimum feedback vertex set of a graph G.

Apath decomposition of a graph

is a sequence

= (

X1, X2, . . . , Xr

)of bags, where

Xi⊆V(G)for each i∈[r], such that the following conditions hold:

i=1 Xi=V(G). In other words, every vertex of Gis in at least one bag.

For every uv ∈E(G), there exists `∈[r]such that the bag X`contains both uand v.

For every

u∈V

(

), if

u∈Xi∩Xk

for some

i≤k

, then

u∈Xj

also for each

such that

i≤j≤k. In other words, the indices of the bags containing uform an interval in [r].

The width of a path decomposition (

X1, X2, . . . , Xr

)is

max1≤i≤r|Xi| −

1. The pathwidth of

a graph

, denoted by

(

), is the minimum possible width of a path decomposition of

Atree decomposition of a graph

is a pair

= (

T, {Xt}t∈V(T)

), where

is a tree whose

every node

is assigned a vertex subset

Xt⊆V

(

), called a bag, such that the following

conditions hold:

St∈V(T)Xt=V(G). In other words, every vertex of Gis in at least one bag.

For every

uv ∈E

(

), there exists a node

such that bag

contains both

and

For every

u∈V

(

), the set

{t∈V

(

) :

u∈Xt}

, i.e., the set of nodes whose

corresponding bags contains u, induces a connected subtree of T.

The width of a tree decomposition

= (

T, {Xt}t∈V(T)

)is

maxt∈V(T)|Xt| −

1. The treewidth

of a graph

, denoted by

(

), is the minimum possible width of a tree decomposition of

M×N

grid is the graph

of the form

(

) =

{

(

i, j

) :

i∈

[

]

, j ∈

[

]

}

, and

E(G) = {(i, j)(i0, j0) : |i−i0|+|j−j0|= 1, i, i0∈[M], j, j0∈[N]}.

Let

and

be multisets of vertices of a graph

(i.e.,

and

can contain several

copies of the same vertex). We say that

and

of the same size are adjacent if there is

a bijective mapping

X→Y

such that for

x∈X

, either

(

)or

and

(

)are

adjacent in G.

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

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

10 玖币 0人已下载

立即下载

摘要：

RomeoandJulietMeetinginForestLikeRegionsNeeldharaMisra!ÏIndianInstituteofTechnology,Gandhinagar,IndiaManasMulpuri!IndianInstituteofTechnology,Gandhinagar,IndiaPrafullkumarTale!ÏIndianInstituteofScienceEducationandResearch,Pune,IndiaGauravViramgami!IndianInstituteofTechnology,Gandhinagar,IndiaAbstra...

展开>> 收起<<

Romeo and Juliet Meeting in Forest Like Regions.pdf

共29页,预览5页

还剩页未读，继续阅读

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

Romeo and Juliet Meeting in Forest Like Regions

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: