Polynomial-time Approximation of Independent Set Parameterized by Treewidth

Abstract

We prove the following result about approximating the maximum independent set in a graph. Informally, we show that any approximation algorithm with a ``non-trivial'' approximation ratio (as a function of the number of vertices of the input graph $G$) can be turned into an approximation algorithm achieving almost the same ratio, albeit as a function of the treewidth of $G$. More formally, we prove that for any function $f$, the existence of a polynomial time $(n/f(n))$-approximation algorithm yields the existence of a polynomial time $O(tw\cdot \log f(tw)/f(tw))$-approximation algorithm, where $n$ and $tw$ denote the number of vertices and the width of a given tree decomposition of the input graph. By pipelining our result with the state-of-the-art $O(n\cdot (\log \log n{)}^2/{\log }^{3}n)$-approximation algorithm by Feige (2004), this implies an $O(tw\cdot (\log \log tw{)}^3/{\log }^{3}tw)$-approximation algorithm.

To appear in the 31st Annual European Symposium on Algorithms (ESA 2023)