Abstract
A graph is dorientable if its edges can be oriented so that the maximum indegree of the resulting digraph is at most d. dorientability is a wellstudied concept with close connections to fundamental graphtheoretic notions and applications as a load balancing problem. In this paper we consider the dOrientable Deletion problem: given a graph G=(V,E), delete the minimum number of vertices to make G dorientable. 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 ninapproximable 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 Whard for each of the parameters d,k separately.
 We show that, under the SETH, for all d,epsilon, the problem does not admit a (d+2epsilon)^{tw}, algorithm where 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 Whard parameterized by the input graph's cliquewidth. Complementing this, we provide an algorithm running in time d^{O(d * cw)}, showing that the problem is FPT by d+cw, and improving the previously best know algorithm for this case.
BibTeX  Entry
@InProceedings{hanaka_et_al:LIPIcs:2018:8850,
author = {Tesshu Hanaka and Ioannis Katsikarelis and Michael Lampis and Yota Otachi and Florian Sikora},
title = {{Parameterized Orientable Deletion}},
booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
pages = {24:124:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770682},
ISSN = {18688969},
year = {2018},
volume = {101},
editor = {David Eppstein},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8850},
URN = {urn:nbn:de:0030drops88506},
doi = {10.4230/LIPIcs.SWAT.2018.24},
annote = {Keywords: Graph orientations, FPT algorithms, Treewidth, SETH}
}
Keywords: 

Graph orientations, FPT algorithms, Treewidth, SETH 
Collection: 

16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) 
Issue Date: 

2018 
Date of publication: 

04.06.2018 