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

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

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

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 pr oblems and show some tractability and intractability results.
Original languageEnglish
Pages (from-to)2160-2180
JournalAlgorithmica
Volume80
Issue number7
Early online date5 Dec 2017
DOIs
Publication statusPublished - 2018

Fingerprint

Parameterized Complexity
Graph Classes
Clique-width
Polynomials
Graph in graph theory
Trapezoid Graph
Chordal Bipartite Graphs
Circular-arc Graphs
Dynamic programming
Maximal Clique
Maximum Independent Set
Treewidth
Chordal Graphs
Tractability
Computational complexity
Degeneracy
Undirected Graph
Polynomial-time Algorithm
Dynamic Programming
Assign

Keywords

  • Graph class
  • Orientation
  • Parameterized complexity
  • Width parameter

Cite this

@article{810c1e8081b04f2fa546ebed6a7f1bce,
title = "Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity",
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 pr oblems and show some tractability and intractability results.",
keywords = "Graph class, Orientation, Parameterized complexity, Width parameter",
author = "H.L. Bodlaender and H. Ono and Y. Otachi",
year = "2018",
doi = "10.1007/s00453-017-0399-9",
language = "English",
volume = "80",
pages = "2160--2180",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer",
number = "7",

}

Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity. / Bodlaender, H.L.; Ono, H.; Otachi, Y.

In: Algorithmica, Vol. 80, No. 7, 2018, p. 2160-2180.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Bodlaender, H.L.

AU - Ono, H.

AU - Otachi, Y.

PY - 2018

Y1 - 2018

N2 - 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 pr oblems and show some tractability and intractability results.

AB - 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 pr oblems and show some tractability and intractability results.

KW - Graph class

KW - Orientation

KW - Parameterized complexity

KW - Width parameter

UR - http://www.mendeley.com/research/degreeconstrained-orientation-maximum-satisfaction-graph-classes-parameterized-complexity

U2 - 10.1007/s00453-017-0399-9

DO - 10.1007/s00453-017-0399-9

M3 - Article

VL - 80

SP - 2160

EP - 2180

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 7

ER -