Independent set on unit disk graphs

This problem was submitted by Jiri Fiala, Department of Applied Mathematics and Institute for Theoretical Computer Science, Charles University, Prague

fiala@kam.ms.mff.cuni.cz

Unit disk graphs are intersection graphs of unit disks in the plane. We are interested in fixed-parameter (in)tractability of the independent set problem restricted to this class of graphs. We could give partial results giving promising indices that the fixed-parameter complexity of this problem should not belong neither to W[1]-hard nor FPT classes of (fixed parameter) problems. In fact we show an algorithm with exponent sublinear in k, but not constant. It is designed on the space separation argument applied on the underlying geometric representation. (Joint work with Jochen Alber.)

Back to the Problem Session page and to the workshop page