Abstract
Maximum weight independent set (MWIS) admits a 1/kapproximation in inductively kindependent graphs [Karhan Akcoglu et al., 2002; Ye and Borodin, 2012] and a 1/(2k)approximation in kperfectly orientable graphs [Kammer and Tholey, 2014]. These are a parameterized class of graphs that generalize kdegenerate graphs, chordal graphs, and intersection graphs of various geometric shapes such as intervals, pseudodisks, and several others [Ye and Borodin, 2012; Kammer and Tholey, 2014]. We consider a generalization of MWIS to a submodular objective. Given a graph G = (V,E) and a nonnegative submodular function f: 2^V → ℝ_+, the goal is to approximately solve max_{S ∈ ℐ_G} f(S) where ℐ_G is the set of independent sets of G. We obtain an Ω(1/k)approximation for this problem in the two mentioned graph classes. The first approach is via the multilinear relaxation framework and a simple contention resolution scheme, and this results in a randomized algorithm with approximation ratio at least 1/e(k+1). This approach also yields parallel (or lowadaptivity) approximations.
Motivated by the goal of designing efficient and deterministic algorithms, we describe two other algorithms for inductively kindependent graphs that are inspired by work on streaming algorithms: a preemptive greedy algorithm and a primaldual algorithm. In addition to being simpler and faster, these algorithms, in the monotone submodular case, yield the first deterministic constant factor approximations for various special cases that have been previously considered such as intersection graphs of intervals, disks and pseudodisks.
BibTeX  Entry
@InProceedings{chekuri_et_al:LIPIcs.APPROX/RANDOM.2023.24,
author = {Chekuri, Chandra and Quanrud, Kent},
title = {{Independent Sets in Elimination Graphs with a Submodular Objective}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
pages = {24:124:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772969},
ISSN = {18688969},
year = {2023},
volume = {275},
editor = {Megow, Nicole and Smith, Adam},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18849},
URN = {urn:nbn:de:0030drops188490},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.24},
annote = {Keywords: elimination graphs, independent set, submodular maximization, primaldual}
}
Keywords: 

elimination graphs, independent set, submodular maximization, primaldual 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) 
Issue Date: 

2023 
Date of publication: 

04.09.2023 