Parameterized Orientable Deletion

DOI DOI DOI 機関リポジトリ (HANDLE) PDF ほか1件をすべて表示 一部だけ表示 参考文献23件 オープンアクセス

この論文をさがす

説明

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-ε)^<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.

収録刊行物

参考文献 (23)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ