Tangles are Decided by Weighted Vertex Sets
Advances in Combinatorics · 2020
DOI: 10.19086/aic.13691 ↗Kurz gefasst
Fachartikel in der Zeitschrift Advances in Combinatorics, 2020. Verfasst von Christian Elbracht und 2 weiteren Autor:innen.
Abstract (Originalsprache)
Tree-like decompositions play an important role both in structural combinatorics and algorithm design. The most well-known are [tree decompositions](https://en.wikipedia.org/wiki/Tree_decomposition) of graphs, which are of key importance in the Graph Minor Project of Robertson and Seymour as well as in algorithm design. The minimum width of a tree decomposition is the [treewidth](https://en.wikipedia.org/wiki/Treewidth) of a graph; this parameter captures how closely the global structure of a graph resembles a tree. In particular, a graph has treewidth one if and only if each of its components is a tree. Treewidth has a strong [duality property](https://en.wikipedia.org/wiki/Duality_(optimization)) in the sense of mathematical optimization: the minimum treewidth of a graph is equal to the maximum order of a [bramble](https://en.wikipedia.org/wiki/Bramble_(graph_theory)) increased by one; a bramble is a collection of touching connected subgraphs that cannot be hit by a small set of vertices. [Branchwidth](https://en.wikipedia.org/wiki/Branch-decomposition), which is linearly related to treewidth, is another important width parameter, and its dual parameter is the maximum order of a *tangle*, an object that is more amenable to generalizations to other combinatorial structures than a bramble. Informally speaking, a tangle picks for every separation a small part in a way that small parts of any three separations do not cover the whole structure. In the case of graphs, a tangle of order $k$ concerns vertex $k$-separations, i.e., pairs of subsets of the vertex set such that the union of the two subsets is the whole vertex set, the intersection has size at most $k$ and every edge is in one of the subsets. The main result of the article asserts that every tangle of a graph can be obtained by assigning weights to the vertices so that the small part of every $k$-separation is the one of smaller weight.
Zitieren
APA
Elbracht, C., Kneip, J., & Teegen, M. (2020). Tangles are Decided by Weighted Vertex Sets. Advances in Combinatorics. https://doi.org/10.19086/aic.13691
Vancouver
Elbracht C, Kneip J, Teegen M. Tangles are Decided by Weighted Vertex Sets. Advances in Combinatorics. 2020. doi:10.19086/aic.13691
BibTeX
@article{Elbracht2020,
author = {Elbracht, Christian and Kneip, Jakob and Teegen, Maximilian},
title = {Tangles are Decided by Weighted Vertex Sets},
journal = {Advances in Combinatorics},
year = {2020},
doi = {10.19086/aic.13691}
}
EUVIMED