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

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

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)2160-2180
Number of pages21
JournalAlgorithmica
Volume80
Issue number7
Early online date5 Dec 2017
DOIs
Publication statusPublished - 1 Jul 2018

Keywords

  • Graph class
  • Orientation
  • Parameterized complexity
  • Width parameter

Fingerprint Dive into the research topics of 'Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity'. Together they form a unique fingerprint.

Cite this