Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor Daniel LokshtanovMarcin PilipczukMicha l PilipczukSaket Saurabh

2025-05-06 0 0 1.26MB 70 页 10玖币
侵权投诉
Fixed-parameter tractability of Graph Isomorphism
in graphs with an excluded minor
Daniel Lokshtanov∗Marcin Pilipczuk†Micha l Pilipczuk‡Saket Saurabh§
Abstract
We prove that Graph Isomorphism and Canonization in graphs excluding a fixed graph
H
as a minor can be solved by an algorithm working in time
f
(
H
)
·nO(1)
, where
f
is some
function. In other words, we show that these problems are fixed-parameter tractable when
parameterized by the size of the excluded minor, with the caveat that the bound on the running
time is not necessarily computable. The underlying approach is based on decomposing the
graph in a canonical way into unbreakable (intuitively, well-connected) parts, which essentially
provides a reduction to the case where the given
H
-minor-free graph is unbreakable itself. This
is complemented by an analysis of unbreakable
H
-minor-free graphs, performed in a second
subordinate manuscript, which reveals that every such graph can be canonically decomposed
into a part that admits few automorphisms and a part that has bounded treewidth.
∗
University of California, Santa Barbara, USA,
daniello@ucsb.edu
. Supported by BSF award 2018302 and NSF
award CCF-2008838.
†
Institute of Informatics, University of Warsaw, Poland,
marcin.pilipczuk@mimuw.edu.pl
. This work is a part
of project CUTACOMBS that has received funding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (grant agreement No. 714704).
‡
Institute of Informatics, University of Warsaw, Poland,
michal.pilipczuk@mimuw.edu.pl
. This work is a part of
projects TOTAL and BOBR that have received funding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (grant agreements No. 677651 and 948057, respectively).
§
Institute of Mathematical Sciences, India,
saket@imsc.res.in
, and Department of Informatics, University
of Bergen, Norway,
Saket.Saurabh@ii.uib.no
. Supported by the European Research Council (ERC) under the
European Union’s Horizon 2020 research and innovation programme (grant agreement No. 819416), and Swarnajayanti
Fellowship (No. DST/SJF/MSA01/2017-18).
arXiv:2210.14638v1 [cs.DS] 26 Oct 2022
Contents
1 Introduction 1
2 Overview 5
3 Preliminaries 10
3.1 Separations, Separators, and Clique Separators . . . . . . . . . . . . . . . . . . . . . 11
3.2 ImprovedGraph ...................................... 12
3.3 Boundaried Graphs, Gluing and Forgetting, Boundary-Consistency . . . . . . . . . . 13
3.4 Topological Minors Of Boundaried Graphs . . . . . . . . . . . . . . . . . . . . . . . . 13
3.5 Tree Decompositions and Star Decompositions . . . . . . . . . . . . . . . . . . . . . 15
3.6 Isomorphisms of Colored and Labeled Graphs, Lexicographic Ordering . . . . . . . . 16
3.7 (Weak) Isomorphism Invariance, Canonical Labelings . . . . . . . . . . . . . . . . . . 17
4 Statement and Proof of Main Theorems 19
5 Recursive Understanding for Canonization 22
5.1 Canonization Tools for Boundaried Graphs . . . . . . . . . . . . . . . . . . . . . . . 23
5.1.1 Strong And Weak Representatives and their Size Bounds (ηsand ηw) .... 26
5.1.2 Star Decompositions and Leaf-Labelings . . . . . . . . . . . . . . . . . . . . . 29
5.2 UnpumpingandLifting .................................. 32
5.3 Reduction To Improved-Clique-Unbreakable Graphs . . . . . . . . . . . . . . . . . . 37
5.3.1 Canonical Decomposition into Atoms . . . . . . . . . . . . . . . . . . . . . . . 37
5.3.2 Structural Properties of Clique Separators and Improved Graphs . . . . . . . 40
5.3.3 ReductionAlgorithm................................ 43
5.4 Reduction To Unbreakable Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.4.1 k-Important Separators and Important Separator Extension . . . . . . . . . . 50
5.4.2 Unbreakablity-TiedSets.............................. 52
5.4.3 Unbreakability of Weak Representatives . . . . . . . . . . . . . . . . . . . . . 53
5.4.4 StableSeparations ................................. 55
5.4.5 ReductionAlgorithm................................ 55
6 Canonizing unbreakable graphs with an excluded minor 64
1 Introduction
The Graph Isomorphism problem is arguably the most widely known problem whose member-
ship in Pis unknown, but which is not believed to be
NP
-hard. After decades of research, a
quasi-polynomial time algorithm was proposed by Babai in 2015 [Bab16].
While the existence of a polynomial-time algorithm on general graphs is still elusive, the complex-
ity of Graph Isomorphism has been well understood on several classes of graphs, where structural
properties of graphs in question have been used to design polynomial-time procedures solving the
problem. Classic results in this area include an
nO(d)
-time algorithm on graphs of maximum de-
gree
d
[
BL83
,
Luk82
], a polynomial-time algorithm for planar graphs [
HT72
,
HT73
,
HW74
,
Wei66
],
an
nO(g)
-time algorithm on graphs of Euler genus
g
[
FM80
,
Mil80
], an
O
(
nk+4.5
)-time algorithm for
graphs of treewidth
k
[
Bod90
], an
nO(k)
-time algorithm for graphs of rankwidth
k
[
GS15
,
GN21
], an
nf(|H|)
-time algorithm for graphs excluding a fixed graph
H
as a minor [
Pon91
], and an
nf(|H|)
-time
algorithm for graphs excluding a fixed graph
H
as a topological minor [
GM12
] (where
f
is some
computable function).
In all the results mentioned above, the degree of the polynomial bound on the running time de-
pends on the parameter — maximum degree, genus, treewidth
1
, rankwidth, or the size of the excluded
(topological) minor — in at least a linear fashion. Since the parameter can be as high as linear in the
size of the graph, for large values of the parameter the running time bound of the quasi-polynomial-
time algorithm of Babai [Bab16], which works on general graph, is preferable. During the last few
years, there has been several successful attempts of bridging this gap by using the group-theoretic
approach of Babai in conjunction with structural insight about considered graph classes. This led
to algorithms with running time of the form
npolylog(p)
, where
p
is any of the following parameters:
maximum degree [
GNS18
], Euler genus [
Neu20
], treewidth [
Wie20
], and the size of a fixed graph
Hexcluded as a minor [GWN20]. We refer to a recent survey [GN20] for an excellent exposition.
A parallel line of research is to turn the aforementioned algorithms into fixed-parameter tractable
algorithms for the parameters in question. That is, instead of a running time bound of the form
nf(p)
for a computable function
f
and a parameter
p
, we would like to have an algorithm with running time
bound
f
(
p
)
·nc
for a universal constant
c
. In other words, the degree of the polynomial governing
the running time bound should be independent of the parameter; only the leading multiplicative
factor may depend on it.
In this line of research, the current authors developed an FPT algorithm for Graph Iso-
morphism parameterized by treewidth [
LPPS17
]. This result has been subsequently improved
and simplified [
GNSW20
], as well as used to give a slice-wise logspace algorithm [
ES17
]. In 2015,
Kawarabayashi [
Kaw15
] announced an FPT algorithm for Graph Isomorphism parameterized
by the Euler genus of the input graph, with a linear dependency of the running time on the input
size. Very recently, Neuen [
Neu21
] proposed a different and simpler algorithm for this case, which
runs in time 2
O(g4log g)·nc
, for some constant
c
. The recent survey [
GN20
] mentions obtaining FPT
algorithms with parameterizations by the size of an excluded minor, maximum degree, and the size
of an excluded topological minor as important open problems. (Note that the last parameter, the
size of an excluded topological minor, generalizes the other two.)
Our contribution.
In this work we essentially solve the first of these open problems by proving
the following statement.
1
In order to avoid an avalanche of definitions in the introduction, we give formal definitions for the concepts used
in the paper in Section 3
1
Theorem 1.1.
There exists an algorithm that given a graph
H
and an
H
-minor-free graph
G
,
works in time f(H)·nO(1) for some function fand outputs a canonical labeling of G.
Here, a canonical labeling of
G
is a labeling of the vertices of
G
with labels from [
|V
(
G
)
|
] =
{
1
,...,|V
(
G
)
|}
so that for any two isomorphic graphs
G
and
G0
, the mapping matching vertices
with equal labels in
G
and
G0
is an isomorphism between
G
and
G0
. Thus, our algorithm solves the
more general Canonization problems, while Graph Isomorphism can be solved by computing
the canonical labelings for both input graphs and comparing the obtained labeled graphs.
The caveat in Theorem 1.1 is that we are not able to guarantee that
f
is computable. This
makes the algorithm formally fall outside of the usual definitions of fixed-parameter tractability (see
e.g. [
CFK+15
]), but we still allow ourselves to call it an FPT algorithm for Graph Isomorphism
and Canonization parameterized by the size of an excluded minor. We stress that we obtain a
single algorithm that takes Hon input, and not a different algorithm for every fixed H.
We now describe the ideas standing behind the proof of Theorem 1.1. First, we need to take
a closer look at the FPT algorithm for Graph Isomorphism and Canonization for graphs of
bounded treewidth [
LPPS17
,
GNSW20
]. There, the goal is to obtain an isomorphism-invariant tree
decomposition of the input graph of width bounded in parameter; then, to test isomorphism of two
graphs it suffices to test isomorphism of such decompositions. Unfortunately, it is actually impossible
to find one such isomorphism-invariant tree decomposition of the input graph; for instance, in a
long cycle one needs to arbitrarily break symmetry at some moment. However, up to technical
details, it suffices and is possible to find a small isomorphism-invariant family of tree decompositions.
To achieve this goal, the algorithm of [
LPPS17
] heavily relies on the existing understanding of
parameterized algorithms for approximating the treewidth of a graph.
The initial idea behind our approach is to borrow more tools from the literature on parameterized
graph separation problems, in particular from the work on the technique of recursive understand-
ing [
KT11
,
CCH+16
,
CLP+19
,
CKL+21
]. This work culminated in the following decomposition
theorem for graphs, proved by a superset of authors.
Theorem 1.2
([
CKL+21
])
.
Given a graph
G
and an integer
k
, one can in time 2
O(klog k)nO(1)
compute a tree decomposition of
G
where every adhesion is of size at most
k
and for every bag
S
the following holds: for every separation (
A, B
)in
G
of order at most
k
, either
|A∩S|6|A∩B|
or |B∩S|6|A∩B|.
The last property of Theorem 1.2 says that a bag
S
of the tree decomposition cannot be broken
by a separation of order at most
k
into two parts that both contain a large portion of
S
. This
property is often called unbreakability. More formally, let us recall the notion of a (
q, k
)-unbreakable
set introduced in [
CCH+16
,
CLP+19
]. Given a graph
G
and integers
q>k>
0, we say that a
set
S⊆V
(
G
) is (
q, k
)-unbreakable if for every separation (
A, B
) in
G
of order at most
k
, we have
|A∩S|6q
or
|B∩S|6q
. Theorem 1.2 of [
CKL+21
] can be seen as a simpler and cleaner version
of an analogous result of [
CLP+19
], where the bags are only guaranteed to be (
q, k
)-unbreakable
for some
q
bounded exponentially in
k
, and adhesion sizes are also bounded only exponentially in
k
.
Theorem 1.2 and its predecessor from [
CLP+19
] have been used to design parameterized
algorithms for several graph separation problems [CLP+19,CKL+21], most notably for Minimum
Bisection. In most cases, when looking for a deletion set of size at most
k
, one performs dynamic
programming on the tree decomposition provided by Theorem 1.2, where every step handling a single
bag can be solved using color-coding thanks to the unbreakability of the bag. More recent applications
include a parameterized approximation scheme for Min k-Cut [LSS20], as well as algorithms and
data structures for problems definable in first-order logic with connectivity predicates [PSS+21].
In this paper we propose to use the ideas behind the tree decomposition of Theorem 1.2 in the
context of Graph Isomorphism and Canonization in order to provide a reduction to the case
2
when the input graph is suitably unbreakable. The next statement is a wishful-thinking theorem that
in some variant we were able to prove, but in the end the result turned out to be too cumbersome to
use. In essence, it says the following: in FPT time one can compute a tree decomposition with the
same qualitative properties as the one provided by Theorem 1.2, but in an isomorphism-invariant way.
“Wishful-thinking Statement” 1.3.
There is a computable function
f
and an algorithm that,
given a graph
G
and an integer
k
, in time
f
(
k
)
nO(1)
computes an isomorphism-invariant tree
decomposition of Gsuch that
•the sizes of adhesions are bounded by f(k); and
•every bag is either of size at most f(k)or is (f(k), k)-unbreakable.
Instead of proving and using (a formal and correct version of) “Theorem” 1.3, we resort to the
strategy used in the earlier works, namely recursive understanding. Here, in some sense we compute
a variant of the tree decomposition of “Theorem” 1.3 on the fly, shrinking the already processed part
of the graph into constant-size representatives. Importantly, the run of this process is isomorphism
invariant. An overview of this approach is provided in Section 2, while the full statement and its
proof are in Section 4and Section 5.
At first glance, “Theorem” 1.3 may seem unrelated to the setting of graphs excluding a fixed
minor. However, let us recall one of the main results of the Graph Minor Theory, namely the
Structure Theorem for graphs excluding a fixed minor, proved by Robertson and Seymour in [
RS03
].
Informally speaking, this statement says that if a graph
G
excludes a fixed graph
H
as a minor,
then
G
admits a tree decomposition (called henceforth the RS-decomposition) in which the sizes of
adhesions are bounded in terms of
H
and the torso of every bag is nearly embeddable in a surface of
Euler genus bounded in terms of
H
. Without going into the precise definition of “nearly”, let us make
the following observation: if we are given an
H
-minor-free graph
G
and we apply to
G
the algorithm
of Theorem 1.2 with
k
equal to the expected bound on adhesion sizes in an RS-decomposition,
then the resulting tree decomposition should roughly resemble the RS-decomposition. In particular,
one may expect that the “large” bags of the decomposition of Theorem 1.2 should also be nearly
embeddable in some sense, as (due to unbreakability) they cannot be partitioned much finer in an
RS-decomposition whose adhesions are of size at most k.
For the Graph Isomorphism and Canonization problems, the main issue now is that the
output of Theorem 1.2 is not necessarily isomorphism-invariant; this is where the wishful-thinking
“Theorem” 1.3 comes into play. In particular, one could expect that the “large” bags of the decom-
position of “Theorem” 1.3 would be nearly embeddable in some sense. We are able to carry this
intuition through the recursive understanding point of view, and show the following.
Theorem 1.4
(simplified variant of Theorem 4.3)
.
For every graph
H
there exists a function
qH:N→N
such that the following holds. Suppose there exists an integer
k
and a canonization
algorithm
A
that works on all graphs that are
H
-minor-free and (
qH
(
i
)
, i
)-unbreakable for all
i6k
.
Then there is also a canonization algorithm
B
for all
H
-minor-free graphs. Furthermore,
B
can be
chosen to run in time upper bounded by
g
(
H
)
·nO(1)
plus the total time taken by at most
g
(
H
)
·nO(1)
invocations of Aon H-minor-free graphs with no more than nvertices, where gis some function.
The proof of Theorem 1.4 is sketched in Section 2. The full version — Theorem 4.3 — is proved
in Sections 4and 5. In essence, the full version differs from the one above in that it is uniform in
H
: if there is a single algorithm
A
that works for all
H
, then there is one resulting algorithm
B
that works for all H.
With Theorem 1.4 understood, it suffices to “only” provide a Canonization algorithm working
on graphs that are
H
-minor-free and (
q
(
i
)
, i
)-unbreakable for all
i6k
. We comment here on the
3
摘要：

Fixed-parametertractabilityofGraphIsomorphismingraphswithanexcludedminorDanielLokshtanov*MarcinPilipczuk„MichalPilipczuk…SaketSaurabh§AbstractWeprovethatGraphIsomorphismandCanonizationingraphsexcludinga xedgraphHasaminorcanbesolvedbyanalgorithmworkingintimef(H)nO(1),wherefissomefunction.Inotherword...

展开>> 收起<<
Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor Daniel LokshtanovMarcin PilipczukMicha l PilipczukSaket Saurabh.pdf

共70页,预览5页

还剩页未读， 继续阅读

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

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：70 页 大小：1.26MB 格式：PDF 时间：2025-05-06

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 70
评分 收藏
分享
立即下载
客服
关注