Inductive graph invariants and approximation algorithms

We introduce and study an inductively defined analogue [Formula: see text] of any increasing graph invariant [Formula: see text]. An invariant [Formula: see text] is increasing if [Formula: see text] whenever [Formula: see text] is an induced subgraph of [Formula: see text]. This inductive analogue simultaneously generalizes and unifies known notions like degeneracy, inductive independence number, etc., into a single generic notion. For any given increasing [Formula: see text], this gets us several new invariants and many of which are also increasing. It is also shown that [Formula: see text] is the minimum (over all orderings) of a value associated with each ordering. We also explore the possibility of computing [Formula: see text] (and a corresponding optimal vertex ordering) and identify some pairs [Formula: see text] for which [Formula: see text] can be computed efficiently for members of [Formula: see text]. In particular, it includes graphs of bounded [Formula: see text] values. Some specific examples (like the class of chordal graphs) have already been studied extensively. We further extend this new notion by (i) allowing vertex weighted graphs, (ii) allowing [Formula: see text] to take values from a totally ordered universe with a minimum and (iii) allowing the consideration of [Formula: see text]-neighborhoods for arbitrary but fixed [Formula: see text]. Such a generalization is employed in designing efficient approximations of some graph optimization problems. Precisely, we obtain efficient algorithms (by generalizing the known algorithm of Ye and Borodin [Y. Ye and A. Borodin, Elimination graphs, ACM Trans. Algorithms  8(2) (2012) 1–23] for special cases) for approximating optimal weighted induced [Formula: see text]-subgraphs and optimal [Formula: see text]-colorings (for hereditary [Formula: see text]’s) within multiplicative factors of (essentially) [Formula: see text] and [Formula: see text] respectively, where [Formula: see text] denotes the inductive analogue (as defined in this work) of optimal size of an unweighted induced [Formula: see text]-subgraph of the input and [Formula: see text] is the minimum size of a forbidden induced subgraph of [Formula: see text]. Our results generalize the previous result on efficiently approximating maximum independent sets and minimum colorings on graphs of bounded inductive independence number to optimal [Formula: see text]-subgraphs and [Formula: see text]-colorings for arbitrary hereditary classes [Formula: see text]. As a corollary, it is also shown that any maximal [Formula: see text]-subgraph approximates an optimal solution within a factor of [Formula: see text] for unweighted graphs, where [Formula: see text] is maximum size of any induced [Formula: see text]-subgraph in any local neighborhood [Formula: see text].