Abstractly, tree/path decompositions of a graph $G$ can be thought of as doing the following:

  • fix a "skeleton" class of graphs (tree or path)
  • Pick a member of this class $H$. Associate with each node of $H$ a subset of vertices of $G$ such that (1) For each edge $e = (u,v)$ in $G$, there exists a node of $H$ containing both $u$ and $v$ and (2) the set of nodes of $H$ containing a fixed vertex of $G$ form a connected subgraph
  • minimize the maximum cardinality of the set associated with a node of $H$, over all such associations and skeletons.

Suppose that rather than choosing a tree or a path, we are allowed to pick any graph of girth at least $g$, for some fixed parameter $g$. Is there anything known about the resulting "girthwidth" of a graph ?

  • $\begingroup$ Suppose every vertex in G lies on some edge. Then saying "the endpoints of each edge in G appear together in some node of H" is just saying that for some node of H, the subset of the vertices of G that's associated to it is the full set of all vertices in G. Since criteria (1) must be met, every skeleton+association must have some node that has the maximal set of all vertices of G associated to it, thus independent of H, the maximum cardinality of a set associated with a node of H is |G|, and minimizing the constant |G| over all H+associations still give |G|. Is your definition right? $\endgroup$ – Amit Kumar Gupta Dec 3 '10 at 18:01
  • $\begingroup$ that's not true. the edges don't have to be "witnessed" by the same node of $H$ (aside: this is the standard definition of a tree decomposition). maybe I wasn't clear on the quantification: for each edge, there exists some node of H in which the endpoints appear. $\endgroup$ – Suresh Venkat Dec 3 '10 at 18:05
  • $\begingroup$ I reworded accordingly. $\endgroup$ – Suresh Venkat Dec 3 '10 at 18:06
  • 1
    $\begingroup$ I think something is not correct with this definition, because you can increase the girth of any skeleton graph by subdividing its edges, without significantly changing the class of graphs representable over that skeleton. $\endgroup$ – David Eppstein Dec 3 '10 at 22:17
  • $\begingroup$ David: is that still true if you restrict maximum size of any bag (node of H)? $\endgroup$ – Yaroslav Bulatov Dec 4 '10 at 1:20

The (finite) "girthwidth" is always 1 so this is not going to be that useful (as defined here anyway). First some notation: Let a $g$-decomposition of a graph $G$ consist of a graph $H$ with girth at least $g$ and an assignment to each node of $H$ of a set of vertices as above, the width of such a decomposition be one less than the maximum number of vertices assigned to any node of $H$, and $w_g(G)$ be the minimum width of any $g$-decomposition of $G$. Then $w_3(G)$ is the minimum width where $H$ is completely unrestricted. So $w_3(G)=1$ as we can take $H$ to be a complete graph and put the endpoints of each edge in their own node. Since the girth of a tree is infinite a tree decomposition is an $\infty$-decomposition and the tree width is $w_{\infty}$. Actually these are the only widths that matter since $w_3=w_b \le w_{\infty}$ for any finite $3 \le b$: If $a \lt b \le \infty$ then $w_a \le w_b$ simply by the definitions. However if $a \lt b \lt \infty$ then also $w_b \le w_a$ since we can turn an $a$-decomposition into a $2a$-decomposition by putting a new node in the middle of each edge and assigning it the same vertex set as one of its neighbors.

Maybe one could restrict to $H$ being a planar graph although $w_3(G)$ would still be 1 for planar $G$. I wonder when the "cycle-width" is less than the path-width. If one demands that no two nodes get the same vertex set (which is no restriction for tree width) it would get harder (and sometimes impossible if we forbid empty nodes)

A use of tree-width is that many hard (NP complete, say) problems become easy (say polynomial time) when restricted to bounded tree-width. A variant width could be justified merely by its own intrinsic appeal, but would be more motivated if it had similar applications.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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