The maximum independent set problems and augmenting graphs
Let \(S\) be an independent set of \(G=(V,E)\). A bipartite graph \(H=(B,W,F)\) is augmenting for \(S\) if \(B \subseteq S\), \(W \subseteq V \setminus S\), \(F = E \cap \{bw \mid b \in B, w \in W\}\), \(N(W) \cap (S \setminus B) = \emptyset\) and \(| W| > | B| \). \(S\) is a maximum independent set of \(G\) if and only if there is no augmenting graph for \(S\). Every minimal augmenting graph \(H=(B,W,F)\) is connected and fulfils both \(| B| = | W| -1\) and \(| A| < | W \cap N(A)| \) for all \(A \subseteq B\). This chapter reviews polynomial time algorithms for the maximum independent set problem that generalise \textit{G. J. Minty's} algorithm on claw-free graphs [J.\ Comb.\ Theory, Ser.\ B 28, 284--304 (1980; Zbl 0434.05043)]. All these algorithms use the idea of augmenting graphs, and work for classes defined by a forbidden \(S_{i,j,k}\) (and somtimes other forbidden subgraphs), where \(S_{i,j,k}\) is the star with three rays of length \(i\), \(j\) and \(k\). \(S_{1,1,1}\) is also known as the claw. For the entire collection see [Zbl 1075.05002].
- Finding augmenting chains in extensions of claw-free graphs
- Extending the MAX algorithm for maximum independent set
- New sufficient conditions for \(\alpha\)-redundant vertices
- The maximum independent set problem in subclasses of subcubic graphs
- Combinatorics and algorithms for augmenting graphs
- Augmenting approach for some maximum set problems
- The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs
- A sufficient condition to extend polynomial results for the maximum independent set problem
- The max quasi-independent set Problem
- Augmenting graphs for independent sets
This page was built for publication: The maximum independent set problems and augmenting graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5717953)