A New Simple Algorithm for Computing Maximum Weight Induced Forests in Circle Graphs

Abstract

This paper describes a new, simple algorithm for computing a maximum weight induced forest in a circle graph. The algorithm requires $O(n^3 m)$ time and $O(n^3)$ space.
In the unweighted case, an algorithm operating in $O(n^2 mk)$ time and $O(nk^2)$ space is described, where $k$ is the cardinality of a maximum induced forest in the circle graph.
The previously described algorithms require $O(n^7)$ time and $O(n^3)$ space. The new algorithm is simple to describe and implement within the stated bounds.  We also note the existence of an (impractical) $O(n^{4.686})$ time algorithm in the unweighted case.