Computing at Glasgow University
Paper ID: 6525
DCS Tech Report Number: TR-1997-33

On the 2-maximal independence number of a graph

Publication Type: Tech Report (internal)
Appeared in: DCS Tech Report
Page Numbers :
Publisher: Dept of Computing Science, University of Glasgow
Year: 1997

An independent set S of a graph G=(V,E) is k-maximal (k>=1) if, for all subsets A of S (where |A|<=k-1), and all subsets B of V\S (where |B|=|A|+1), (S\A)\cup B is non-independent. Halldórsson (Approximating discrete collections via local improvements, in Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, pages 160-169. ACM-SIAM, 1995) uses k-maximal independent sets as a means of approximating maximum independent sets in certain graph classes. Here we study the parameter \beta_{0,2}^-(T), the smallest order of a 2-maximal independent set of a graph G, from an algorithmic point of view. We obtain a linear time and space algorithm for computing \beta_{0,2}^-(T) for a tree T and also for constructing a minimum 2-maximal independent set of T. We also show that the decision problem related to computing \beta_{0,2}^-(T) is NP-complete for planar graphs of maximum degree three.

Bibtex entry Endnote XML