Generalized Graph Packing Problems Parameterized by Treewidth
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915483950776320 |
|---|---|
| author | Esmer, Barış Can Marx, Dániel |
| author_facet | Esmer, Barış Can Marx, Dániel |
| contents | $H$-Packing is the problem of finding a maximum number of vertex-disjoint copies of $H$ in a given graph $G$. $H$-Partition is the special case of finding a set of vertex-disjoint copies that cover each vertex of $G$ exactly once. Our goal is to study these problems and some generalizations on bounded-treewidth graphs. The case of $H$ being a triangle is well understood: given a tree decomposition of $G$ having treewidth $tw$, the $K_3$-Packing problem can be solved in time $2^{tw} \cdot n^{O(1)}$, while Lokshtanov et al.~[{\it ACM Transactions on Algorithms} 2018] showed, under the Strong Exponential-Time Hypothesis (SETH), that there is no $(2-ε)^{tw}\cdot n^{O(1)}$ algorithm for any $ε>0$ even for $K_3$-Partition. Similar results can be obtained for any other clique $K_d$ for $d\ge 3$. We provide generalizations in two directions:
- We consider a generalization of the problem where every vertex can be used at most $c$ times for some $c\ge 1$. When $H$ is any clique $K_d$ with $d\ge 3$, then we give upper and lower bounds showing that the optimal running time increases to $(c+1)^{tw}\cdot n^{O(1)}$. We consider two variants depending on whether a copy of $H$ can be used multiple times in the packing.
- If $H$ is not a clique, then the dependence of the running time on treewidth may not be even single exponential. Specifically, we show that if $H$ is any fixed graph where not every 2-connected component is a clique, then there is no $2^{o({tw}\log {tw})}\cdot n^{O(1)}$ algorithm for \textsc{$H$-Partition}, assuming the Exponential-Time Hypothesis (ETH). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_06091 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Generalized Graph Packing Problems Parameterized by Treewidth Esmer, Barış Can Marx, Dániel Data Structures and Algorithms Computational Complexity $H$-Packing is the problem of finding a maximum number of vertex-disjoint copies of $H$ in a given graph $G$. $H$-Partition is the special case of finding a set of vertex-disjoint copies that cover each vertex of $G$ exactly once. Our goal is to study these problems and some generalizations on bounded-treewidth graphs. The case of $H$ being a triangle is well understood: given a tree decomposition of $G$ having treewidth $tw$, the $K_3$-Packing problem can be solved in time $2^{tw} \cdot n^{O(1)}$, while Lokshtanov et al.~[{\it ACM Transactions on Algorithms} 2018] showed, under the Strong Exponential-Time Hypothesis (SETH), that there is no $(2-ε)^{tw}\cdot n^{O(1)}$ algorithm for any $ε>0$ even for $K_3$-Partition. Similar results can be obtained for any other clique $K_d$ for $d\ge 3$. We provide generalizations in two directions: - We consider a generalization of the problem where every vertex can be used at most $c$ times for some $c\ge 1$. When $H$ is any clique $K_d$ with $d\ge 3$, then we give upper and lower bounds showing that the optimal running time increases to $(c+1)^{tw}\cdot n^{O(1)}$. We consider two variants depending on whether a copy of $H$ can be used multiple times in the packing. - If $H$ is not a clique, then the dependence of the running time on treewidth may not be even single exponential. Specifically, we show that if $H$ is any fixed graph where not every 2-connected component is a clique, then there is no $2^{o({tw}\log {tw})}\cdot n^{O(1)}$ algorithm for \textsc{$H$-Partition}, assuming the Exponential-Time Hypothesis (ETH). |
| title | Generalized Graph Packing Problems Parameterized by Treewidth |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2509.06091 |