24 Feb 2024 | Paloma T. Lima, Martin Milanič, Peter Muršič, Karolina Okrasa, Paweł Rzążewski, Kenny Štorgel
**Summary:**
This paper explores the computational complexity of various graph problems on classes of graphs with bounded induced matching treewidth. The induced matching treewidth of a graph is defined as the minimum size of a largest induced matching in the graph that intersects a single bag of a tree decomposition. The paper presents several key results:
1. **Polynomial-Time Algorithms**: The authors show that the MAX WEIGHT INDUCED FOREST problem can be solved in polynomial time for graphs with bounded induced matching treewidth. This is achieved by leveraging structural properties of such graphs and efficient enumeration of signatures for maximal induced forests.
2. **Independent Packings**: The paper also addresses the problem of packing independent induced subgraphs, showing that for graphs with bounded induced matching treewidth, this problem can be solved in polynomial time. This includes applications to problems like MAX WEIGHT INDEPENDENT PACKING and MAX WEIGHT INDUCED MATCHING.
3. **Tree-Independence Number**: The paper introduces the concept of tree-independence number, which is the minimum size of a largest independent set contained in a bag of a tree decomposition. It shows that graphs with bounded tree-independence number have bounded induced matching treewidth and vice versa, and that these parameters are useful for solving various graph problems.
4. **Complexity of Computing Induced Matching Treewidth**: The paper discusses the computational complexity of determining the induced matching treewidth of a graph, showing that it is NP-complete for certain values of k. It also provides polynomial-time algorithms for specific cases, such as when the induced matching treewidth is 1.
5. **Generalizations and Conjectures**: The authors conjecture that for graphs with bounded induced matching treewidth, a wide range of problems expressible in CMSO₂ logic can be solved in polynomial time. This conjecture is supported by results showing that graphs with bounded tree-independence number, a subclass of graphs with bounded induced matching treewidth, allow for such solutions.
The paper concludes with a discussion of the implications of these results for algorithmic graph theory, highlighting the importance of induced matching treewidth as a parameter for efficiently solving complex graph problems.**Summary:**
This paper explores the computational complexity of various graph problems on classes of graphs with bounded induced matching treewidth. The induced matching treewidth of a graph is defined as the minimum size of a largest induced matching in the graph that intersects a single bag of a tree decomposition. The paper presents several key results:
1. **Polynomial-Time Algorithms**: The authors show that the MAX WEIGHT INDUCED FOREST problem can be solved in polynomial time for graphs with bounded induced matching treewidth. This is achieved by leveraging structural properties of such graphs and efficient enumeration of signatures for maximal induced forests.
2. **Independent Packings**: The paper also addresses the problem of packing independent induced subgraphs, showing that for graphs with bounded induced matching treewidth, this problem can be solved in polynomial time. This includes applications to problems like MAX WEIGHT INDEPENDENT PACKING and MAX WEIGHT INDUCED MATCHING.
3. **Tree-Independence Number**: The paper introduces the concept of tree-independence number, which is the minimum size of a largest independent set contained in a bag of a tree decomposition. It shows that graphs with bounded tree-independence number have bounded induced matching treewidth and vice versa, and that these parameters are useful for solving various graph problems.
4. **Complexity of Computing Induced Matching Treewidth**: The paper discusses the computational complexity of determining the induced matching treewidth of a graph, showing that it is NP-complete for certain values of k. It also provides polynomial-time algorithms for specific cases, such as when the induced matching treewidth is 1.
5. **Generalizations and Conjectures**: The authors conjecture that for graphs with bounded induced matching treewidth, a wide range of problems expressible in CMSO₂ logic can be solved in polynomial time. This conjecture is supported by results showing that graphs with bounded tree-independence number, a subclass of graphs with bounded induced matching treewidth, allow for such solutions.
The paper concludes with a discussion of the implications of these results for algorithmic graph theory, highlighting the importance of induced matching treewidth as a parameter for efficiently solving complex graph problems.