On the Minimum Cycle Cover problem on graphs with bounded co-degeneracy Gabriel L. Duarte2and U everton S. Souza12

2025-04-24 0 0 474.07KB 14 页 10玖币

侵权投诉

On the Minimum Cycle Cover problem on

graphs with bounded co-degeneracy?

Gabriel L. Duarte2and U´everton S. Souza1,2

1Institute of Informatics, University of Warsaw, Warsaw, Poland

2Instituto de Computa¸c˜ao, Universidade Federal Fluminense, Niter´oi, Brazil

gabrield@id.uff.br,ueverton@ic.uff.br

Abstract. In 2017, Knop, Kouteck´y, Masaˇr´ık, and Toufar [WG 2017]

asked about the complexity of deciding graph problems Πon the com-

plement of Gconsidering a parameter pof G, especially for sparse graph

parameters such as treewidth. In 2021, Duarte, Oliveira, and Souza

[MFCS 2021] showed some problems that are FPT when parameterized

by the treewidth of the complement graph (called co-treewidth). Since

the degeneracy of a graph is at most its treewidth, they also introduced

the study of co-degeneracy (the degeneracy of the complement graph) as

a parameter. In 1976, Bondy and Chv´atal [DM 1976] introduced the no-

tion of closure of a graph: let `be an integer; the (n+`)-closure, cln+`(G),

of a graph Gwith nvertices is obtained from Gby recursively adding

an edge between pairs of nonadjacent vertices whose degree sum is at

least n+`until no such pair remains. A graph property Υdeﬁned on all

graphs of order nis said to be (n+`)-stable if for any graph Gof order

nthat does not satisfy Υ, the fact that uv is not an edge of Gand that

G+uv satisﬁes Υimplies d(u) + d(v)< n +`. Duarte et al. [MFCS 2021]

developed an algorithmic framework for co-degeneracy parameterization

based on the notion of closures for solving problems that are (n+`)-

stable for some `bounded by a function of the co-degeneracy. In 2019,

Jansen, Kozma, and Nederlof [WG 2019] relax the conditions of Dirac’s

theorem and consider input graphs Gin which at least n−kvertices

have degree at least n

2, and present an FPT algorithm concerning to k,

to decide whether such graphs Gare Hamiltonian. In this paper, we ﬁrst

determine the stability of the property of having a bounded cycle cover.

After that, combining the framework of Duarte et al. [MFCS 2021] with

some results of Jansen et al. [WG 2019], we obtain a 2O(k)·nO(1)-time

algorithm for Minimum Cycle Cover on graphs with co-degeneracy at

most k, which generalizes Duarte et al. [MFCS 2021] and Jansen et al.

[WG 2019] results concerning the Hamiltonian Cycle problem.

Keywords: degeneracy. complement graph. cycle cover. FPT. kernel

?This research has received funding from Rio de Janeiro Research Support Foun-

dation (FAPERJ) under grant agreement E-26/201.344/2021, National Coun-

cil for Scientiﬁc and Technological Development (CNPq) under grant agree-

ment 309832/2020-9, and the European Research Council (ERC) under the

European Union’s Horizon 2020 research and innovation pro-

gramme under grant agreement CUTACOMBS (No. 714704).

arXiv:2210.06703v1 [cs.DS] 13 Oct 2022

1 Introduction

Graph width parameters are useful tools for identifying tractable classes of in-

stances for NP-hard problems and designing eﬃcient algorithms for such prob-

lems on these instances. Treewidth and clique-width are two of the most po-

pular graph width parameters. An algorithmic meta-theorem due to Courcelle,

Makowsky, and Rotics [7] states that any problem expressible in the monadic

second-order logic on graphs (MSO1) can be solved in FPT time when parame-

terized by the clique-width of the input graph.3In addition, Courcelle [5] states

that any problem expressible in the monadic second-order logic of graphs with

edge set quantiﬁcations (MSO2) can be solved in FPT time when parameterized

by the treewidth of the input graph. Although the class of graphs with bounded

treewidth is a subclass of the class of graphs with bounded clique-width [4], the

MSO2logic on graphs extends the MSO1logic, and there are MSO2properties

like “Ghas a Hamiltonian cycle” that are not MSO1expressible [6]. In addi-

tion, there are problems that are ﬁxed-parameter tractable when parameterized

by treewidth, such as MaxCut,Largest Bond,Longest Cycle,Longest

Path,Edge Dominating Set,Graph Coloring,Clique Cover,Mini-

mum Path Cover, and Minimum Cycle Cover that cannot be FPT when

parameterized by clique-width [12,15,16,17,18], unless FPT = W[1].

For problems that are ﬁxed-parameter tractable concerning treewidth, but

intractable when parameterized by clique-width, the identiﬁcation of tractable

classes of instances of bounded clique-width and unbounded treewidth becomes

a fundamental quest [11]. In 2016, Dvoˇr´ak, Knop, and Masaˇr´ık [13] showed that

k-Path Cover is FPT when parameterized by the treewidth of the complement

of the input graph. This implies that Hamiltonian Path is FPT when param-

eterized by the treewidth of the complement graph. In 2017, Knop, Kouteck´y,

Masaˇr´ık, and Toufar (WG 2017, [21]) asked about the complexity of deciding

graph problems Πon the complement of Gconsidering a parameter pof G(i.e.,

with respect to p(G)), especially for sparse graph parameters such as treewidth.

In fact, the treewidth of the complement of the input graph, proposed be called

co-treewidth in [11], seems a nice width parameter to deal with dense instances of

problems that are hard concerning clique-width. MaxCut,Clique Cover, and

Graph Coloring are example of problems W[1]-hard concerning clique-width

but FPT-time solvable when parameterized by co-treewidth (see [11]).

The degeneracy of a graph Gis the least ksuch that every induced subgraph

of Gcontains a vertex with degree at most k. Equivalently, the degeneracy of

Gis the least ksuch that its vertices can be arranged into a sequence so that

each vertex is adjacent to at most kvertices preceding it in the sequence. It is

well-known that the degeneracy of a graph is upper bounded by its treewidth;

thus, the class of graphs with bounded treewidth is also a subclass of the class of

graphs with bounded degeneracy. In [11], Duarte, Oliveira, and Souza presented

an algorithmic framework to deal with the degeneracy of the complement graph,

called co-degeneracy, as a parameter.

3Originally this required a clique-width expression as part of the input.

Although the notion of co-parameters is as natural as their complementary

versions, just a few studies have ventured into the world of dense instances with

respect to sparse parameters of their complements. Also, note that would be nat-

ural to consider “co-clique-width” parameterization, but Courcelle and Olariu [8]

proved that for every graph Gits clique-width is at most twice the clique-width

of G. Thus, the co-clique-width notion is redundant from the point of view of

parameterized complexity. Therefore, in the sense of being a useful parameter for

many NP-hard problems in identifying a large and new class of (dense) instances

that can be eﬃciently handled, the co-degeneracy seems interesting because it

is incomparable with clique-width and stronger4than co-treewidth.

In [11], Duarte, Oliveira, and Souza developed an algorithmic framework for

co-degeneracy parameterization based on the notion of Bondy-Chv´atal closure

for solving problems that have a “bounded” stability concerning some closure.

More precisely, for a graph Gwith nvertices, and two distinct nonadjacent

vertices uand vof Gsuch that d(u) + d(v)≥n, Ore’s theorem states that Gis

hamiltonian if and only if G+uv is hamiltonian. In 1976, Bondy and Chv´atal [2]

generalized Ore’s theorem and deﬁned the closure of a graph:

–let `be an integer; the (n+`)-closure, cln+`(G), of a graph Gis obtained

from Gby recursively adding an edge between pairs of nonadjacent vertices

whose degree sum is at least n+`until no such pair remains.

Bondy and Chv´atal showed that cln+`(G) is uniquely determined from Gand

that Gis hamiltonian if and only if cln(G) is hamiltonian.

A property Υdeﬁned on all graphs of order nis said to be (n+`)-stable if

for any graph Gof order nthat does not satisfy Υ, the fact that uv is not an

edge of Gand that G+uv satisﬁes Υimplies d(u)+d(v)< n+`. In other words,

if uv /∈E(G), d(u) + d(v)≥n+`and G+uv has property Υ, then Gitself has

property Υ(c.f. [3]). The smallest integer n+`such that Υis (n+`)-stable is

the stability of Υ, denoted by s(Υ). Note that Bondy and Chv´atal showed that

Hamiltonicity is n-stable. A survey on the stability of graph properties can be

found in [3].

In [11], based on the fact that the class of graphs with co-degeneracy at

most kis closed under completion (edge addition), it was proposed the following

framework for determining whether a graph Gsatisﬁes a property Υin FPT

time regarding the co-degeneracy of G, denoted by k:

1. determine an upper bound for s(Υ) - the stability of Υ;

2. If s(Υ)≤n+`where `≤f(k) (for some computable function f) then

(a) set G= cln+`(G);

(b) since G= cln+`(G) and Ghas co-degeneracy kthen Ghas co-vertex

cover number (distance to clique) at most 2k+`+ 1 (see [11]);

co-vertex cover parameterization.

4A parameter yis stronger than x, if the set of instances where xis bounded is a

subset of those where yis bounded.

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

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

10 玖币 0人已下载

立即下载

摘要：

OntheMinimumCycleCoverproblemongraphswithboundedco-degeneracy?GabrielL.Duarte2andUevertonS.Souza1;21InstituteofInformatics,UniversityofWarsaw,Warsaw,Poland2InstitutodeComputac~ao,UniversidadeFederalFluminense,Niteroi,Brazilgabrield@id.uff.br,ueverton@ic.uff.brAbstract.In2017,Knop,Koutecky,Masar...

展开>> 收起<<

On the Minimum Cycle Cover problem on graphs with bounded co-degeneracy Gabriel L. Duarte2and U everton S. Souza12.pdf

共14页,预览3页

还剩页未读，继续阅读

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

On the Minimum Cycle Cover problem on graphs with bounded co-degeneracy Gabriel L. Duarte2and U everton S. Souza12

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: