Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915382328033280 |
|---|---|
| author | Bodlaender, Hans L. Fomin, Fedor V. Korhonen, Tuukka |
| author_facet | Bodlaender, Hans L. Fomin, Fedor V. Korhonen, Tuukka |
| contents | 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-}μ(G)$, is the minimum induced matching width of a tree decomposition of $G$. The parameter $\mathsf{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 $\mathsf{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 $\mathsf{CMSO}_2$-sentence $Φ$, and are asked to find a maximum-weight set $X \subseteq 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 $\mathsf{tree-}μ(G)$, $w$, and $|Φ|$ are bounded. The running time of our algorithm for $n$-vertex graphs $G$ with $\mathsf{tree} - μ(G) \le k$ is $f(k, w, |Φ|) \cdot n^{O(k w^2)}$ for a computable function $f$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_07975 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Finding sparse induced subgraphs on graphs of bounded induced matching treewidth Bodlaender, Hans L. Fomin, Fedor V. Korhonen, Tuukka Data Structures and Algorithms 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-}μ(G)$, is the minimum induced matching width of a tree decomposition of $G$. The parameter $\mathsf{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 $\mathsf{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 $\mathsf{CMSO}_2$-sentence $Φ$, and are asked to find a maximum-weight set $X \subseteq 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 $\mathsf{tree-}μ(G)$, $w$, and $|Φ|$ are bounded. The running time of our algorithm for $n$-vertex graphs $G$ with $\mathsf{tree} - μ(G) \le k$ is $f(k, w, |Φ|) \cdot n^{O(k w^2)}$ for a computable function $f$. |
| title | Finding sparse induced subgraphs on graphs of bounded induced matching treewidth |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.07975 |