Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity
Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity
复制标题
最大满意度的度约束方向：图类和参数化复杂性
DOI：
10.1007/s00453-017-0399-9
复制
发表时间：
2018
期刊：
影响因子：
1.1
通讯作者：
Otachi Yota
中科院分区：
文献类型：
--
作者：
Bodlaender Hans L.;Ono Hirotaka;Otachi Yota
无向图的MaxW-Light（MaxW-Heavy）问题是指给每一条边指定一个方向，使得出度的顶点数至多为W（分别为.至少W）被最大化。已知这些问题即使对于固定W也是NP难的。例如，Max 0-Light等价于寻找最大独立集的问题。本文证明了对于任意固定的常数W，对于树宽由退化函数限定的遗传图类，MaxW-Heavy可以在线性时间内求解。我们表明，这样的图类包括弦图，圆弧图，d-梯形图，弦二部图，和有界的cash宽度的图形。为了具有MaxW-Light的多项式时间算法，我们需要关于潜在最大团的数量的多项式上限的附加条件，以应用Fomin等人的元定理（SIAM J Comput 44：54-87，2015）。上述的图类，除了有界宽度图，满足这样的条件。对于有限宽度的图，我们提出了一个动态规划方法，不使用元定理来证明它实际上是多项式时间可解的这类图。我们还研究了问题的参数化复杂性，并给出了一些易处理性和难处理性的结果。
The problemMaxW-Light(MaxW-Heavy) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at mostW(resp. at leastW) is maximized. It is known that these problems are NP-hard even for fixedW. For example,Max 0-Lightis equivalent to the problem of finding a maximum independent set. In this paper, we show that for any fixed constantW,MaxW-Heavycan 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 forMaxW-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.