A faster algorithm for maximum independent set on interval filament graphs

Abstract

We provide an algorithm requiring only $O(N^2)$ time to compute the maximum weight independent set in an $N$-vertex interval filament graph. This implies an $O(N^4)$-time algorithm to compute the maximum weight induced matching in such graphs. Both algorithms significantly improve upon the previous best complexities for these problems. Previously, the maximum weight independent set and maximum weight induced matching problems required $O(N^3)$ and $O(N^6)$ time respectively.