License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.20
URN: urn:nbn:de:0030-drops-67898
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6789/
Bodlaender, Hans L. ;
Ono, Hirotaka ;
Otachi, Yota
Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity
Abstract
The problem Max W-Light (Max W-Heavy) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at most W (resp. at least W) is maximized. It is known that these problems are NP-hard even for fixed W. For example, Max 0-Light is equivalent to the problem of finding a maximum independent set.
In this paper, we show that for any fixed constant W, Max W-Heavy can be solved in linear time for hereditary graph classes for which treewidth is bounded by a function of degeneracy. We show that such graph classes include chordal graphs, circular-arc graphs, d-trapezoid graphs, chordal bipartite graphs, and graphs of bounded clique-width.
To have a polynomial-time algorithm for Max W-Light, we need an additional condition of a polynomial upper bound on the number of potential maximal cliques to apply the metatheorem by Fomin, Todinca, and Villanger [SIAM J. Comput., 44(1):57-87, 2015]. The aforementioned graph classes, except bounded clique-width graphs, satisfy such a condition. For graphs of bounded clique-width, we present a dynamic programming approach not using the metatheorem to show that it is actually polynomial-time solvable for this graph class too.
We also study the parameterized complexity of the problems and show some tractability and intractability results.
BibTeX - Entry
@InProceedings{bodlaender_et_al:LIPIcs:2016:6789,
author = {Hans L. Bodlaender and Hirotaka Ono and Yota Otachi},
title = {{Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {20:1--20:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-026-2},
ISSN = {1868-8969},
year = {2016},
volume = {64},
editor = {Seok-Hee Hong},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6789},
URN = {urn:nbn:de:0030-drops-67898},
doi = {10.4230/LIPIcs.ISAAC.2016.20},
annote = {Keywords: orientation, graph class, width parameter, parameterized complexity}
}
Keywords: |
|
orientation, graph class, width parameter, parameterized complexity |
Collection: |
|
27th International Symposium on Algorithms and Computation (ISAAC 2016) |
Issue Date: |
|
2016 |
Date of publication: |
|
07.12.2016 |