导向树宽在蝴蝶子式下是封闭的

Directed treewidth is closed under taking butterfly minors

摘要 Abstract

蝴蝶子式是将无向图的子式包含关系推广到有向图的一种方法。在有向图结构理论的许多结果中,除了有向树宽(树宽这一宽度度量在有向图上的推广)外,蝴蝶子式常作为一个中心工具。Adler [JCTB'07] 曾证明有向树宽在取蝴蝶子式时不是封闭的。多年来,文献中出现了许多有向树宽的替代定义,这些定义在小函数范围内等价于原始定义。本文考虑了其中主要的几种,并证明它们并非都存在Adler所指出的问题。

Butterfly minors are a generalisation of the minor containment relation for undirected graphs to directed graphs. Many results in directed structural graph theory use this notion as a central tool next to directed treewidth, a generalisation of the width measure treewidth to directed graphs. Adler [JCTB'07] showed that the directed treewidth is not closed under taking butterfly minors. Over the years, many alternative definitions for directed treewidth appeared throughout the literature, equivalent to the original definition up to small functions. In this paper, we consider the major ones and show that not all of them share the problem identified by Adler.

导向树宽在蝴蝶子式下是封闭的 - arXiv