Faster parameterized algorithms for modification problems to minor-closed classes_2

2025-04-27 0 0 1.39MB 75 页 10玖币

侵权投诉

1/ 75 2024:19

Faster parameterized algorithms

for modification problems to

minor-closed classes

Received Jul 21, 2023

Revised May 31, 2024

Accepted Jul 21, 2024

Published Aug 12, 2024

Key words and phrases

Graph minors, Parameterized

algorithms, Graph modification

problems, Vertex deletion,

Elimination distance, Irrelevant

vertex technique, Flat Wall

Theorem, Obstruction set

Laure Morellea

Ignasi Saua

Giannos Stamoulisb

Dimitrios M. Thilikosa

aLIRMM, Université de

Montpellier, CNRS, Montpellier,

France

bInstitute of Informatics,

University of Warsaw, Poland

ABSTRACT. Let

be a minor-closed graph class and let

𝐺

be an

𝑛

-vertex graph. We say

that

𝐺

is a

𝑘

-apex of

𝐺

contains a set

𝑆

of at most

𝑘

vertices such that

𝐺\𝑆

belongs to

Our ﬁrst result is an algorithm that decides whether

𝐺

is a

𝑘

-apex of

in time 2

poly(𝑘)·𝑛2

improving a previous algorithm by Sau, Stamoulis, and Thilikos [ICALP 2020, TALG 2022] whose

running time was 2

poly(𝑘)·𝑛3

. The elimination distance of

𝐺

, denoted by

edG(𝐺)

, is the

minimum number of rounds required to reduce each connected component of

𝐺

to a graph

by removing one vertex from each connected component in each round. Bulian and

Dawar [Algorithmica 2017] provided an FPT-algorithm, with parameter

𝑘

, to decide whether

edG(𝐺) ≤ 𝑘

. The class of graphs with

ed𝐺≤𝑘

is minor-closed, hence characterized by a ﬁnite

set of excluded minors. The algorithm of Bulian and Dawar is based on the computability of this

ﬁnite minor-obstruction set and its dependence on

𝑘

is not explicit. We extend the techniques

used in our ﬁrst algorithm to decide whether

edG(𝐺) ≤ 𝑘

in time 2

22poly(𝑘)·𝑛2

. This is the ﬁrst

algorithm for this problem with an explicit parametric dependence in

𝑘

. In the special case

where

excludes some apex-graph as a minor, we give two alternative algorithms, one running

in time 2

2O(𝑘2log 𝑘)·𝑛2

and one running in time 2

poly(𝑘)·𝑛3

. As a stepping stone for these algorithms,

we provide an algorithm that decides whether

edG(𝐺) ≤ 𝑘

in time 2

O(tw·𝑘+tw log tw)·𝑛

, where

All authors where supported by the ANR projects DEMOGRAPH (ANR-16-CE40-0028), ELIT (ANR-20-CE48-0008), ESIGMA

(ANR-17-CE23-0010), the French-German Collaboration ANR/DFG Project UTMA (ANR-20-CE92-0027). The first and the

last author were also supported by the Franco-Norwegian project PHC AURORA 2024 (Projet no. 51260WL). Most of the

research work for this paper was conducted when Giannos Stamoulis was affiliated with LIRMM, Univ Montpellier, CNRS,

Montpellier, France. A conference version of this article appeared in the Proceedings of the 50th International Colloquium on

Automata, Languages, and Programming (ICALP) [56].

Cite as Laure Morelle, Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos. Faster

parameterized algorithms for modification problems to minor-closed classes.

TheoretiCS, Volume 3 (2024), Article 19, 1-75.

https://theoretics.episciences.org

DOI 10.46298/theoretics.24.19

2/ 75 L. Morelle, I. Sau, G. Stamoulis, D.M. Thilikos

is the treewidth of

𝐺

. This algorithm combines the dynamic programming framework of Reidl,

Rossmanith, Villaamil, and Sikdar [ICALP 2014] for the particular case where

contains only

the empty graph (i.e., for treedepth) with the representative-based techniques introduced by

Baste, Sau, and Thilikos [SODA 2020]. In the complexities above, poly is a polynomial function

whose degree depends on

, and the hidden constants also depend on

. Finally, we provide

explicit upper bounds on the size of the graphs in the minor-obstruction set of the class of

graphs E𝑘(G) ={𝐺|edG(𝐺) ≤ 𝑘}.

1. Introduction

The distance from triviality is a concept formalized by Guo, Hüner, and Niedermeier [35]to

express the closeness of a graph to a supposedly “simple” target graph class. One such a measure

of closeness is, for instance, the number of vertices or edges that one must delete/add from/to a

graph

𝐺

to obtain a graph in the target graph class. This concept of distance to a graph class has

recently gained the interest of the parameterized complexity community. The motivation is

that, if a problem is tractable on a graph class

, it is natural to study other classes of graphs

according to their “distance to

”. In this paper, we focus on two such measures of distance

from triviality: Given a target graph class

, we consider the vertex deletion distance to

and

the elimination distance to G, which we formalize next.

Given a target graph class

and a non-negative integer

𝑘

, we deﬁne

A𝑘(G)

as the set of

all graphs containing a set

𝑆

of at most

𝑘

vertices whose removal results in a graph in

. If

𝐺∈ A𝑘(G)

, then we say that

𝐺

is a

𝑘

-apex of

. We refer to

𝑆

as a

𝑘

-apex set of

𝐺

for the class

In other words, we consider the following meta-problem for a ﬁxed class G.

Vertex Deletion to G

Input: A graph 𝐺and a non-negative integer 𝑘.

Objective: Find, if it exists, a

𝑘

-apex set of

𝐺

for the class

Throughout the paper, we denote by

𝑛

the number of vertices of the input graph of the prob-

lem under consideration. The importance of Vertex Deletion to

can be illustrated by the

variety of graph modiﬁcation problems that it encompasses (hence the term of meta-problem).

For instance, if

is the class of edgeless (resp. acyclic, planar, bipartite, (proper) interval,

chordal) graphs, then we obtain the Vertex Cover (resp. Feedback Vertex Set,Vertex Pla-

narization,Odd Cycle Transversal,(proper) Interval Vertex Deletion,Chordal Vertex

Deletion) problem.

The second measure of distance from triviality that we study was recently introduced by

Bulian and Dawar [17,16]. Given a graph class

, we deﬁne the elimination distance of a graph

3/ 75 Faster parameterized algorithms for modification problems to minor-closed classes

𝐺to G, denoted by edG(𝐺), as follows:

edG(𝐺)=









0if 𝐺∈ G,

1+min{edG(𝐺\ {𝑣}) | 𝑣∈𝑉(𝐺)} if 𝐺is connected,

max{edG(𝐻) | 𝐻is a connected component of 𝐺}otherwise.

Given that

edG(𝐺) ≤ 𝑘

, a set

𝑆⊆𝑉(𝐺)

of vertices recursively deleted from

𝐺

to achieve

edG(𝐺)

is called a

𝑘

-elimination set of

𝐺

for

. We deﬁne the (parameterized) class of graphs

E𝑘(G) ={𝐺|edG(𝐺) ≤ 𝑘}

. The above notion can be seen as a natural generalization of

treedepth (denoted by

), which corresponds to the case where

contains only the empty

graph. Treedepth, along with treewidth, are two of the most studied and widely used parameters

to measure the structural complexity of a graph [19,48,57]. The second meta-problem that we

consider is the following, again for a ﬁxed class G.

Elimination Distance to G

Input: A graph 𝐺and a non-negative integer 𝑘.

Objective: Find, if it exists, a

𝑘

-elimination set of

𝐺

for

the class G.

Unsurprisingly, Vertex Deletion to

is NP-hard for every non-trivial graph class

[54],

while Elimination Distance to

is NP-hard even when

contains only the empty graph [60].

To circumvent this intractability, we study both problems from the parameterized complexity

point of view and consider their parameterizations by

𝑘

. In this setting, the most desirable

behavior is the existence of an algorithm running in time

𝑓(𝑘) · 𝑛O(1)

, where

𝑓

is a computable

function depending only on

𝑘

. Such an algorithm is called ﬁxed-parameter tractable, or FPT-

algorithm for short, and a parameterized problem admitting an FPT-algorithm is said to belong

to the parameterized complexity class FPT. Also, the function

𝑓

is called parametric dependence

of the corresponding FPT-algorithm, and the challenge is to design FPT-algorithms with small

parametric dependencies and with a polynomial factor of small degree [19,21,25,58]. We

may also consider XP-algorithms, i.e., algorithms running in time

O(𝑓(𝑘) · 𝑛𝑔(𝑘))

for some

computable functions 𝑓and 𝑔depending only on 𝑘.

In general, for any of the two considered problems, we cannot expect FPT-algorithms for

every graph class

. For instance, the two problems are NP-hard, even for

𝑘=

0, for every

graph class

whose recognition problem is NP-hard. This is the case of 3-colorable graphs,

which is a class closed under taking (induced) subgraphs. In this paper, we focus on a family of

graph classes that exhibits a nice behavior with respect to the considered problems (and many

others): we consider

to be a minor-closed graph class, i.e., such that every minor of a graph in

(that is, obtained from a subgraph of a graph in

by contracting edges; see Subsection 2.1

for the formal deﬁnition) is also in

. Indeed, it turns out that, for every such a family

, the

problems become ﬁxed-parameter tractable, as we proceed to discuss.

4/ 75 L. Morelle, I. Sau, G. Stamoulis, D.M. Thilikos

The minor-obstruction set (in short obstruction set) of

is the set of minor-minimal graphs

that do not belong to

, and is denoted by

obs(G)

. Notice that

obs(G)

gives a complete charac-

terization of

as, for every graph

𝐺

, it holds that

𝐺∈ G

if and only if, for every

𝐻∈obs(G)

𝐻

is not a minor of

𝐺

. Because of Robertson and Seymour’s theorem [65],

obs(G)

is ﬁnite for

every minor-closed graph class. As checking whether an

ℎ

-vertex graph

𝐻

is a minor of

𝐺

can

be done in time

𝑓(ℎ) ·𝑛2

[63,43], the ﬁniteness of

obs(G)

along with the above characterization

imply that, for every minor-closed graph class

, checking whether

𝐺∈ G

can be done in time

𝑐·𝑛2

, where

𝑐

is a constant depending on the graph class

. This meta-theorem implies the

existence of FPT-algorithms for a wide family of problems, including Vertex Deletion to

and Elimination Distance to

. Indeed, this follows by observing that if

is minor-closed,

then for every non-negative integer 𝑘, the classes A𝑘(G) and E𝑘(G) are also minor-closed.

As Robertson and Seymour’s theorem [65]does not give any way to construct the corre-

sponding obstruction sets, the aforementioned argument is not constructive, i.e., it is not able to

construct the obstruction sets required for the corresponding FPT-algorithms. Moreover, these

algorithms are non-uniform in

𝑘

, meaning that we have a distinct algorithm for every value of

𝑘

Important steps towards the constructibility of such FPT-algorithms were done by Adler, Grohe,

and Kreutzer [2]and Bulian and Dawar [16], who respectively proved that

obs(A𝑘(G))

and

obs(E𝑘(G))

are eectively computable. Hence, for both problems, it is possible to construct

uniform (in

𝑘

) algorithms running in time

𝑓(𝑘) · 𝑛2

for some computable function

𝑓

. However,

this does not imply any reasonable, or even explicit, parametric dependence of the obtained

algorithms.

The main focus of this paper is on the parametric and polynomial dependence of FPT-

algorithms to solve Vertex Deletion to

and Elimination Distance to

, i.e., for recognizing

the classes A𝑘(G) and E𝑘(G), when Gis a minor-closed graph class.

Concerning Vertex Deletion to

, after a number of articles for particular cases of minor-

closed classes

, such as graphs of bounded treewidth [28,46], planar graphs [55,38], or graphs

of bounded genus [49], an explicit FPT-algorithm for any minor-closed graph

was recently

proposed by Sau, Stamoulis, and Thilikos [70], running in time 2

O(𝑘𝑐)·𝑛3

, where

𝑐

is a constant

that depends on the maximum size of a graph in the obstruction set of

. Moreover, in the case

where

obs(G)

contains some apex-graph (that is, a 1-apex for the class of planar graphs), Sau,

Stamoulis, and Thilikos [70]gave an improved running time of 2

O(𝑘𝑐)·𝑛2

. Note also that the

more general variant where Gis a topological-minor-closed graph class is in FPT as well [29].

As for Elimination Distance to

when

is minor-closed, no explicit parametric de-

pendence was known, with the notable exception of treedepth, for which Reidl, Rossmanith,

Villaamil, and Sikdar [61]gave an algorithm deciding whether

td(𝐺) ≤ 𝑘

in time 2

O(𝑘·tw)·𝑛

where

=tw(𝐺)

(see also [15]). Using our terminology, and given that

tw(𝐺) ≤ td(𝐺)

for

every graph

𝐺

, this yields an FPT-algorithm for Elimination Distance to

G∅

, where

G∅

is the

class consisting of the empty graph, running in time 2

O(𝑘2)·𝑛

. Note that this algorithm [61],

5/ 75 Faster parameterized algorithms for modification problems to minor-closed classes

combined with the fact that

td(𝐺) ≤ log(𝑛) · tw(𝐺)

(see [15]), imply an XP-algorithm for the

problem of computing

when parameterized by

, namely an algorithm that computes the

value of

td(𝐺)

in time

𝑛O(tw(𝐺)2)

. To the best of our knowledge, it is open whether computing

parameterized by tw is in FPT.

Before describing our results, let us mention some recent relevant results dealing with

Elimination Distance to

for classes

that are not necessarily minor-closed. Agrawal and

Ramanujan [6](resp. Agrawal, Kanesh, Panolan, Ramanujan, and Saurabh [5]) provided FPT-

algorithms, with parameter

𝑘

, when

is the class of cliques (resp. graphs of bounded degree).

Fomin, Golovach, and Thilikos [27]identiﬁed sucient and necessary conditions for the ex-

istence of FPT-algorithms when

is deﬁnable in ﬁrst-order logic (such as having bounded

degree). Jansen, de Kroon, and Włodarczyk [37]proved, among a number of other results, that

is a hereditary union-closed graph class and Vertex Deletion to

can be solved in time

𝑘O(1)·𝑛O(1)

(as it is the case for every minor-closed class

by the results of [70]), then there is

an algorithm that, given an

𝑛

-vertex graph

𝐺

, computes an

O(edG(𝐺)3)

-elimination set of

𝐺

for

in time 2

edG(𝐺)O(1)·𝑛O(1)

. Therefore, for union-closed minor-closed graph classes

, the result

of [37]yields an FPT-approximation algorithm for Elimination Distance to G.

Note that, for every graph class

and every graph

𝐺

, it holds that

edG(𝐺)

is not larger

than the smallest

𝑘

such that

𝐺

admits a

𝑘

-apex for

. Thus, if Elimination Distance to

is in

FPT, so is Vertex Deletion to

. Agrawal, Kanesh, Lokshtanov, Panolan, Ramanujan, Saurabh,

and Zehavi [4]showed, among other results, that in many cases the reverse implication also

holds. Namely, they proved that if

is hereditary, union-closed, and deﬁnable in monadic

second-order logic, and Vertex Deletion to

is in FPT, then Elimination Distance to

also (non-uniformly) in FPT. Incidentally, they also showed that if

is deﬁned by excluding a

ﬁnite number of connected topological minors, then Elimination Distance to

is (uniformly)

in FPT. We note that the results of [4]do not provide explicit parametric dependencies for these

FPT-algorithms. Also, let us mention that it was conjectured in [4]that Elimination Distance

is in FPT parameterized by a generalization of treewidth called

-treewidth (see [37,4,

23]). Note that, if true, this conjecture would answer the open problem mentioned above of

whether computing td parameterized by tw is in FPT.

Our results. In this paper, we provide explicit FPT-algorithms for Vertex Deletion to

and

Elimination Distance to

for every ﬁxed minor-closed graph class

. Our ﬁrst result is the

following.

THEOREM 1.1. For every minor-closed graph class

, there exists an algorithm that solves

Vertex Deletion to Gin time 2𝑘O(1)·𝑛2.

The degree of

𝑘

in the running time of Theorem 1.1, as well as the constants hidden in the

-notation in the running time of the algorithms of the results below, depend on the maximum

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

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

10 玖币 0人已下载

立即下载

摘要：

1/752024:19Fasterparameterizedalgorithmsformodificationproblemstominor-closedclassesReceivedJul21,2023RevisedMay31,2024AcceptedJul21,2024PublishedAug12,2024KeywordsandphrasesGraphminors,Parameterizedalgorithms,Graphmodificationproblems,Vertexdeletion,Eliminationdistance,Irrelevantvertextechnique,Fla...

展开>> 收起<<

Faster parameterized algorithms for modification problems to minor-closed classes_2.pdf

共75页,预览5页

还剩页未读，继续阅读

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

Faster parameterized algorithms for modification problems to minor-closed classes_2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: