A note on the parameterized complexity of unordered maximum tree orientation

作者：Boecker Sebastian; Damaschke Peter^*

来源：Discrete Applied Mathematics, 2012, 160(10-11): 1634-1638.

DOI：10.1016/j.dam.2012.02.017

• Graph orientation
• Directed path
• Parameterized reduction
• Bipartization

In the UNORDERED MAXIMUM TREE ORIENTATION problem, a set P of paths in a tree and a parameter k is given, and we want to orient the edges in the tree such that all but at most k paths in P become directed paths. This is a more difficult variant of a well-studied problem in computational biology where the directions of paths in P 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.