The max quasi‐independent set problem

In this paper, we deal with the problem of finding quasi‐independent sets in graphs. This problem is formally defined in three versions, which are shown to be polynomially equivalent. The one that looks most general, namely, f‐max quasi‐independent set, consists of, given a graph and a non‐decreasing function f, finding a maximum size subset Q of the vertices of the graph, such that the number of edges in the induced subgraph is less than or equal to f(|Q|). For this problem, we show an exact solution method that runs within time $O^{*}(2^{\frac{d‐27/23}{d+1}n})$ on graphs of average degree bounded by d. For the most specifically defined γ‐max quasi‐independent set and k‐max quasi‐independent set problems, several results on complexity and approximation are shown, and greedy algorithms are proposed, analyzed and tested.