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-\(\mu(G)\), is the minimum induced matching width of a tree decomposition of \(G\). The parameter tree-\(\mu\) 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-\(\mu\). Lima, Milanič, Muršič, Okrasa, Rzążewski, and Šorgel [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 \(\mathsf{CMSO_2}\)-sentence \(\Phi\), and are asked to find a maximum-weight set \(X \subseteq V(G)\) so that \(G[X]\) has treewidth at most \(w\) and satisfies \(\Phi\). They proved the conjecture for some special cases, such as for the problem Maximum-Weight Induced Forest.