Parameterized Orientable Deletion

Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, Florian Sikora

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

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 Gd-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, ϵ, the problem does not admit a O((d+ 2 - ϵ) tw) -time 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[1]-hard parameterized by the input graph’s clique-width. Complementing this, we provide an algorithm running in time O(dO ( d · cw )) , showing that the problem is FPT by d+ cw , and improving the previously best known algorithm for this case.

Original languageEnglish
Pages (from-to)1909-1938
Number of pages30
JournalAlgorithmica
Volume82
Issue number7
DOIs
Publication statusPublished - Jul 1 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Parameterized Orientable Deletion'. Together they form a unique fingerprint.

Cite this