A Note on Robust Subsets of Transversal Matroids Naoyuki Kamiyama Institute of Mathematics for Industry Kyushu University Fukuoka Japan.

2025-04-30 0 0 331.15KB 7 页 10玖币

侵权投诉

A Note on Robust Subsets of Transversal Matroids

Naoyuki Kamiyama∗

Institute of Mathematics for Industry, Kyushu University, Fukuoka, Japan.

kamiyama@imi.kyushu-u.ac.jp

Abstract

Robust subsets of matroids were introduced by Huang and Sellier to propose approximate

kernels for the matroid-constrained maximum vertex cover problem. In this paper, we prove

that the bound for robust subsets of transversal matroids given by Huang and Sellier can

be improved.

1 Introduction

Robust subsets of matroids were introduced by Huang and Sellier [1] to propose approximate

kernels for the matroid-constrained maximum vertex cover problem (see Section 2 for the formal

deﬁnition of a robust subset of a matroid). By using this concept, Huang and Sellier [1] extended

the approach proposed by Manurangsi [2] for uniform matroids to partition matroids, laminar

matroids, and transversal matroids.

In this paper, we especially focus on robust subsets of transversal matroids. We prove that

the bound for robust subsets of transversal matroid given by Huang and Sellier [1] can be

improved (see Section 2 for the formal description of our result).

2 Preliminaries

Throughout this paper, let Z+denote the set of non-negative integers. For each positive integer

z, we deﬁne [z] := {1,2, . . . , z}. In addition, we deﬁne [0] := ∅. For each ﬁnite set Xand each

element x, we deﬁne X+x:= X∪ {x}and X−x:= X\ {x}. Furthermore, for each ﬁnite set

X, each function ρ:X→Z+, and each subset Y⊆X, we deﬁne ρ(Y) := Px∈Yρ(x).

In this paper, we assume that every undirected graph is ﬁnite and simple. Thus, every edge

of an undirected graph Gcan be regraded as a set consisting of two distinct vertices of G. Let

G= (U, V ;E) denote an undirected bipartite graph where the vertex set of Gis partitioned

into Uand V,Eis the edge set of G, and each edge of Econsists of one vertex in Uand one

vertex in V. For every undirected bipartite graph G= (U, V ;E) and every edge {u, v} ∈ E, we

assume that u∈Uand v∈V. For each undirected bipartite graph G= (U, V ;E), we call a

subset M⊆Eamatching in Gif e∩f=∅for every pair of distinct edges e, f ∈M. For each

undirected bipartite graph G= (U, V ;E) and each subset F⊆E, we deﬁne ∂(F) as the set of

vertices v∈U∪Vsuch that there exists an edge e∈Fsatisfying the condition that v∈e.

An ordered pair M= (U, I) of a ﬁnite set Uand a non-empty family Iof subsets of Uis

called a matroid if, for every pair of subsets I, J ⊆U, the following conditions are satisﬁed.

(I1) If I⊆Jand J∈ I, then I∈ I.

∗This work was supported by JSPS KAKENHI Grant Number JP20K11680.

arXiv:2210.09534v1 [math.CO] 18 Oct 2022

(I2) If I, J ∈ I and |I|<|J|, then there exists an element u∈J\Isuch that I+u∈ I.

Let M= (U, I) be a matroid. Deﬁne rk(M) := maxI∈I |I|. We call an element B∈ I abase

of Mif |B|= rk(M). For each positive integer `, we deﬁne the ordered pair M`= (U, I`) as

follows. Deﬁne I`as the family of subsets I⊆Usuch that there exist pairwise disjoint subsets

I1, I2, . . . , I`⊆Isatisfying the following conditions.

(U1) I1∪I2∪ · · · ∪ I`=I.

(U2) For every integer i∈[`], we have Ii∈ I.

It is known that the ordered pair M`is a matroid (see, e.g., [3, Section 11.3]). For each function

ω:U→Z+, we call a base of Man optimal base of Mwith respect to ωif ω(B)≥ω(B0) holds

for every base B0of M.

In this paper, we especially focus on transversal matroids. Let G= (U, V ;E) be an undi-

rected bipartite graph. Then we deﬁne the matroid MG= (U, IG) as follows. Deﬁne IGas the

family of subsets I⊆Usuch that there exists a matching Min Gsatisfying the condition that

I=∂(M)∩U. It is known that MGdeﬁned in this way is a matroid. This kind of matroid is

called a transversal matroid (see, e.g., [3, Section 1.6]).

For each matroid M= (U, I), each function ω:U→Z+, and each positive integer k, we

call a subset X⊆Uak-robust subset of Mwith respect to ωif, for every base Bof M, there

exist pairwise disjoint subsets X1, X2, . . . , X|B\X|⊆X\Band a bijection φ:B\X→[|B\X|]

satisfying the following conditions.

(R1) For every integer i∈[|B\X|], we have |Xi|=k.

(R2) For every element u∈B\Xand every element v∈Xφ(u), we have ω(u)≤ω(v).

(R3) For every element (u1, u2, . . . , u|B\X|)∈X1×X2× · · · × X|B\X|, we have

(B∩X)∪ {u1, u2, . . . , u|B\X|}∈I.

Then for each matroid M= (U, I), each function ω:U→Z+, and each positive integer k, we

deﬁne τ(M, ω, k) as the minimum positive integer `such that every optimal base of M`with

respect to ωis a k-robust subset of Mwith respect to ω. (See also Section 5 for remarks on the

deﬁnition of τ(M, ω, k).)

Huang and Sellier [1] proved that, for every undirected bipartite graph G= (U, V ;E), every

function ω:U→Z+, and every positive integer k, we have

τ(MG, ω, k)≤k+ rk(MG)−1.

In this paper, we prove the following theorem. We prove Theorem 1 in Section 4.

Theorem 1. For every undirected bipartite graph G= (U, V ;E), every function ω:U→Z+,

and every positive integer k, we have

τ(MG, ω, k)≤k.

3 Auxiliary Bipartite Graphs

Throughout this section, let G= (U, V ;E) be an undirected bipartite graph. Furthermore, we

are given a function ω:U→Z+and a positive integer k.

We deﬁne the undirected bipartite graph Gk= (U, V k;Ek) as follows. For each vertex v∈V

and each integer t∈[k], we prepare a new vertex v(t). Then we deﬁne Vk:= {v(t)|v∈V, t ∈

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

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

10 玖币 0人已下载

立即下载

摘要：

ANoteonRobustSubsetsofTransversalMatroidsNaoyukiKamiyama*InstituteofMathematicsforIndustry,KyushuUniversity,Fukuoka,Japan.kamiyama@imi.kyushu-u.ac.jpAbstractRobustsubsetsofmatroidswereintroducedbyHuangandSelliertoproposeapproximatekernelsforthematroid-constrainedmaximumvertexcoverproblem.Inthispaper...

展开>> 收起<<

A Note on Robust Subsets of Transversal Matroids Naoyuki Kamiyama Institute of Mathematics for Industry Kyushu University Fukuoka Japan..pdf

共7页,预览2页

还剩页未读，继续阅读

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

A Note on Robust Subsets of Transversal Matroids Naoyuki Kamiyama Institute of Mathematics for Industry Kyushu University Fukuoka Japan.

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: