Mendeley出力
＜会議発表論文＞
Parameterized Orientable Deletion
| 作成者 | |
|---|---|
| 本文言語 | |
| 出版者 | |
| 発行日 | |
| 収録物名 | |
| 巻 | |
| 開始ページ | |
| 終了ページ | |
| 会議情報 | |
| 出版タイプ | |
| アクセス権 | |
| 権利関係 | |
| 権利関係 | |
| 関連DOI | |
| 関連DOI | |
| 関連URI | |
| 関連HDL | |
| 関連ISBN | |
| 関連HDL | |
| 関連情報 | |
| 概要 | 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 fundamenta...l 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.続きを見る |
詳細
| EISSN | |
|---|---|
| レコードID | |
| 関連ISBN | |
| 主題 | |
| 注記 | |
| 助成情報 | |
| 登録日 | 2025.04.25 |
| 更新日 | 2025.04.28 |