2
$\begingroup$

The treewidth is a parameter of the graph that describes its similarity to a tree. Treewidth is NP-hard to find. For the introduction please see wikipedia

The question is how to generate interesting graphs with a specified treewidth? I know that: 1) Any graph containing a $k+1$-clique has treewidth at least $k$ 2) Any graph containing a $k \times k$ grid has treewidth at least $k$

Are other variants possible?

Improve this question
$\endgroup$
4
  • $\begingroup$ $k$-trees can be generated incrementally by definition. Subgraphs that are not too sparse (e.g., leave at least one $(k+1)$-clique intact) also have treewidth $k$. Generating w.r. uniform measure among graphs of treewidth $k$ seems hard. $\endgroup$
    – Mikhail Tikhomirov
    Commented Jul 7, 2019 at 21:33
  • $\begingroup$ Thanks for the comment! Having an intact $k+1$-clique in the graph is another option which is also not very interesting. However, is it possible to remove some edges from the clique so the treewidth is still $k$? I corrected the original question to mention the large clique case. I would like to generate hard cases to test the tree decomposition algorithm $\endgroup$
    – qbit-
    Commented Jul 7, 2019 at 22:21
  • $\begingroup$ An interesting test would be to distinguish between a full $k$-tree (treewidth $k$) and and a full $k$-tree with an extra random edge (treewidth $k + 1$). You may also want to look up critical forbidden minor tables for small $k$ (can't quite find the link myself right now). $\endgroup$
    – Mikhail Tikhomirov
    Commented Jul 7, 2019 at 22:50
  • $\begingroup$ Thanks for this idea! It looks the modification of the $k$-tree is the route to take. Also, I found some results on the structure of the treewidth-$k$ graphs which do not contain a $k \times k$-grid as a minor here: arxiv.org/pdf/1207.6927.pdf I would accept your comment as the answer $\endgroup$
    – qbit-
    Commented Jul 7, 2019 at 23:36

2 Answers 2

Reset to default
0
$\begingroup$

This is an extended comment. Here are some classes of graphs that should be interesting:

  • $k$-trees by definition have treewidth $k$; moreover, adding any edge to a $k$-tree increases treewidth. This should be an interesting example since $k$-trees are "borderline maximal" with treewidth $k$.
  • Graphs with treewdith $\leq k$ are famously characterized by a finite set of forbidden minors. Each of these minors is again interesting since they are "borderline minimal" with treewidth $> k$. Again, deleting any edge from any such critical graph decreases treewidth.
  • Edge subdivision does not change treewidth, hence any interesting graph can be artificially "inflated" to produce another, sparser one.
Improve this answer
$\endgroup$
0
$\begingroup$

Graphs of bounded treewidth may be defined by forbidden induced subgraphs.

Examples are on graphclasses.org

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .