Approximation algorithms for finding and partitioning unit-disk graphs into co-$k$-plexes

Abstract

This article studies a degree-bounded generalization of independent sets called co-$k$-plexes. Constant factor approximation algorithms are developed for the maximum co-$k$-plex problem on unit-disk graphs. The related problem of minimum co-$k$-plex coloring that generalizes classical vertex coloring is also studied in the context of unit-disk graphs. We extend several classical approximation results for independent sets in UDGs to co-$k$-plexes, and settle a recent conjecture on the approximability of co-$k$-plex coloring in UDGs.