DAG-width is PSPACE-complete

详细信息    查看全文

• 作者：Saeed Akhoondian Amiri ^{saeed.amiri@tu-berlin.de} ; Stephan Kreutzer ^{stephan.kreutzer@tu-berlin.de} ; Roman Rabinovich ; ^{roman.rabinovich@tu-berlin.de}
• 关键词：Graph searching games ; DAG-width ; PSPACE-complete
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：6 December 2016
• 年：2016
• 卷：655
• 期：part_PA
• 页码：78-89
• 全文大小：437 K
• 卷排序：655

文摘

Berwanger et al. show in [2] that for every graph G of size n and DAG-width k there is a DAG decomposition of width k   and size nO(k)nO(k). They also establish a polynomial time algorithm for deciding whether the DAG-width of a graph is at most a fixed number k. However, if the DAG-width of the graphs is not bounded, such algorithms become exponential. This raises the question whether we can always find a DAG decomposition of size polynomial in n as it is the case for tree width and most other generalisations of tree width similar to DAG-width.In this paper we show that there is an infinite class of graphs such that every DAG decomposition of optimal width has size super-polynomial in n   and, moreover, there is no polynomial size DAG decomposition of width at most k+k1−εk+k1−ε for every ε∈(0,1)ε∈(0,1).In the second part we use our construction to prove that deciding whether the DAG-width of a given graph is at most a given value is PSpace-complete.