2026-07-20T05:59:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6789 2024-03-06T10:38:53Z ddc:004 open_access

Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity Bodlaender, Hans L. Ono, Hirotaka Otachi, Yota orientation graph class width parameter parameterized complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hans L. Bodlaender and Hirotaka Ono and Yota Otachi 2016 Is Part Of LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2016.20 urn:nbn:de:0030-drops-67898 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.20 eng https://creativecommons.org/licenses/by/3.0/legalcode