The Complexity of Online Graph Games

2025-05-02 0 0 701.97KB 21 页 10玖币

侵权投诉

Janosch Fuchs

Department of Computer Science, RWTH Aachen University, Germany

fuchs@algo.rwth-aachen.de

Christoph Grüne

Department of Computer Science, RWTH Aachen University, Germany

gruene@algo.rwth-aachen.de

Tom Janßen

Department of Computer Science, RWTH Aachen University, Germany

janssen@algo.rwth-aachen.de

Abstract

Online computation is a concept to model uncertainty where not all information on a problem

instance is known in advance. An online algorithm receives requests which reveal the instance

piecewise and has to respond with irrevocable decisions. Often, an adversary is assumed that

constructs the instance knowing the deterministic behavior of the algorithm. Thus, the adversary

is able to tailor the input to any online algorithm. From a game theoretical point of view, the

adversary and the online algorithm are players in an asymmetric two-player game.

To overcome this asymmetry, the online algorithm is equipped with an isomorphic copy of the

graph, which is referred to as unlabeled map. By applying the game theoretical perspective on online

graph problems, where the solution is a subset of the vertices, we analyze the complexity of these

online vertex subset games. For this, we introduce a framework for reducing online vertex subset

games from TQBF. This framework is based on gadget reductions from 3-Satisfiability to the

corresponding oﬄine problem. We further identify a set of rules for extending the 3-Satisfiability-

reduction and provide schemes for additional gadgets which assure that these rules are fulﬁlled.

By extending the gadget reduction of the vertex subset problem with these additional gadgets, we

obtain a reduction for the corresponding online vertex subset game.

At last, we provide example reductions for online vertex subset games based on Vertex Cover,

Independent Set, and Dominating Set, proving that they are PSPACE-complete. Thus, this

paper establishes that the online version with a map of NP-complete vertex subset problems form a

large class of PSPACE-complete problems.

2012 ACM Subject Classiﬁcation Theory of computation

→

Problems, reductions and completeness

Keywords and phrases Online Algorithms, Computational Complexity, Online Algorithms Complex-

ity, Two-Player Games, NP-complete Graph Problems, PSPACE-completeness, Gadget Reduction

Funding This work is funded by the Deutsche Forschungsgemeinschaft (DFG, German Research

Foundation) — GRK 2236/1, WO 1451/2-1.

arXiv:2210.01694v3 [cs.CC] 27 Nov 2023

2 The Complexity of Online Graph Games

1 Introduction

Online computation is an intuitive concept to model real time computation where the full

instance is not known beforehand. In this setting, the instance is revealed piecewise to the

online algorithm and each time a piece of information is revealed, an irrevocable decision

by the online algorithm is required. To analyze the worst-case performance of an algorithm

solving an online problem, a malicious adversary is assumed.

The adversary constructs the instance while the online algorithm has to react and compute

a solution. This setting is highly asymmetric in favor of the adversary. Thus, for most

decision problems, the adversary is able to abuse the imbalance of power to prevent the

online algorithm from ﬁnding a solution that is close to the optimal one. To overcome the

imbalance, there are diﬀerent extensions of the online setting in which the online algorithm

is equipped with some form of a priori knowledge about the instance. In this work, we

analyze the inﬂuence of knowing an isomorphic copy of the input instance, which is also

called an unlabeled map. With the unlabeled map, the algorithm is able to recognize unique

structures while the online instance is revealed – like a vertex with unique degree – but it

cannot distinguish isomorphic vertices or subgraphs.

The relation between the online algorithm and the adversary corresponds to players in an

asymmetric two-player game, in which the algorithm wants to maximize its performance and

the adversary’s goal is to minimize it. The unlabeled map can be considered as the game

board. One turn of the game consists of a move by the adversary followed by a move of the

online algorithm. Thereby, the adversary reveals a vertex together with its neighbors and

the online algorithm has to irrevocably decide whether to include this vertex in the solution

or not. The problem is to evaluate whether the online algorithm has a winning strategy, that

is, it is able to compute a solution of size smaller/greater or equal to the desired solution

size k, for all possible adversary strategies.

Papadimitriou and Yannakakis make use of the connection between games and online

algorithms for analyzing the canadian traveler problem in [

], which is an online problem

where the task is to compute a shortest

-path in an a priori known graph in which certain

edges can be removed by the adversary. They showed that the computational problem of

devising a strategy that achieves a certain competitive ratio is PSPACE-complete by giving

a reduction from True Quantified Boolean Formula, short TQBF.

Independently, Halldórsson [

] introduced the problems online coloring and online in-

dependent set on a priori known graphs, which is equivalent to having an unlabeled map.

He studies how the competitive ratios improve compared to the model when the graph is

a priori not known. Based on these results, Halldórsson et al. [

] continued the work on

the online independent set problem without a priori knowing the graph. These results are

then applied by Boyar et al. [

] to derive a lower bound for the advice complexity of the

online independent set problem. Furthermore, they introduce the class of asymmetric online

covering problems (AOC) containing Online Vertex Cover,Online Independent Set,

Online Dominating Set and others. Boyar et al. [

] analyze the complexity of these

problems as graph property, namely the online vertex cover number, online independence

number and online domination number, by showing their NP-hardness.

Moreover based on the work by Halldórsson [

], Kudahl [

] shows PSPACE-completeness

of the decision problem Online Chromatic Number with Precoloring on an a priori

known graph, which asks whether some online algorithm is able to color

with at most

colors for every possible order in which

is presented while having a precolored part

. This approach is then improved by Böhm and Veselý [

] by showing that Online

J. Fuchs, C. Grüne, T. Janßen 3

Chromatic Number is PSPACE-complete by giving a reduction from TQBF.

Our contribution is to analyze the computational complexity of a subclass of AOC problems

that consider graph problems where the solution is a subset of the vertices. Similar to the

problem Online Chromatic Number, we equip the online algorithm with an unlabeled

map in order to apply and formalize the ideas of Böhm and Veselý. We call these problems

online vertex subset games due to their relation to two-player games. While symmetrical

combinatorial two-player games are typically PSPACE-complete [

], this principle does not

apply to our asymmetrical setting. We are still able to prove PSPACE-completeness for the

online vertex subset games based on Vertex Cover,Independent Set and Dominating

Set by designing reductions such that the adversary’s optimal strategy corresponds to the

optimal strategy of the ∀-player in TQBF.

In order to derive reductions from TQBF to online vertex subset games, we identify

properties describing the revelation or concealment of information to correctly simulate the

∀

- and

∃

-decisions as well as the evaluation of the quantiﬁed Boolean formula in the online

vertex subset game. This simulation is modeled by disjoint and modular gadgets, which form

a so-called gadget reduction – similar to already known reductions between NP-complete

problems. Diﬀerent forms of gadget reductions are described by Agrawal et al. [

] who

formalize

AC0

-gadget-reductions in the context of NP-completeness and by Trevisan et

al. [

] who describe gadgets in reductions of problems that are formalized as linear programs.

By formalizing gadgets capturing the above mentioned properties, we provide a framework

to derive reductions for other online vertex subset games, which are based on problems that

are gadget-reducible from 3-Satisfiability.

Paper Outline

First, we explain the online setting that we use throughout the paper and important terms,

e.g., the online game, the problem class and the reveal model of our online problems.

Secondly, we deﬁne the gadget reduction framework to reduce 3-Satisfiability to vertex

subset problems. In the third section, we extend the framework to the online setting by

identifying a set of important properties that must be fulﬁlled in the reduction. We also

provide a scheme for gadgets that enforce these properties to generalize the framework to

arbitrary vertex subset problems. In the fourth section, we detail the application of this

framework to the problem Vertex Cover. Lastly, we apply the framework to the problems

Independent Set and Dominating Set in the ﬁfth section. At the end, we summarize

the results and give a prospect on future possible work.

Neighborhood Reveal Model

Each request of the online problem reveals information about the instance for the online

algorithm. The amount of information in each step is based on the reveal model. For an

online problem with a map, the subgraph that arrives in one request is called revelation

subgraph.

The neighborhood reveal model, which we use in this paper, was introduced by Haru-

tyunyan et. al. [

]. Within that model, the online algorithm gains information about the

complete neighborhood of the revealed vertex. Nevertheless, the online algorithm has to

make a decision on the current revealed vertex only but not on the exposed neighborhood

vertices. All exposed but not yet revealed neighborhood vertices have to be revealed in the

process of the online problem such that a decision can be made upon them. We denote the

closed neighborhood of vwith N[v], that is, the set of vand all vertices adjacent to v.

4 The Complexity of Online Graph Games

▶

Deﬁnition 1 (Neighborhood Reveal Model).The neighborhood reveal model is deﬁned

by an ordering of graphs (

Vi, Ai, Ei

)

i≤|V|

. The reveal order of the adversary is deﬁned by

adv ∈S|V|, where S|V|is the symmetric group of size |V|. The graph Giis deﬁned by

V0=E0=∅,

Vi=Vi−1∪N[vadv(i)],for 0< i ≤ |V|

Ei=Ei−1∪ {(vadv(i), w)∈E|w∈Vi},for 0< i ≤ |V|.

The revelation subgraph

G′

in the neighborhood reveal model is the subgraph of

deﬁned by

G′

= (

V′, E′

)with

V′

[

vadv(i)

]and

E′

{{vadv(i), w} ∈ E}

. The online algorithm has

to decide whether vadv(i)is in the solution or not.

Online Vertex Subset Games

Throughout the paper, we consider a special class of combinatorial graph problems. The

question is to ﬁnd a vertex subset, whereby the size should be either smaller or equals, for

minimization problems, or greater or equals, for maximization problems, some

, which is

part of the input. Thereby, the vertex set needs to fulﬁll some constraints based on the

speciﬁc problem. We call these problems vertex subset problems. Well-known problems like

Vertex Cover,Independent Set and Dominating Set are among them.

We denote the online version with a map of a vertex subset problem

PV S

with

PV S

and

deﬁne them as follows.

▶

Deﬁnition 2 (Online Vertex Subset Game).An online vertex subset game

PV S

has a graph

and a

k∈N

as input. The question is, whether the online algorithm is able to ﬁnd a

vertex set of size smaller (resp. greater) or equals

, which fulﬁlls the constraints of

PV S

for

all strategies of the adversary. Thereby, the online algorithm has access to an isomorphic

copy of

and the adversary reveals the vertices according to the neighborhood reveal model.

2 Gadget Reductions

Gadget reductions are a concept to reduce combinatorial problems in a modular and structured

way. For the context of the paper, we deﬁne gadget reductions from 3-Satisfiability to

vertex subset problems. The 3-Satisfiability instances

= (

L, C

)are deﬁned by their

literals

and their clauses

. We use a literal vertex

vℓ

for all

ℓ∈L

to represent a literal

in the graph. There are implicit relations over the literals besides the explicit relation

in that the reduction may be decomposed. For example, the relation between a literal and

its negation, which is usually implicitly used to build up a variable gadget. These variable

gadgets are connected by graph substructures that assemble the clauses as clause gadgets.

▶

Deﬁnition 3 (Gadget Reduction from 3-Satisfiability to Vertex Subset Problems).A

gadget reduction

Rgadget

(

PV S

)from a 3-Satisfiability formula

= (

L, C

)to a vertex

subset problem with graph

Gφ

= (

V, E

)is a tuple containing functions from the literal set

and all relations of the 3-Satisfiability formula to the vertex set and all relations of the

vertex subset problem. In the following, we denote the gadget based on element

to be

:= (

Vx, Ex

)with

being a set of vertices and

a set of edges, whereby the edges are

potentially incident to vertices of a diﬀerent gadget.

The literal set of a 3-Satisfiability formula

ℓ1, ℓ2, . . . , ℓ|L|−1, ℓ|L|

is mapped to the

vertex set of the graph problem. Thereby, each literal is mapped to exactly one vertex:

RL→V

gadget(PV S ) : L→V, ℓ 7→ Gℓ

J. Fuchs, C. Grüne, T. Janßen 5

The following relations on the literals are mapped as well.

(1) Literal - Negated Literal: RL,L

gadget(PV S ) : R(L, L)→(V, E),(ℓ, ℓ)7→ Gℓ,ℓ

(2) Clause: RC

gadget(PV S ) : R(C)→(V, E), Cj7→ GCj

(3) Literal - Clause: RL,C

gadget(PV S ) : R(L, C)→(V, E),(ℓ, Cj)7→ Gℓ,Cj

(4) Negated Literal - Clause: RL,C

gadget(PV S ) : R(L, C)→(V, E),(ℓ, Cj)7→ Gℓ,Cj

Additionally, the following mapping allows for constant parts that do not change depending

on the instance:

Rconst

gadget

(

PV S

) :

∅ →

(

V, E

)

,∅ 7→ Gconst

. Thereby, the vertices and edges of

all gadgets are pairwise disjoint.

We use the more coarse grained view of variable gadgets as well. These combine the

mappings

RL→V

gadget

and

RL,L

gadget

, and

RL,C

gadget

and

RL,C

gadget

RX,C

gadget

, where

the set of nvariables.

The important function of the variable gadget is to ensure that only one of the literals of

ℓ, ℓ ∈L

is chosen. On the other hand, the function of the clause gadget is to ensure together

with the constraints of the vertex subset problem

PV S

that the solution encoded on the

literals fulﬁll the 3-Satisfiability-formula if and only if the literals induce a correct solution.

These functionalities are utilized in the correctness proof of the reduction by identifying the

logical dependencies between the literal vertices

vℓ

for

ℓ∈L

and all other vertices based on

the graph and the constraints of

PV S

together with combinatorial arguments on the solution

size. We denote these logical dependencies as solution dependencies as they are logical

dependencies on the solutions of

PV S

. Due to the asymmetric nature of the online problems,

the adversary can reveal a solution dependent vertex before revealing the corresponding

literal vertex. Thus, a decision on the solution dependent vertex is implicitly also a decision

on the literal vertex, although it has not been revealed. We address this speciﬁc problem

later in the description of the framework.

▶

Deﬁnition 4 (Solution dependent vertices).Given a gadget reduction, the following vertices

of the reduction graph are solution dependent:

1. All literal vertices are solution dependent on their respective variable.

For a literal

ℓ

(resp. its negation

ℓ

), we denote the set of vertices that need to be part of

the solution if

vℓ

(resp.

vℓ

) is part of the solution with

Vℓ

(resp.

Vℓ

). Then the vertices,

that are in one but not both of these sets, i.e.

Vℓ△Vℓ

, are solution dependent on the

corresponding variable.

All vertices that are not solution dependent on any variable are called solution independent.

For example, in the reduction from 3-Satisfiability to Vertex Cover [

], the following

solution dependencies apply: For each literal, the vertices

vℓ

and

vℓ

are solution dependent

on their respective variable. Furthermore, if a literal is part of the solution, all clause vertices

representing its negation must also be part of the solution. Thus all clause vertices are

solution dependent on their respective variable. Consequently, all vertices of the reduction

graph for vertex cover are solution dependent.

3 A Reduction Framework for Online Vertex Subset Games

In this section, we present a general framework for reducing TQBF Game to an arbitrary

online vertex subset game

PV S

with neighborhood reveal model. The TQBF Game is

played on a fully quantiﬁed Boolean formula, where one player decides the

∃

-variables and

the other decides the

∀

-variables, in the order they are quantiﬁed. Deciding whether the

∃

-player has a winning strategy is PSPACE-complete [

], and thus this reduction proves

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

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

10 玖币 0人已下载

立即下载

摘要：

TheComplexityofOnlineGraphGamesJanoschFuchsDepartmentofComputerScience,RWTHAachenUniversity,Germanyfuchs@algo.rwth-aachen.deChristophGrüneDepartmentofComputerScience,RWTHAachenUniversity,Germanygruene@algo.rwth-aachen.deTomJanßenDepartmentofComputerScience,RWTHAachenUniversity,Germanyjanssen@algo.rw...

展开>> 收起<<

The Complexity of Online Graph Games.pdf

共21页,预览5页

还剩页未读，继续阅读

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

The Complexity of Online Graph Games

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: