  Maximum weight independent set (MWIS) admits a $\frac1k$-approximation in
inductively $k$-independent graphs and a $\frac{1}{2k}$-approximation in
$k$-perfectly orientable graphs. These are a a parameterized class of graphs
that generalize $k$-degenerate graphs, chordal graphs, and intersection graphs
of various geometric shapes such as intervals, pseudo-disks, and several
others. We consider a generalization of MWIS to a submodular objective. Given a
graph $G=(V,E)$ and a non-negative submodular function $f: 2^V \rightarrow
\mathbb{R}_+$, the goal is to approximately solve $\max_{S \in \mathcal{I}_G}
f(S)$ where $\mathcal{I}_G$ is the set of independent sets of $G$. We obtain an
$\Omega(\frac1k)$-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 $\frac{1}{e(k+1)}$. This approach also yields
parallel (or low-adaptivity) approximations. Motivated by the goal of designing
efficient and deterministic algorithms, we describe two other algorithms for
inductively $k$-independent graphs that are inspired by work on streaming
algorithms: a preemptive greedy algorithm and a primal-dual 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 pseudo-disks.
