Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity

H.L. Bodlaender, H. Ono, Y. Otachi

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

3 Citaten (Scopus)


The problem MaxW-Light (MaxW-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, MaxW-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 MaxW-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.

Originele taal-2Engels
Pagina's (van-tot)2160-2180
Aantal pagina's21
Nummer van het tijdschrift7
Vroegere onlinedatum5 dec 2017
StatusGepubliceerd - 1 jul 2018

Vingerafdruk Duik in de onderzoeksthema's van 'Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity'. Samen vormen ze een unieke vingerafdruk.

Citeer dit