Generalized maximal independence parameters for trees

Abstract

An independent set I ⊆ V of a graph G = (V.E) is said to be k-maximal if there does not exist two sets X and Y' such that X ⊆ I. Y ⊆ (V - I). |X| < k and (I - X) ∪ Y is an independent set of cardinality larger than |I|. This definition generalizes the traditional concept of maximality of independent sets. -- The problem of finding the smallest k-maximal set for a given graph is NP-hard for many simple classes of graphs, such as the class of bipartite graphs. Here we investigate the MINIMUM k-MAXIMAL INDEPENDENT SET (MIN k-MIS) problem for trees. We characterize the k-maximal independent sets for trees and we present an O(n³) time algorithm for the MIN k-MIS problem under this restriction. We will also show that we can test an independent set for k-maximality in O(n) time for trees.