Camouflaging Independent Sets in Quasi-Random Graphs

Mark Brockington and Joseph C. Culberson

DIMACS Series, Volume 26, "Cliques, Coloring and Satisfiability" Editors: David S. Johnson and Michael A. Trick, 75-88, 1996.

Abstract

In this paper, we look at the problem of how one might try to hide a large independent set in a graph in which all other independent sets are significantly smaller.

We observe that the most common methods of generating graphs with known maximal independent sets are subject to attack using quite simple techniques that are successful significantly often for graphs of practical size. We present an improved random graph generation system, DELTA, which increases the range of maximal independent sets that can be hidden from these techniques.

Full paper preprint

Joseph Culberson