IMSc Webinar

Inductive Graph Invariants and Algorithmic Applications

C R Subramanian

IMSc

Meeting link: https://meet.google.com/hxy-cvex-drr We introduce and study an inductively defined analogue f_{IND}() of any increasing graph invariant f(). An invariant f() is increasing if f(H) ≤ f(G) whenever H is an induced subgraph of G. This inductive analogue simultaneously generalizes and unifies known notions like degeneracy, inductive independence number, etc into a single generic notion. For any given increasing f(), this gets us several new invariants and many of which are also increasing. It is also shown that f_{IND}() is the minimum (over all orderings) of a value associated with each ordering. We further extend this new notion by (i) allowing vertex weighted graphs, (ii) allowing f () to take values from a totally ordered universe with a minimum and (iii) allowing the consideration of r-neighborhoods for arbitrary but fixed r ≥ 1. 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 for special cases) for approximating optimal weighted induced P-subgraphs and optimal P-colorings (for hereditary P’s) within multiplicative factors of (essentially) k and k/(m−1) respectively, where k denotes the inductive analogue (as defined in this work) of optimal size of an unweighted induced P-subgraph of the input and m is the minimum size of a forbidden induced subgraph of P. Our results generalize the previous result on efficiently approximating maximum independent sets and minimum colorings on graphs of bounded inductive independence number, to optimal P-subgraphs and P-colorings for arbitrary hereditary classes P. As a corollary, it is also shown that any maximal P-subgraph approximates an optimal solution within a factor of k+1 for unweighted graphs, where k is maximum size of any induced P-subgraph in any local neighborhood N_G(u). If time permits, we will also outline further generalisations to inductive (graph,vertex) invariants and also inductive invariants over abstract geodesic spaces.