Tree decompositions meet induced matchings: beyond Max Weight Independent Set

Tree decompositions meet induced matchings: beyond Max Weight Independent Set

24 Feb 2024 | Paloma T. Lima, Martin Milanič, Peter Muršič, Karolina Okrasa, Paweł Rzążewski, Kenny Štorgel
This paper explores the computational complexity of various graph problems in the context of graphs with bounded induced matching treewidth. The induced matching treewidth of a graph \( G \) is defined as the minimum value of \( \mu(\mathcal{T}) \), where \( \mathcal{T} \) is a tree decomposition of \( G \), and \( \mu(\mathcal{T}) \) is the size of the largest induced matching in \( G \) whose edges intersect a single bag of \( \mathcal{T} \). Yolov [SODA 2018] proved that MAX WEIGHT INDEPENDENT SET can be solved in polynomial time for graphs with bounded induced matching treewidth. The main results of this paper include: 1. **Solving MIN WEIGHT FEEDBACK VERTEX SET**: The authors provide a polynomial-time algorithm for MIN WEIGHT FEEDBACK VERTEX SET in graphs with bounded induced matching treewidth. 2. **Packing Induced Subgraphs**: They present positive results concerning the packing of induced subgraphs, leading to a PTAS for finding the largest induced subgraph of bounded treewidth. 3. **$(r, \psi)$-MWIS for Bounded Tree-independence Number**: They conjecture and prove that $(r, \psi)$-MWIS can be solved in polynomial time for graphs with bounded tree-independence number, where \( r \) is a fixed integer and \( \psi \) is a CMSO$_2$ formula. 4. **Complexity of Computing Induced Matching Treewidth**: They establish hardness results for exact and approximate computation of induced matching treewidth, showing that determining whether \( \text{tree-\mu}(G) \leq k \) is NP-complete for \( k \geq 4 \). The paper also includes several structural results and computational bounds related to induced matching treewidth, such as the relationship between induced matching treewidth, tree-independence number, and treewidth for graphs with bounded degree. The authors conclude with directions for further research, including the study of induced matching treewidth in specific graph families.This paper explores the computational complexity of various graph problems in the context of graphs with bounded induced matching treewidth. The induced matching treewidth of a graph \( G \) is defined as the minimum value of \( \mu(\mathcal{T}) \), where \( \mathcal{T} \) is a tree decomposition of \( G \), and \( \mu(\mathcal{T}) \) is the size of the largest induced matching in \( G \) whose edges intersect a single bag of \( \mathcal{T} \). Yolov [SODA 2018] proved that MAX WEIGHT INDEPENDENT SET can be solved in polynomial time for graphs with bounded induced matching treewidth. The main results of this paper include: 1. **Solving MIN WEIGHT FEEDBACK VERTEX SET**: The authors provide a polynomial-time algorithm for MIN WEIGHT FEEDBACK VERTEX SET in graphs with bounded induced matching treewidth. 2. **Packing Induced Subgraphs**: They present positive results concerning the packing of induced subgraphs, leading to a PTAS for finding the largest induced subgraph of bounded treewidth. 3. **$(r, \psi)$-MWIS for Bounded Tree-independence Number**: They conjecture and prove that $(r, \psi)$-MWIS can be solved in polynomial time for graphs with bounded tree-independence number, where \( r \) is a fixed integer and \( \psi \) is a CMSO$_2$ formula. 4. **Complexity of Computing Induced Matching Treewidth**: They establish hardness results for exact and approximate computation of induced matching treewidth, showing that determining whether \( \text{tree-\mu}(G) \leq k \) is NP-complete for \( k \geq 4 \). The paper also includes several structural results and computational bounds related to induced matching treewidth, such as the relationship between induced matching treewidth, tree-independence number, and treewidth for graphs with bounded degree. The authors conclude with directions for further research, including the study of induced matching treewidth in specific graph families.
Reach us at info@study.space
Understanding Tree decompositions meet induced matchings%3A beyond Max Weight Independent Set