Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity

• Published in: Algorithmica 2018-07, Vol.80 (7), p.2160-2180
• Main Authors: Bodlaender, Hans L., Ono, Hirotaka, Otachi, Yota
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Complexity; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Dynamic programming; Graph theory; Graphs; Mathematics of Computing; Parameterization; Polynomials; Special Issue on Algorithms and Computation; Theory of Computation; Upper bounds
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-017-0399-9

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 et al. (SIAM J Comput 44:54–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.