Locally Defined Independence Systems on Graphs

概要

Locally Defined Independence Systems
on Graphs
Yuki Amano

The maximization for independence system is one of the most fundamental combinatorial optimization problems [4, 16, 17]. An independence system is a pair (E, I) of a finite set E and a
family I ⊆ 2E that satisfies
I contains empty set, i.e., ∅ ∈ I, and
J ∈ I implies I ∈ I for any I ⊆ J ⊆ E.

(1)
(2)

Here a member I in I is called an independent set. Property (2) means that I is downward closed.
The maximization problem for an independence system is to find an independent set with the
maximum cardinality. This problem includes, as a special case, the maximum independent set of a
graph, the maximum matching, the maximum set packing and the matroid (intersection) problems
[14, 16, 17].
In the paper, we consider the following independence systems defined on graphs. Let G = (V, E)
be a graph with a vertex set V and an edge set E. For a vertex v in V , let Ev denote the set
of edges incident to v. In our problem setting, each vertex v has a local independence system
(Ev , Iv ), i.e., Iv ⊆ 2Ev , and we consider the independence system (E, I) defined by
I = {I ⊆ E | I ∩ Ev ∈ Iv for all v ∈ V }.

(3)

Namely, (E, I) is obtained by concatenating local independence systems (Ev , Iv ), and is called an
independence system defined on a graph G. In the paper, we consider the maximization problem
for it, i.e., for a given graph G = (V, E) with local independence systems (Ev , Iv ), our problem is
described as
maximize |I|
subject to I ∩ Ev ∈ Iv for all v ∈ V
I ⊆ E.

(4)

Note that any independence system (E, I) is viewed as an independence system defined on a star.
In the paper, we consider problem (4) by making use of local oracles Av for each v in V . For
an independence system (E, I) and a subset F ⊆ E, I[F ] denotes the family of independent sets
of I restricted to F , i.e., I[F ] = {I ∩ F | I ∈ I}. For a vertex v ∈ V and a subset F ⊆ Ev ,
Av (F ) is an α-approximate independent set of the maximization for (F, Iv [F ]). That is, the oracle
Av : 2Ev → 2Ev satisfies
Av (F ) ∈ Iv [F ]
α |Av (F )| ≥ max |J|.
J∈Iv [F ]

1

(5)
(6)

We call Av an α-approximation local oracle. It is also called an exact local oracle if α = 1.
In the paper, we assume the monotonicity of Av , i.e., |Av (S)| ≤ |Av (T )| holds for the subsets
S ⊆ T ⊆ Ev , which is a natural assumption on the oracle since it deals with independence system.
We study this oracle model to investigate the global approximability of problem (4) by using the
local approximability.
In the paper, we first propose two natural algorithms for problem (4), where the first one
applies local oracles Av in the order of the vertices v that is fixed in advance, while the second one
applies local oracles in the greedy order of vertices v1 , . . . , vn , where n = |V | and
vi ∈ arg max{|Av (Ev ∩ F (i) )| | v ∈ V \ {v1 , . . . , vi−1 }}

for i = 1, . . . , n.

Here the subset F (i) ⊆ E is a set of available edges during the i-th iteration.
We show that the first algorithm guarantees an approximation ratio (α + n − 2), and the second
algorithm guarantees an approximation ratio ρ(α, n), where ρ is the function of α and n defined
as

1
2α − 1


(n − 1) −
if (α − 1)(n − 1) ≥ α(α + 1)
α+



2α
2

α
ρ(α, n) = α +
(n − 1)
if α ≤ (α − 1)(n − 1) < α(α + 1)

α+1



n


if (α − 1)(n − 1) < α.
2
We also show that both of approximation ratios are almost tight for these algorithms.
We then consider two subclasses of problem (4). We provide two approximation algorithms
for the k-degenerate graphs, whose approximation ratios are α + 2k − 2 and αk. Here, a graph is
k-degenerate if any subgraph has a vertex of degree at most k. This implies for example that the
algorithms find an α-approximate independent set for the problem if a given graph is a tree. This
is best possible, because the local maximization is not approximable with c (< α). We also show
that the second algorithm can be generalized to the hypergraph setting.
We next provide an (α + k)-approximation algorithm for the problem when a given graph is
bipartite and local independence systems for one side are all k-systems with independence oracles.
Here an independence system (E, I) is called a k-system if for any subset F ⊆ E, any two maximal
independent sets I and J in I[F ] satisfy k|I| ≥ |J|, and its independence oracle is to decide if a
given subset J ⊆ E belongs to I or not.
All of statements and proofs can be found in the full version [1]. The full paper is organized
as follows. In Section 2, we describe two natural algorithms for problem (4) and analyze their
approximation ratios. Section 3 provides approximation algorithms for the problem in which a
given graph G has bounded degeneracy. Section 4 also provides an approximation algorithm for
the problem in which a given graph G is bipartite, and all the local independence systems of the
one side of vertices are k-systems. Section 5 defines independence systems defined on hypergraphs
and generalizes algorithms to the hypergraph case.

Acknowledgments
I give special gratitude to Kazuhisa Makino for his valuable discussions and carefully proofreading
of the manuscript. I am also grateful to Yusuke Kobayashi, Akitoshi Kawamura, and Satoru
Fujishige for constructive suggestions. This work was supported by the joint project of Kyoto
University and Toyota Motor Corporation, titled ”Advanced Mathematical Science for Mobility
Society”.
2

References
[1] Yuki Amano. Locally defined independence systems on graphs. Discrete Applied Mathematics,
326:1–16, 2023.
[2] Adi Avidor, Ido Berkovitch, and Uri Zwick. Improved approximation algorithms for max
nae-sat and max sat. Approximation and Online Algorithms, pages 27–40, 2005.
[3] Chandra Chekuri and Amit Kumar. Maximum coverage problem with group budget constraints and applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 72–83. Springer, 2004.
[4] W. Cook, W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, and A. Schrijver. Combinatorial
Optimization. A Wiley-Interscience publication. Wiley, 1997.
[5] Eugene C. Freuder. A sufficient condition for backtrack-free search. Journal of the ACM
(JACM), 29(1):24–32, 1982.
[6] Toshihiro Fujito. A 2/3-approximation of the matroid matching. In Algorithms and Computation: 4th International Symposium, ISAAC’93, Hong Kong, December 15-17, 1993. Proceedings, volume 762, page 185. Springer Science & Business Media, 1993.
[7] T.A. Jenkyns. Matchoids: a generalization of matchings and matroids. PhD thesis, University
of Waterloo, 1975.
[8] Vassilis Kostakos. Temporal graphs. Physica A: Statistical Mechanics and its Applications,
388(6):1007–1023, 2009.
[9] Jon Lee, Maxim Sviridenko, and Jan Vondr´ak. Matroid matching: the power of local search.
SIAM Journal on Computing, 42(1):357–379, 2013.
[10] Don R. Lick and Arthur T. White. k-degenerate graphs. Canadian Journal of Mathematics,
22(5):1082–1096, 1970.
[11] L´aszl´o Lov´asz. The matroid matching problem. Algebraic methods in graph theory, 2:495–517,
1978.
[12] Subhrangsu Mandal and Arobinda Gupta. 0-1 timed matching in bipartite temporal graphs.
In Conference on Algorithms and Discrete Applied Mathematics, pages 331–346. Springer,
2020.
[13] David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring
algorithms. Journal of the ACM (JACM), 30(3):417–427, 1983.
[14] James G. Oxley. Matroid theory, volume 3. Oxford University Press, USA, 2006.
[15] Michael D Plummer and L´aszl´o Lov´asz. Matching theory. Elsevier Science Ltd., 1986.
[16] Alexander Schrijver et al. Combinatorial optimization: polyhedra and efficiency, volume 24.
Springer, 2003.
[17] D.J.A. Welsh and London Mathematical Society. Matroid Theory. L.M.S. monographs. Academic Press, 1976. ...