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

Hans L. Bodlaender, Hirotaka Ono, Yota Otachi

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

126 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publication27th International Symposium on Algorithms and Computation (ISAAC 2016), December 12-14, 2016, Sidney, Australia
EditorsSeol-Hee Hong
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages12
ISBN (Print)978-3-95977-026-2
DOIs
Publication statusPublished - 2016
Event27th International Symposium on Algorithms and Computation (ISAAC 2016) - Sydney, Australia
Duration: 12 Dec 201614 Dec 2016
Conference number: 27
http://rp-www.cs.usyd.edu.au/~visual/isaac2016/

Publication series

NameLIPICS
Volume64
ISSN (Electronic)1868-8969

Conference

Conference27th International Symposium on Algorithms and Computation (ISAAC 2016)
Abbreviated titleISAAC 2016
CountryAustralia
CitySydney
Period12/12/1614/12/16
Internet address

Keywords

  • orientation, graph class, width parameter, parameterized complexity

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