Suppose I want to find vertex subset $S$ of graph $G=(V,E)$ such that any simple closed walk that visits vertices both in $S$ and in $V\backslash S$ has length $\ge g$

The idea is to relax requirements of tree decomposition to get bag-graph of large girth instead of a tree, and form an approximation algorithm based on this decomposition.

Does this come up in any literature?

Clarification Bags in the context of tree decomposition are sets of nodes. Taking bags produced by tree decomposition algorithm and connecting any pair of bags that are not disjoint gives a tree.

This trade-off idea is briefly mentioned in Koller's "Graphical Models" book where she calls it "Cluster Graph" and defines it similar to a tree decomposition except that the graph formed by connecting overlapping bags is not restricted to be a tree. In the context of probabilistic inference, this approach gives a way to trade off cost and accuracy, with exact tree decomposition-based approach as a special case.

Since quality of approximation improves with girth of such graph while complexity increases with size of bags/clusters, a natural question is when it's possible to find a "(relaxed?) tree decomposition" where largest bag size is bounded above and girth is bounded below

  • $\begingroup$ what's a bag graph ? $\endgroup$ Commented Dec 3, 2010 at 7:12
  • $\begingroup$ @Suresh : I think by bag-graph Yaroslav means the underlying tree, in the case of a tree decomposition. In his modified decomposition (of whose exact definition I am not sure) this may not necessarily be a tree (I guess), so he calls it a bag-graph. $\endgroup$
    – gphilip
    Commented Dec 3, 2010 at 7:17
  • $\begingroup$ added clarification $\endgroup$ Commented Dec 3, 2010 at 8:25
  • 1
    $\begingroup$ It seems to me that your approximation question is a bit of a red herring: the real interesting question is whether there's a nice notion of the 'cycle width" of a graph (or "girth width" or something like that) $\endgroup$ Commented Dec 3, 2010 at 8:30
  • $\begingroup$ For every k you could define "girth width" as the largest achievable girth of the "modified tree decomposition" such that each bag is smaller than k. $\endgroup$ Commented Dec 3, 2010 at 8:47


Your Answer

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