A note on the parameterized complexity of unordered maximum tree orientation

详细信息	查看全文 | 推荐本文 |

• 作者：Sebastian Bö ; cker^a ; ^{sebastian.boecker@uni-jena.de} ; Peter Damaschke^b ; ^{ptr@chalmers.se}
• 关键词：Graph orientation ; Directed path ; Parameterized reduction ; Bipartization
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 期刊代码：46_0166218x
• 类别：cp
• 出版时间：July, 2012
• 卷：160
• 期：10-11
• 页码：1634-1638
• 文件大小：204 K

摘要

In the Unordered Maximum Tree Orientation problem, a set of paths in a tree and a parameter is given, and we want to orient the edges in the tree such that all but at most paths in become directed paths. This is a more difficult variant of a well-studied problem in computational biology where the directions of paths in are already given. We show that the parameterized complexity of the unordered version is between Edge Bipartization and Vertex Bipartization, and we give a characterization of orientable path sets in trees by forbidden substructures, which are cycles of a certain kind.