Abstract
The problem Max WLight (Max WHeavy) 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 NPhard even for fixed W. For example, Max 0Light is equivalent to the problem of finding a maximum independent set.
In this paper, we show that for any fixed constant W, Max WHeavy 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, circulararc graphs, dtrapezoid graphs, chordal bipartite graphs, and graphs of bounded cliquewidth.
To have a polynomialtime algorithm for Max WLight, 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):5787, 2015]. The aforementioned graph classes, except bounded cliquewidth graphs, satisfy such a condition. For graphs of bounded cliquewidth, we present a dynamic programming approach not using the metatheorem to show that it is actually polynomialtime 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 = {{DegreeConstrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {20:120:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770262},
ISSN = {18688969},
year = {2016},
volume = {64},
editor = {SeokHee Hong},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6789},
URN = {urn:nbn:de:0030drops67898},
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 