TY - GEN
T1 - Degree-constrained orientation of maximum satisfaction
T2 - 27th International Symposium on Algorithms and Computation, ISAAC 2016
AU - Bodlaender, Hans L.
AU - Ono, Hirotaka
AU - Otachi, Yota
PY - 2016/12/1
Y1 - 2016/12/1
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 problems 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 problems and show some tractability and intractability results.
KW - Graph class
KW - Orientation
KW - Parameterized complexity
KW - Width parameter
UR - http://www.scopus.com/inward/record.url?scp=85010723624&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ISAAC.2016.20
DO - 10.4230/LIPIcs.ISAAC.2016.20
M3 - Conference contribution
AN - SCOPUS:85010723624
T3 - Leibniz International Proceedings in Informatics
SP - 20:1-20:12
BT - 27th International Symposium on Algorithms and Computation (ISAAC 2016)
A2 - Hong, Seok-Hee
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 12 December 2016 through 14 December 2016
ER -