2026-07-23T19:18:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8850 2024-03-06T10:42:48Z ddc:004 open_access

Parameterized Orientable Deletion Hanaka, Tesshu Katsikarelis, Ioannis Lampis, Michael Otachi, Yota Sikora, Florian Graph orientations FPT algorithms Treewidth SETH 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-hard 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+2-epsilon)^{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 W-hard parameterized by the input graph's clique-width. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tesshu Hanaka and Ioannis Katsikarelis and Michael Lampis and Yota Otachi and Florian Sikora 2018 Is Part Of LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2018.24 urn:nbn:de:0030-drops-88506 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.24 eng https://creativecommons.org/licenses/by/3.0/legalcode