Parameterized Orientable Deletion
Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, Florian Sikora · Algorithmica · 2020
A graph is d -orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most d . d -orientability is a well-studied concept with close connections to fundamental graph-theoretic notions and applications as a load balancing problem. In this paper we consider the \(d\) - Orientable Deletion problem: given a graph \(G=(V,E)\) , delete the minimum number of vertices to make G d -orientable. We contribute a number of results that improve the state of the art on this problem. Specifically: We show that the problem is W[2]-hard and \(\log n\) -inapproximable with respect to k , the number of deleted vertices. This closes the gap in the problem’s approximability. We completely characterize the parameterized complexity of the problem on chordal graphs: it is FPT parameterized by \(d+k\) , but W[1]-hard by d and W[2]-hard by k alone. We show that, under the SETH, for all \(d,\epsilon\) , the problem does not admit a \(O^*((d+2-\epsilon )^{\text {tw}})\) -time algorithm where \(\text {tw}\) is the graph’s treewidth, resolving as a special case an open problem on the complexity of PseudoForest Deletion . We show that the problem is W[1]-hard parameterized by the input graph’s clique-width. Complementing this, we provide an algorithm running in time \(O^*(d^{O(d\cdot \text {cw})})\) , showing that the problem is FPT by \(d+\text {cw}\) , and improving the previously best known algorithm for this case.