in polynomial time. Thus, it is inter esting to find out when ν
k
(D) and ν
∗
k
(D) are “close” as, in
particular, for such instances this immediately yields an efficient approximation algorithm for this
NP-Hard problem. Indeed, a result of Nutov and Yuster [9] asserts that, for orientations, these two
parameters differ by at most o(n
2
), thus giving an approximation algorithm with an o(n
2
) additive
error term. In fact, their result is much more general. Let S be any given (finite or infinite) family
of orientations. For an orientation D, let ν
S
(D) denote the maximum number of arc-disjoint copies
of elements of S that can be found in D, and let ν
∗
S
(D) denote the respective fr actional relaxation.
The followin g is proved in [9]
Theorem 2.1 For any given family S of orientations, if D is an n-vertex orientation then ν
∗
S
(D)−
ν
S
(D) = o(n
2
). Furthermore, a set of at least ν
S
(D) − o(n
2
) arc-disjoint elements of S can be
generated in randomized polynomial time.
We note that an undirected version of Theorem 2.1 has been recently proved by Yuster [15] extending
an earlier result of Haxell and R¨odl [6] dealing with single element families. The proof of Theorem
2.1 makes u se of the directed ver sion of Szemer´edi’s regularity lemma [13] that has been used
implicitly in [3] and proved in [1].
By considering the single-element family S = {T T
k
} we obtain the following immediate corol-
laries of Theorem 2.1.
Corollary 2.2 Let k ≥ 3 be a fixed integer. If D is an n-vertex orientation then ν
∗
k
(D) − ν
k
(D) =
o(n
2
). Furthermore, a set of at least ν
k
(D)−o(n
2
) arc-disjoint copies of T T
k
in D can be generated
in randomized polynomial time.
Let ν
∗
k
(n) be the minimum possible value of ν
∗
k
(T ) ranging over all n-vertex tournaments T . Obvi-
ously, ν
∗
k
(n) ≥ ν
k
(n). Together with Corollary 2.2 we have:
Corollary 2.3 Let k ≥ 3 be a fixed integer. Then, ν
∗
k
(n) ≥ ν
k
(n) ≥ ν
∗
k
(n) − o(n
2
).
2.2 Gluing fractional solutions
The goal of th is s ubsection is to prove the following lemma.
Lemma 2.4 Let 2 < k < r < n be integers. Then,
ν
∗
k
(n) ≥
n(n − 1)
r(r − 1)
ν
∗
k
(r).
Proof: Clearly, the complete graph K
n
has pr ecisely
n
r
distinct copies of K
r
(not necessarily
edge-disjoint). Also, for any edge (u, v) of K
n
, we can select any set of r − 2 vertices, other th an
u, v and obtain a copy of K
r
containing (u, v). Thus, every edge of K
n
appears in precisely
n − 2
r − 2
4
剩余16页未读，继续阅读
zpc_rjy
- 粉丝: 0
- 资源: 6
我的内容管理
展开
最新资源
- Unity UGUI性能优化实战：UGUI_BatchDemo示例
- Java实现小游戏飞翔的小鸟教程分享
- Ant Design 4.16.8：企业级React组件库的最新更新
- Windows下MongoDB的安装教程与步骤
- 婚庆公司响应式网站模板源码下载
- 高端旅行推荐：官网模板及移动响应式网页设计
- Java基础教程：类与接口的实现与应用
- 高级版照片排版软件功能介绍与操作指南
- 精品黑色插画设计师作品展示网页模板
- 蓝色互联网科技企业Bootstrap网站模板下载
- MQTTFX 1.7.1版：Windows平台最强Mqtt客户端体验
- 黑色摄影主题响应式网站模板设计案例
- 扁平化风格商业旅游网站模板设计
- 绿色留学H5模板：科研教育机构官网解决方案
- Linux环境下EMQX安装全流程指导
- 可爱卡通儿童APP官网模板_复古绿色动画设计
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
