Finding sparse induced subgraphs on graphs of bounded induced matching treewidth

The induced matching width of a tree decomposition of a graph G is the cardinality of a largest induced matching M of G, such that there exists a bag that intersects every edge in M . The induced matching treewidth of G, denoted by tree-µ(G), is the minimum induced matching width of a tree decomposition of G. The parameter tree-µ was introduced by Yolov [SODA '18], who showed that, for example, Maximum-Weight Independent Set can be solved in polynomial-time on graphs of bounded tree-µ. Lima, Milanič, Muršič, Okrasa, Rzążewski, and Štorgel [ESA '24] conjectured that this algorithm can be generalized to a meta-problem called Maximum-Weight Induced Subgraph of Bounded Treewidth, where we are given a vertex-weighted graph G, an integer w, and a CMSO 2 -sentence Φ, and are asked to find a maximum-weight set X ⊆ V (G) so that G[X] has treewidth at most w and satisfies Φ. They proved the conjecture for some special cases, such as for the problem Maximum-Weight Induced Forest.

In this paper, we prove the general case of the conjecture. In particular, we show that Maximum-Weight Induced Subgraph of Bounded Treewidth is polynomial-time solvable when tree-µ(G), w, and |Φ| are bounded. The running time of our algorithm for n-vertex graphs G with tree-µ(G) ≤ k is f (k, w, |Φ|) • n O(kw 2 ) for a computable function f .