A note on the parameterized complexity of unordered maximum tree orientation

In the Unordered Maximum Tree Orientation problem, a set PP of paths in a tree and a parameter kk is given, and we want to orient the edges in the tree such that all but at most kk paths in PP become directed paths. This is a more difficult variant of a well-studied problem in computational biology where the directions of paths in PP 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.