Tree decompositions meet induced matchings: beyond Max Weight Independent Set
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917597265526784 |
|---|---|
| author | Lima, Paloma T. Milanič, Martin Muršič, Peter Okrasa, Karolina Rzążewski, Paweł Štorgel, Kenny |
| author_facet | Lima, Paloma T. Milanič, Martin Muršič, Peter Okrasa, Karolina Rzążewski, Paweł Štorgel, Kenny |
| contents | For a tree decomposition $\mathcal{T}$ of a graph $G$, by $μ(\mathcal{T})$ we denote the size of a largest induced matching in $G$ all of whose edges intersect one bag of $\mathcal{T}$. Induced matching treewidth of a graph $G$ is the minimum value of $μ(\mathcal{T})$ over all tree decompositions $\mathcal{T}$ of $G$. Yolov [SODA 2018] proved that Max Weight Independent Set can be solved in polynomial time for graphs of bounded induced matching treewidth.
In this paper we explore what other problems are tractable in such classes of graphs. As our main result, we give a polynomial-time algorithm for Min Weight Feedback Vertex Set. We also provide some positive results concerning packing induced subgraphs, which in particular imply a PTAS for the problem of finding a largest induced subgraph of bounded treewidth.
These results suggest that in graphs of bounded induced matching treewidth, one could find in polynomial time a maximum-weight induced subgraph of bounded treewidth satisfying a given CMSO$_2$ formula. We conjecture that such a result indeed holds and prove it for graphs of bounded tree-independence number, which form a rich and important family of subclasses of graphs of bounded induced matching treewidth.
We complement these algorithmic results with a number of complexity and structural results concerning induced matching treewidth. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_15834 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tree decompositions meet induced matchings: beyond Max Weight Independent Set Lima, Paloma T. Milanič, Martin Muršič, Peter Okrasa, Karolina Rzążewski, Paweł Štorgel, Kenny Data Structures and Algorithms Discrete Mathematics Combinatorics 05C85 (Primary), 68Q25, 68R10, 05C05, 05C12, 05C38, 05C15, 05C40, 05C70, 05C75, 05C76, 05C83 (Secondary) For a tree decomposition $\mathcal{T}$ of a graph $G$, by $μ(\mathcal{T})$ we denote the size of a largest induced matching in $G$ all of whose edges intersect one bag of $\mathcal{T}$. Induced matching treewidth of a graph $G$ is the minimum value of $μ(\mathcal{T})$ over all tree decompositions $\mathcal{T}$ of $G$. Yolov [SODA 2018] proved that Max Weight Independent Set can be solved in polynomial time for graphs of bounded induced matching treewidth. In this paper we explore what other problems are tractable in such classes of graphs. As our main result, we give a polynomial-time algorithm for Min Weight Feedback Vertex Set. We also provide some positive results concerning packing induced subgraphs, which in particular imply a PTAS for the problem of finding a largest induced subgraph of bounded treewidth. These results suggest that in graphs of bounded induced matching treewidth, one could find in polynomial time a maximum-weight induced subgraph of bounded treewidth satisfying a given CMSO$_2$ formula. We conjecture that such a result indeed holds and prove it for graphs of bounded tree-independence number, which form a rich and important family of subclasses of graphs of bounded induced matching treewidth. We complement these algorithmic results with a number of complexity and structural results concerning induced matching treewidth. |
| title | Tree decompositions meet induced matchings: beyond Max Weight Independent Set |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics 05C85 (Primary), 68Q25, 68R10, 05C05, 05C12, 05C38, 05C15, 05C40, 05C70, 05C75, 05C76, 05C83 (Secondary) |
| url | https://arxiv.org/abs/2402.15834 |