Finding sparse induced subgraphs on graphs of bounded induced matching treewidth

Abstract

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 a graph $G$, denoted by $\mathsf{tree}-\hat{I}¼(G)$, is the minimum induced matching width of a tree decomposition of $G$. The parameter $\mathsf{tree}-\hat{I}¼$ 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 $\mathsf{tree}-\hat{I}¼$. 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 ${\mathsf{CMSO}}_2$-sentence $\hat{I}¦$, and are asked to find a maximum-weight set $X\subseteq V(G)$ so that $G[X]$ has treewidth at most $w$ and satisfies $\hat{I}¦$. 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 $\mathsf{tree}-\hat{I}¼(G)$, $w$, and $|\hat{I}¦|$ are bounded. The running time of our algorithm for $n$-vertex graphs $G$ with $\mathsf{tree}-\hat{I}¼(G)\le k$ is $f(k,w,|\hat{I}¦|)\cdot n^{O(k{w}^2)}$ for a computable function $f$.

31 pages