### Abstract

Original language | English |
---|---|

Pages (from-to) | 2160-2180 |

Journal | Algorithmica |

Volume | 80 |

Issue number | 7 |

Early online date | 5 Dec 2017 |

DOIs | |

Publication status | Published - 2018 |

### Fingerprint

### Keywords

- Graph class
- Orientation
- Parameterized complexity
- Width parameter

### Cite this

*Algorithmica*,

*80*(7), 2160-2180. https://doi.org/10.1007/s00453-017-0399-9

}

*Algorithmica*, vol. 80, no. 7, pp. 2160-2180. https://doi.org/10.1007/s00453-017-0399-9

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

Research output: Contribution to journal › Article › Academic › peer-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 -