Directed Tangle Tree-Decompositions and Applications
Directed Tangle Tree-Decompositions and Applications
复制标题
有向缠结树分解与应用
DOI：
10.1137/1.9781611977073.19
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Kwon O-joung
中科院分区：
文献类型：
--
作者：
Giannopoulou Archontia C.;Kawarabayashi Ken-ichi;Kreutzer Stephan;Kwon O-joung
缠结树分解定理，由Robertson和Seymour在他们的开创性的图子式系列中证明，在结构和算法图论中是一个非常有价值的工具。本文证明了有向图的类似结果--有向缠结树分解定理。更准确地说，我们引入了有向缠结，并提供了一个有向树分解的有向图G区分所有最大有向缠结在G。此外，对于任何整数k，我们构造一个有向树分解，区分所有阶为k的有向缠结。通过稍微放松边界，我们可以使前面的结果算法化：对于FixedK，我们设计了一个多项式时间算法，找到一个有向树分解，区分所有6 k-1阶的有向缠结，这些缠结被一些低阶的分离所分离。作为缠结树的直接应用，分解定理，我们证明了对于每个固定k，存在一个多项式时间算法，该算法在输入G，以及源和汇顶点（s1，t1），...，（sk，tk）上，或者找到一族路径P1，...，Pk，使得每个Pilinksitot和G的每个顶点最多包含在两条路径中，或者确定不存在每个连接sitoti的成对顶点不相交路径的集合。这一结果改进了以前的结果（用“三”代替“二”），并给出已知的硬度结果，我们的结果不能扩展到固定参数的易处理性，也不是完全顶点不相交的有向路径。
The tangle tree-decomposition theorem, proved by Robertson and Seymour in their seminal graph minors series, turns out to be an extremely valuable tool in structural and algorithmic graph theory. In this paper, we prove the analogous result for digraphs, thedirected tangle tree-decomposition theorem. More precisely, we introduce directed tangles and provide a directed tree-decomposition of digraphsGthat distinguishes all maximal directed tangles inG. Furthermore, for any integerk, we construct a directed tree-decomposition that distinguishes all directed tangles of orderk.By relaxing the bound slightly, we can make the previous result algorithmic: for fixedk, we design a polynomial-time algorithm that finds a directed tree-decomposition distinguishing all directed tangles of order 6k–1 separated by some separation of order less thank.As a direct application of the tangle tree-decomposition theorem, we prove that for every fixedkthere is a polynomial-time algorithm which, on inputG, and source and sink vertices (s1,t1),…, (sk, tk), either finds a family of pathsP1,…, Pksuch that eachPilinkssitotiand every vertex ofGis contained in at most two paths, or determines that there is no set of pairwise vertex-disjoint paths each connectingsitoti. This result improves previous results (with “two” replaced by “three”), and given known hardness results, our result cannot be extended to fixed parameter tractability nor fully vertex-disjoint directed paths.