17
$\begingroup$

Is the following graph class known in the literature?

The class of graphs is parameterized by positive integers $d$ and $t$ and contains each graph $G=(V,E)$ such that for each vertex $v\in V$, the subgraph of $G$ induced on all vertices at distance at most $d$ from $v$ in $G$ has treewidth at most $t$.

It generalizes the concept of locally bounded treewidth, and it seems useful when searching for local structures in graphs.

$\endgroup$
11
$\begingroup$

The concept of exploiting properties that a graph possesses locally can be taken even further. Dawar, Grohe and Kreutzer in Locally Excluding a Minor considered classes of graphs that locally exclude a minor and Dvorak, Kral and Thomas in Deciding first-order properties for sparse graphs considered classes of graphs that have (locally) bounded expansion.

Both of those classes are subsumed by classes of nowhere dense graphs, introduced by Nesetril and Ossona de Mendez.

Grohe announced this week at the Highlights conference that Grohe, Kreutzer and Siebertz. have proved that every property of graphs definable in first-order logic can be solved in almost linear time on nowhere dense classes of graphs. This implies many fixed-parameter tractability results on nowhere dense graphs, e.g. for the (connected) dominating set and digraph kernel (both parameterized by the size of the solution), Steiner tree (parameterized by the size of the tree) and circuit satisfiability (parameterized by the depth of the circuit and the Hamming weight of the solution).

$\endgroup$
9
$\begingroup$

This is not exactly what you are asking for, but it is very closely related and thus might be nevertheless interesting to you:

The concept of local treewidth introduced in M. Frick, M.Grohe, Deciding first-order properties of locally tree-decomposable structures is more general than the definition of locally bounded treewidth in the wikipedia article to which you refer. For each graph $G$, the local treewidth of $G$ is the function $ltw^G$ which maps a radius $r$ to the maximum treewidth of $N^G_r(v)$ among all vertices $v$ of $G$, where $N^G_r(v)$ is the subgraph of $G$ induced by vertices at distance at most $r$ to $v$. A class has bounded local treewidth, if there exists a function $f$ such that $ltw^G(r) \leq f(r)$ for each $r$ and each graph $G$ belonging to the class.

$\endgroup$
  • 1
    $\begingroup$ Indeed, this seems more general than the definition on Wikipedia. However, if one requires the class of graphs to be closed under induced subgraphs, the two definitions are equivalent. Note that the Frick-Grohe paper is also cited in the Wikipedia article. $\endgroup$ – Serge Gaspers Jul 23 '13 at 11:07

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.