关于在 2-连通有向图中找到超过最小度数界限的长有向圈的注记-计算机科学-有向图-算法.pdfVIP

关于在2-连通有向图中找到超过最小度数界限的长有向圈的

注记

JadwigaCzyewska∗MarcinPilipczuk†

摘要

对于有向图，设mindeg为所有顶点的入度和出度的最小值。很容易看出，包

含一个长度至少为mindeg的有向环。在这篇笔记中，我们证明了即使是-连通的，

检查是否包含长度至少为mindeg的环也是NP-难的问题。这与Fomin、Golovach、

Sagunov和Simonov[SODA2022]关于无向图中类似问题的近期算法结果形成对比。

本

译1介绍

中

1图的最小度数，记为mindeg，定义如下：如果是无向图，它就是所有顶点的度

v数的最小值；如果是有向图，它就是所有顶点的入度和出度中的最小值。

7

0狄拉克在1952年[1]证明了一个无向2-连通图包含一个长度至少为mindeg的环。在

8

3SODA2022上，Fomin,Golovach,Sagunov,和Simonov[2]提出了狄拉克定理的以下算法版

0

.本：寻找一个长度至少为mindeg的环在中是固定参数可解的，即可以在时间

7

0poly内求解，对于某个可计算函数。一个自然的问题，在过去几年的多次开放问题讨

5

2论会上被非正式地重复提出（也在[2]的结论部分提到，尽管对Thomassen的一个定理[4]的记

:

v忆有误），即这种事实是否在有向图中也有类似的情况。

i

xThomassen展示了在特殊情况下[4]狄拉克定理的类比是成立的mindeg。

r

a很容易看出每个有向图包含一个长度至少为mindeg的环。那么很自然地提出关于寻

找长度为mindeg的环的参数化算法的问题。在这项工作中，我们证明了当和

是-连通时，这个问题是NP难的。（有向图是-连通的，如果对于任意两个顶点和，在

中存在两条从到的不相交路径。）

观察到由于以下构造（也出现在未定向设置中的[3]），2-连通性假设是必不可少的。令为

有向哈密顿圈问题的一个实例，并表示为。对于每一个，创建一个包含

个顶点的有向团，并将其中一个顶点与标识。新图的最小度数为，并且只有在

输入图中存在哈密尔顿圈时，才有可能形成长度至少为的圈。

我们的工作本质上是一个观察，即对于输入实例哈密顿回路的边（而不是前述构造中的顶

点）存在类似的度数增加装置，保持最终图连通。尚不清楚更高的连通性假设（例如，连通

性）是否会对结果产生重大影响。

∗UniversityofWarsaw,Poland(j.czyzewska@mimuw.edu.pl).SupportedbyPolishNationalSci-

enceCentreSONATABIS-12grantnumber2022/46/E/ST6/00143.†UniversityofWarsaw,Poland

(m.pilipczuk@mimuw.edu.pl).SupportedbyPolishNationalScienceCentreSONATABIS-12grantnum-

ber2022/46/E/ST6/00143.

1

符号。我们使用标准的图论符号。本文中所有的图都是有限、简单且无权的。图的顶点集表

示为，边集表示为。

在无向图中，顶点和之间的边表示为。在有向图中，从顶点到的弧表示