<p>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$
</p>

<p>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.</p>

<p>Does this come up in any literature?</p>

<p><b>Clarification</b>
Bags in the <a href="http://en.wikipedia.org/wiki/Tree_decomposition" rel="nofollow">context of</a> 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.</p>

<p>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.</p>

<p>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</p>

CC BY-SA 2.5
2010-12-03T07:12:02.343Z
what's a bag graph ?
Suresh Venkat
CC BY-SA 2.5
2010-12-03T07:17:35.100Z
@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.
gphilip
CC BY-SA 2.5
2010-12-03T08:25:57.243Z
added clarification
Yaroslav Bulatov
CC BY-SA 2.5
2010-12-03T08:30:34.787Z
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)
Suresh Venkat
CC BY-SA 2.5
2010-12-03T08:47:16.843Z
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.
Yaroslav Bulatov
CC BY-SA 2.5
2010-12-03T10:15:09.940Z
right. doesn't seem like anything is known about this
Suresh Venkat
CC BY-SA 2.5
2010-12-09T13:53:49.590Z
Related post on MO: http://mathoverflow.net/questions/48197/the-girthwidth-of-a-graph
Hsien-Chih Chang 張顯之
<graph-theory><co.combinatorics><treewidth>
Decomposition based on approximate separators in graph
Yaroslav Bulatov
# Decomposition based on approximate separators in graph

(Asked by: username_0 on 2010-12-03)

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](http://en.wikipedia.org/wiki/Tree_decomposition) 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

**Tags:** graph-theory, co.combinatorics, treewidth
> **Comments:**
> **username_1**: what's a bag graph ?  
> **username_2**: @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.  
> **username_0**: added clarification  
> **username_1**: 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)  
> **username_0**: 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.  
> **username_1**: right. doesn't seem like anything is known about this  
> **username_3**: Related post on MO: http://mathoverflow.net/questions/48197/the-girthwidth-of-a-graph  

---

## 0 answers

