<p>The maximum independent set problem is a packing problem (you can think it as packing disjoint stars), and it has a well-known algorithm with running time $2^k \operatorname{poly(n)}$ in graphs with treewidth at most $k$. </p>

CC BY-SA 3.0
2012-02-19T13:29:50.370Z
Thanks Janne for your response. I am aware of the MIS algorithm. Apart from MIS, has the notion of treewidths been applied to packing of other structures? Also, I am not entirely convinced to think of MIS as packing of disjoint stars, could you please explain your point on this? (which star structure are you trying to pack, what is the notion of "disjoint stars")?
Nikhil
CC BY-SA 3.0
2012-02-19T20:58:31.840Z
It's not quite as straightforward as I thought when posting the answer. "Packing edge-disjoint stars" would be more appropriate, and then you have to require that any placed star has as large degree as possible. I don't remember seeing treewidth applied to any more complex packing problems.
Janne H. Korhonen
CC BY-SA 3.0
2012-02-19T22:23:05.220Z
Maximum independent set is certainly a "packing problem" in the usual terminology; another example of a packing problem is maximum matching. (They are packing integer programs; the LP relaxation is a packing LP.)
Jukka Suomela
CC BY-SA 3.0
2012-02-19T12:45:21.417Z
2012-02-19T12:45:21.417Z
Janne H. Korhonen
<p>A wonderful reference on this topic is Bruce Reed's survey article below.</p>

<p>Reed, B. (1997). Tree width and tangles: A new connectivity measure and some applications. Surveys in combinatorics, 241, 87-162.</p>

<p>One of my recent papers allows one to bypass the grid-minor theorem in some cases via treewidth decomposition theorems. See paper below.</p>

<p>Large-Treewidth Graph Decompositions and Applications
<a href="http://arxiv.org/abs/1304.1577">http://arxiv.org/abs/1304.1577</a></p>

CC BY-SA 3.0
2013-05-29T23:01:10.123Z
2013-05-29T23:01:10.123Z
Chandra Chekuri
<p>This is also a vague answer. There is a duality similar to Erdos-Posa theorem for graphs of bounded treewidth. See, for example
Fedor V. Fomin, Saket Saurabh, Dimitrios M. Thilikos: Strengthening Erdös-Pósa property for minor-closed graph classes. Journal of Graph Theory 66(3): 235-240 (2011)</p>

CC BY-SA 3.0
2012-02-19T14:14:20.243Z
2012-02-19T14:14:20.243Z
R2-D2
<p>I can interpret this question in two different ways:</p>

<p>1) When it comes to algorithmic properties of packing problems on graphs of bounded treewidth, Courcelle's Theorem shows that for every fixed $k$ we can optimally solve problems expressible in Monadic Second Order Logic in linear time on graphs of treewidth at most $k$ (see for example <a href="http://dx.doi.org/10.1093/comjnl/bxm037">http://dx.doi.org/10.1093/comjnl/bxm037</a> for a survey on the algorithmic properties of bounded-treewidth graphs). As many packing problems can be formulated in MSOL, this proves tractability of many such problems on graphs of bounded treewidth, including Independent Set, Triangle Packing, Cycle Packing, packing vertex/edge disjoint copies of any fixed graph, packing vertex-disjoint minor models of some fixed graph H, and so on. But as this tractability extends to all MSOL-definable problems, it is not specific to packing.</p>

<p>2) When it comes to graph-structural relationships between packings and treewidth, the following might be of interest. Thanks to the work of Robertson and Seymour it is known that there is a function $f \colon \mathbb{N} \to \mathbb{N}$ such that every graph of treewidth at least $f(r)$ contains an $r \times r$ grid as a minor (the original bound for $f$ given by Seymour and Robertson was later improved in collaboration with Thomas; see <a href="http://www.sciencedirect.com/science/article/pii/S0095895684710732">http://www.sciencedirect.com/science/article/pii/S0095895684710732</a> for the current-best bound). Hence if you have a structure $S$ such that many copies of $S$ can be packed into an $r \times r$ grid minor, then you know that any graph of large treewidth contains a large packing of copies of $S$. For example, as an $r \times r$ grid (for even $r$) contains $(r/2)^2$ vertex-disjoint cycles, it follows that a graph of treewidth $f(r)$ contains at least $(r/2)^2$ disjoint cycles.</p>

CC BY-SA 3.0
2012-02-20T21:11:27.430Z
Bart May be this is irrelevant, but do you see any relation between graph reconstruction and their tree-width? Also do you have link to free version of your prof paper? (Combinatorial Optimization on Graphs of Bounded Treewidth)
Saeed
CC BY-SA 3.0
2012-02-21T09:48:16.507Z
The treewidth paper is available at Citeseer http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.2561 . As for graph reconstruction: you mean the process in which, given the multiset of all subgraphs which are obtained by deleting a single vertex, you want to reconstruct the original graph? It seems Shiva Kintali has recently looked into the question of whether the graph reconstruction conjecture is true for treewidth two: http://cstheory.stackexchange.com/questions/5155/reconstruction-conjecture-and-partial-2-trees .
Bart Jansen
CC BY-SA 3.0
2012-02-21T11:51:51.190Z
Thanks bart, yes I see Shiva's question, but, It was for one year ago, may be there is any new result, thanks in all.
Saeed
CC BY-SA 3.0
2012-02-21T12:21:28.423Z
Shiva's website lists two manuscripts on the subject, "On the Reconstruction of k-trees and trees of regular graphs" and "New Reconstructible Graph Properties" with a note "pdf coming soon" ( http://www.cs.princeton.edu/~kintali/#proprecon ). You might contact him directly for to ask about the current state of the art.
Bart Jansen
CC BY-SA 3.0
2013-05-30T15:46:50.547Z
Subsequent to this answer, the best bound for the treewidth required to ensure an $r \times r$ grid minor was improved by Kawarabayashi and Kobayashi to $2^{O(r^2\log r)}$ in http://dx.doi.org/10.4230/LIPIcs.STACS.2012.278, and Seymour claimed an improvement to $2^{O(r \log r)}$ in August 2012.
András Salamon
CC BY-SA 3.0
2012-02-20T13:24:46.967Z
2012-02-20T13:24:46.967Z
Bart Jansen
<p>My question is a bit vague. I have been wondering if (and how), we can apply the notion of treewidth to packing problems in graphs.</p>

<p>I would be happy with any insights or references of past research work on this (assuming their is some relation). Thanks.</p>

<ds.algorithms><reference-request><graph-theory><graph-algorithms><approximation-algorithms>
Treewidth and Packing
Nikhil
# Treewidth and Packing

(Asked by: username_0 on 2012-02-19)

My question is a bit vague. I have been wondering if (and how), we can apply the notion of treewidth to packing problems in graphs.

I would be happy with any insights or references of past research work on this (assuming their is some relation). Thanks.

**Tags:** ds.algorithms, reference-request, graph-theory, graph-algorithms, approximation-algorithms

---

## 4 answers

### Answer by username_5 on 2012-02-20. Score: 11 | Accepted answer

I can interpret this question in two different ways:

1) When it comes to algorithmic properties of packing problems on graphs of bounded treewidth, Courcelle's Theorem shows that for every fixed $k$ we can optimally solve problems expressible in Monadic Second Order Logic in linear time on graphs of treewidth at most $k$ (see for example <http://dx.doi.org/10.1093/comjnl/bxm037> for a survey on the algorithmic properties of bounded-treewidth graphs). As many packing problems can be formulated in MSOL, this proves tractability of many such problems on graphs of bounded treewidth, including Independent Set, Triangle Packing, Cycle Packing, packing vertex/edge disjoint copies of any fixed graph, packing vertex-disjoint minor models of some fixed graph H, and so on. But as this tractability extends to all MSOL-definable problems, it is not specific to packing.

2) When it comes to graph-structural relationships between packings and treewidth, the following might be of interest. Thanks to the work of Robertson and Seymour it is known that there is a function $f \colon \mathbb{N} \to \mathbb{N}$ such that every graph of treewidth at least $f(r)$ contains an $r \times r$ grid as a minor (the original bound for $f$ given by Seymour and Robertson was later improved in collaboration with Thomas; see <http://www.sciencedirect.com/science/article/pii/S0095895684710732> for the current-best bound). Hence if you have a structure $S$ such that many copies of $S$ can be packed into an $r \times r$ grid minor, then you know that any graph of large treewidth contains a large packing of copies of $S$. For example, as an $r \times r$ grid (for even $r$) contains $(r/2)^2$ vertex-disjoint cycles, it follows that a graph of treewidth $f(r)$ contains at least $(r/2)^2$ disjoint cycles.

> **Comments:**
> **username_6**: Bart May be this is irrelevant, but do you see any relation between graph reconstruction and their tree-width? Also do you have link to free version of your prof paper? (Combinatorial Optimization on Graphs of Bounded Treewidth)  
> **username_5**: The treewidth paper is available at Citeseer http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.2561 . As for graph reconstruction: you mean the process in which, given the multiset of all subgraphs which are obtained by deleting a single vertex, you want to reconstruct the original graph? It seems Shiva Kintali has recently looked into the question of whether the graph reconstruction conjecture is true for treewidth two: http://cstheory.stackexchange.com/questions/5155/reconstruction-conjecture-and-partial-2-trees .  
> **username_6**: Thanks bart, yes I see Shiva's question, but, It was for one year ago, may be there is any new result, thanks in all.  
> **username_5**: Shiva's website lists two manuscripts on the subject, "On the Reconstruction of k-trees and trees of regular graphs" and "New Reconstructible Graph Properties" with a note "pdf coming soon" ( http://www.cs.princeton.edu/~kintali/#proprecon ). You might contact him directly for to ask about the current state of the art.  
> **username_7**: Subsequent to this answer, the best bound for the treewidth required to ensure an $r \times r$ grid minor was improved by Kawarabayashi and Kobayashi to $2^{O(r^2\log r)}$ in http://dx.doi.org/10.4230/LIPIcs.STACS.2012.278, and Seymour claimed an improvement to $2^{O(r \log r)}$ in August 2012.  

---

### Answer by username_1 on 2012-02-19. Score: 7

The maximum independent set problem is a packing problem (you can think it as packing disjoint stars), and it has a well-known algorithm with running time $2^k \operatorname{poly(n)}$ in graphs with treewidth at most $k$.

> **Comments:**
> **username_0**: Thanks Janne for your response. I am aware of the MIS algorithm. Apart from MIS, has the notion of treewidths been applied to packing of other structures? Also, I am not entirely convinced to think of MIS as packing of disjoint stars, could you please explain your point on this? (which star structure are you trying to pack, what is the notion of "disjoint stars")?  
> **username_1**: It's not quite as straightforward as I thought when posting the answer. "Packing edge-disjoint stars" would be more appropriate, and then you have to require that any placed star has as large degree as possible. I don't remember seeing treewidth applied to any more complex packing problems.  
> **username_2**: Maximum independent set is certainly a "packing problem" in the usual terminology; another example of a packing problem is maximum matching. (They are packing integer programs; the LP relaxation is a packing LP.)  

---

### Answer by username_3 on 2013-05-29. Score: 6

A wonderful reference on this topic is Bruce Reed's survey article below.

Reed, B. (1997). Tree width and tangles: A new connectivity measure and some applications. Surveys in combinatorics, 241, 87-162.

One of my recent papers allows one to bypass the grid-minor theorem in some cases via treewidth decomposition theorems. See paper below.

Large-Treewidth Graph Decompositions and Applications
<http://arxiv.org/abs/1304.1577>


---

### Answer by username_4 on 2012-02-19. Score: 5

This is also a vague answer. There is a duality similar to Erdos-Posa theorem for graphs of bounded treewidth. See, for example
Fedor V. Fomin, Saket Saurabh, Dimitrios M. Thilikos: Strengthening Erdös-Pósa property for minor-closed graph classes. Journal of Graph Theory 66(3): 235-240 (2011)


---

