9
$\begingroup$

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.

Improve this question
$\endgroup$

4 Answers 4

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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) $\endgroup$
    – Saeed
    Feb 20, 2012 at 21:11
  • $\begingroup$ The treewidth paper is available at Citeseer 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: cstheory.stackexchange.com/questions/5155/… . $\endgroup$
    – Bart Jansen
    Feb 21, 2012 at 9:48
  • $\begingroup$ 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. $\endgroup$
    – Saeed
    Feb 21, 2012 at 11:51
  • $\begingroup$ 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" ( cs.princeton.edu/~kintali/#proprecon ). You might contact him directly for to ask about the current state of the art. $\endgroup$
    – Bart Jansen
    Feb 21, 2012 at 12:21
  • $\begingroup$ 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 dx.doi.org/10.4230/LIPIcs.STACS.2012.278, and Seymour claimed an improvement to $2^{O(r \log r)}$ in August 2012. $\endgroup$
    – András Salamon
    May 30, 2013 at 15:46
7
$\begingroup$

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$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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")? $\endgroup$
    – Nikhil
    Feb 19, 2012 at 13:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – Janne H. Korhonen
    Feb 19, 2012 at 20:58
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Jukka Suomela
    Feb 19, 2012 at 22:23
6
$\begingroup$

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

Improve this answer
$\endgroup$
5
$\begingroup$

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)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.