Highly unbreakable graph with a xed excluded minor are almost rigid Daniel LokshtanovMarcin PilipczukMicha l PilipczukSaket Saurabh

2025-05-06 0 0 1.25MB 69 页 10玖币
侵权投诉
Highly unbreakable graph with a fixed excluded minor
are almost rigid
Daniel Lokshtanov∗Marcin Pilipczuk†Micha l Pilipczuk‡Saket Saurabh§
Abstract
A set
X⊆V
(
G
) in a graph
G
is (
q, k
)-unbreakable if every separation (
A, B
) of order at
most
k
in
G
satisfies
|A∩X|6q
or
|B∩X|6q
. In this paper, we prove the following result:
If a graph
G
excludes a fixed complete graph
Kh
as a minor and satisfies certain unbreakability
guarantees, then
G
is almost rigid in the folloring sense: the vertices of
G
can be partitioned in
an isomorphism-invariant way into a part inducing a graph of bounded treewidth and a part that
admits a small isomorphism-invariant family of labelings. This result is the key ingredient in the
fixed-parameter algorithm for Graph Isomorphism parameterized by the Hadwiger number
of the graph, which is presented in a companion paper.
∗
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.14629v1 [math.CO] 26 Oct 2022
Contents
1 Introduction 1
2 Overview of the proof 2
2.1 Graphsofboundedgenus ................................. 2
2.2 Thegeneralcase ...................................... 5
3 Preliminaries 7
3.1 3-connectedcomponents.................................. 7
3.2 Embeddingsandsurfaces ................................. 8
3.3 AdditivityofEulergenus ................................. 9
3.4 Face-width, face-vertex curves, nooses . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.5 Walls............................................. 11
3.6 Large face-width implies surface minor . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.7 Uniquenessofanembedding................................ 13
3.8 Radialballs......................................... 14
3.9 Locally bounded treewidth of embedded graphs . . . . . . . . . . . . . . . . . . . . . 14
3.10Unbreakabilitytangle.................................... 15
3.11Miscellaneous........................................ 15
4 Near-embeddings 15
4.1 Basic definitions and notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2 Projecting a subgraph to G⊕and lifting a subgraph of G⊕............... 20
4.3 Preimages of parts of the surface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.4 Existence of a near-embedding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5 Optimal near-embeddings 23
6 Canonizing dongles 27
7 Large grids 37
8 Radial discs 41
9 Universal apices 45
10 Proximity of attachment points 50
11 Wrap-up 59
A Proof of an explicit bound for statement (3.5) of [RS88]64
B Computability of optimal near-embeddings (proof sketch of Lemma 11.1)66
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].
We focus on the Graph Isomorphism problem restricted to graphs with a fixed excluded minor.
Recall that a graph
H
is a minor of a graph
G
if
H
can be obtained from a subgraph of
G
by a
series of edge contractions. Ponomarenko [
Pon91
] showed that when restricted to
H
-minor-free
graphs, the Graph Isomorphism problem can be solved in time
O
(
npH
) where
n
is the size of the
input and pHis a constant depending on Honly.
This work is a part of a two-paper series that proves that Graph Isomorphism is fixed-parameter
tractable when parameterized by the excluded minor
H
; that is, it can be solved on
n
-vertex graphs
in time bounded by
pH·nc
where
pH
depends on
H
only and the constant
c
is a universal constant
(independent of
H
). The main paper [
LPPS22
] provides an algorithmic framework for the Graph
Isomorphism problem relying on the notion of unbreakability and decomposition into highly un-
breakable parts. This paper, subordinate to the main one, provides the crucial ingredient coming
from the graph minors theory. We refer to the introduction of [
LPPS22
] for an extended discussion
of the background of our main result.
To state the main result of this paper, we need a few definitions. For two graphs
G1, G2
, an iso-
morphism is a bijection
π
:
V
(
G1
)
→V
(
G2
) such that
uv ∈E
(
G1
) if and only if
π
(
u
)
π
(
v
)
∈E
(
G2
).
Let
G
be an undirected simple graph. A pair (
A, B
) is a separation if
A, B ⊆V
(
G
),
A∪B
=
V
(
G
),
and there is no edge of
G
with one endpoint in
A\B
and the second endpoint in
B\A
. The order
of the separation (
A, B
) is
|A∩B|
. For integers
q, k >
0, a set
X⊆V
(
G
) is (
q, k
)-unbreakable if
for every separation (
A, B
) of order at most
k
, we have
|A∩X|6q
or
|B∩X|6q
. In other words,
separations of order at most
k
are not able to split
X
into two parts larger than
q
. A graph
G
is
(q, k)-unbreakable if V(G) is (q, k)-unbreakable.
In this work we consider
H
-minor-free graphs with very high unbreakability properties. As
we will show, such graphs are close to being embeddable in a fixed surface: they are so-called
nearly-embeddable graphs. Furthermore, we show that if one properly defines a “quality measure”
of a near-embedding, the space of optimal (under this measure) near-embeddings of such graphs is
very constrained: all near-embeddings are essentially the same and only differ in some local details.
Let us proceed to formal definitions.
We need to make assumptions stronger than simply (
q, k
)-unbreakability for some fixed
q, k
.
In essence, we require a whole sequence of unbreakability assertions, as explained formally in the
following definition.
Definition 1.1
(unbreakability chain)
.
Let
G
be a graph and
f:N→N
be a nondecreasing function
with
f
(
x
)
> x
for every
x∈N
. An unbreakability chain of
G
with length
ζ
and step
f
is any
sequence ((qi, ki))ζ
i=0 of pairs of integers satisfying the following:
•Gis (qi, ki)-unbreakable, for each 0 6i6ζ; and
•ki=f(qi−1+ki−1), for each 1 6i6ζ.
We shall often say that such a chain starts at k0.
We are now ready to state the main result, whose proof spans the rest of the paper.
Theorem 1.2.
There exist constants
ctime
,
cgenus
, computable functions
ftw
,
fstep
,
fchain
,
ftime
,
fcut
,
fgenus
(with
fstep :N→N
being nondecreasing and satisfying
fstep
(
x
)
> x
for every
x∈N
), and
an algorithm that, given a graph
H
and an
H
-minor-free graph
G
together with ((
qi, ki
))
ζ
i=0
being
an unbreakability chain of
G
of length
ζ:
=
fchain
(
H
)with step
fstep
starting at
k0:
=
fcut
(
H
), works
1
in time bounded by
ftime
(
H, Pζ
i=0 qi
)
· |V
(
G
)
|ctime
and computes a partition
V
(
G
) =
Vtw ]Vgenus
and
a family Fgenus of bijections Vgenus 7→ [|Vgenus|]such that
1. the partition V(G) = Vtw ]Vgenus is isomorphism-invariant;
2. G[Vtw]has treewidth bounded by ftw(H, Pζ
i=0 qi);
3. |Fgenus|6fgenus(H, Pζ
i=0 qi)· |V(G)|cgenus ; and
4. Fgenus is isomorphism-invariant.
Here, isomorphism-invariant output means that for every
H
and for every two
H
-minor-free
graphs
G1
and
G2
and every isomorphism
π
between them, the output of the algorithm invoked
on
H
,
G1
(and some unbreakability chain) and the output of the algorithm invoked on
H
,
G2
(and
the same unbreakability chain) are isomorphic and, furthermore, the isomorphism
π
extends to the
isomorphism of the outputs.
Intuitively, the
Vgenus
part corresponds to the main skeleton of the whole graph, which is em-
bedded in the same way in every optimal near-embedding. On the other hand,
Vtw
consists of parts
of bounded size that “dangle” from the skeleton; an optimal near-embedding may take some local
decisions about how to exactly represent them.
We provide an introduction to the proof in Section 2. Here, we mainly sketch the proof of
an analog of Theorem 1.2 for classes of graphs embeddable in a fixed surface. This proof already
highlights main ideas behind the proof of the general case, while being technically less challenging.
After preliminaries in Section 3, we continue with the full proof of Theorem 1.2 in subsequent sections.
2 Overview of the proof
In this section we provide an intuitive overview of the proof of Theorem 1.2.
To simplify the exposition, we first focus on proving Theorem 1.2 under a stronger assumption
that
G
actually has bounded genus. This case already allows us to show most of the key concep-
tual steps used in the argument for the general case of unbreakable
H
-minor-free graphs. Then,
we briefly discuss traps, issues, and caveats that arise when working in the general setting with
near-embeddings rather than embeddings.
2.1 Graphs of bounded genus
In this section we sketch how to prove the following statement, which is weaker variant of Theorem 1.2
tailored to the bounded genus case.
Theorem 2.1.
There exist computable functions
fcut, ftw, ftime
and an algorithm
A
with the fol-
lowing specification. The algorithm
A
is given as input a graph
G
and integers
g
and
q
with a
promise that
G
is of Euler genus at most
g
and is (
q, k
)-unbreakable for
k
=
fcut
(
g
). Then
A
runs
in time bounded by
ftime
(
g, q
)
·nO(1)
and computes an isomorphism-invariant partition of
V
(
G
)into
Vtw ]Vgenus
and a nonempty isomorphism-invariant family
Fgenus
of size
O
(
|E
(
G
)
|
)of bijections
Vgenus 7→ [|Vgenus|]such that G[Vtw]is of treewidth at most ftw(g)·q.
Without loss of generality assume that
q>k>
2. If
G
is of treewidth
O
(
q
), then we can return
Vgenus =∅. Hence, we assume that the treewidth of Gis much larger than q.
2
Consider Tutte’s decomposition of
G
into 3-connected components
1
. Since
G
is (
q, k
)-unbreakable
and has treewidth much larger than
q
, it follows that there is a unique 3-connected component of
G
that has more than
q
vertices and treewidth much larger than
q
, while all the other 3-connected
components are of size at most
q
. The same conclusion holds for the graph
G−X
for any set
X⊆V
(
G
) of size at most
k−
2: If (
A, B
) is a separation of order at most 2 in
G−X
, then
(
A∪X, B ∪X
) is a separation of order at most
k
in
G
and, hence, either
|A\B|6q
or
|B\A|6q
.
For any set
X⊆V
(
G
) of size at most
k−
2, by
GX
we denote the unique 3-connected component
of
G−X
that has more than
q
vertices. Note that the treewidth assumption implies that the
treewidth of GXis in fact much larger than q.
Our goal is to define
Vgenus
so that
G
[
Vgenus
] is almost rigid — admits only few automorphisms
— and this rigidity will be derived from the rigidity of embedded graphs. Observe that if Π is an
embedding of a connected graph
G
in some surface, then an automorphism of (
G,
Π) is fixed by
fixing only the image of one edge with distinguished endpoint and an indication which side of the
edge is “left” and which is “right”. This gives at most 4|E(G)|automorphisms.
Unfortunately, a graph can have many different embeddings in a surface of Euler genus
g
, even
assuming it is 3-connected. However, the number of different embeddings drops if the embeddings
have large face-width (the minimum number of vertices on a noncontractible face-vertex noose, i.e.,
a closed curve without self-intersections):
Theorem 2.2
([
ST96
])
.
There is a function
fue
(
g
)
∈ O
(
log g/ log log g
)such that if
G
is a 3-
connected graph and Πis an embedding of
G
of Euler genus
g
and face-width at least
fue
(
g
), then
gis equal to the (minimum) Euler genus of Gand Πis the unique embedding of Euler genus g.
The first idea would be to apply Theorem 2.2 to
G∅
— the unique large 3-connected component
of
G
. That is, consider an embedding Π of
G∅
of minimum possible Euler genus. If the face-width
of this embedding is at least
fue
(
g
), then we may simply set
Vgenus
=
V
(
G∅
). Then Π is the unique
embedding of
G
[
Vgenus
] of minimum Euler genus, which gives rise to an isomorphism-invariant family
of at most 4
|E
(
G
)
|
automorphisms of
G
, from which a suitable family
Fgenus
can be easily derived.
Note that by (
q, k
)-unbreakability, every connected component of
G
[
Vtw
] =
G−Vgenus
has at most
qvertices, hence in particular G[Vtw] has treewidth at most q.
However, it may happen that Π has face-width smaller than
fue
(
g
) and Theorem 2.2 cannot be
applied. But then there is a set
X1⊆V
(
G∅
) of size at most
fue
(
g
) such that
G∅−X1
has strictly
smaller Euler genus than G∅. This implies that GX1has strictly smaller Euler genus than G∅.
We can iterate this process: if we take any minimum Euler genus embedding Π
1
of
GX1
and
it turns out that Π
1
has small face-width, there is a set
X2
of small cardinality such that
GX1∪X2
has strictly smaller Euler genus. It will be useful later to allow subsequent steps in this process
to ask for larger and larger face-width (and thus allowing larger cut sets
X2, X3, . . .
). Note that
the number of steps is bounded by the Euler genus of G.
More formally, let us define a function
κ:{
0
,
1
, . . . , g, g
+ 1
} → N
by setting
κ
(0) = 0 and
κ
(
γ
+ 1) =
pκ
(
κ
(
γ
)) for a polynomial
pκ
(
x
) =
x
+
fue
(
g
) +
c·
(
x
+
g
+ 1)
4
, where
c
is a sufficiently
large constant. We set k=fcut(g) = κ(g+ 1) :=pκ(κ(g)) ∈22O(g).
Let 0
6γ6g
. A set
X⊆V
(
G
) is a potential deletion set for
γ
if
|X|6κ
(
γ
) and the Euler
genus of
GX
is at most
g−γ
. Let 0
6γ06g
be the maximum integer such that there exists a
potential deletion set for
γ0
; note that
γ0
exists as
X
=
∅
is a potential deletion set for
γ
= 0. Let
κ06κ
(
γ0
) be the minimum size of a potential deletion set for
γ0
. A potential deletion set for
γ0
of size κ0shall be called a deletion set.
1
The 3-connected components of a graph are the torsos of the bags of its Tutte’s decomposition. See Section 3.1
for a discussion.
3
摘要：

Highlyunbreakablegraphwitha xedexcludedminorarealmostrigidDanielLokshtanov*MarcinPilipczuk„MichalPilipczuk…SaketSaurabh§AbstractAsetXV(G)inagraphGis(q;k)-unbreakableifeveryseparation(A;B)oforderatmostkinGsatis esjA\Xj6qorjB\Xj6q.Inthispaper,weprovethefollowingresult:IfagraphGexcludesa xedcompletegr...

展开>> 收起<<
Highly unbreakable graph with a xed excluded minor are almost rigid Daniel LokshtanovMarcin PilipczukMicha l PilipczukSaket Saurabh.pdf

共69页,预览5页

还剩页未读， 继续阅读

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

相关推荐

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

开通VIP享超值会员特权

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

作者详情

相关内容

更多

热门标签

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