Weighted proper orientations of trees and graphs of bounded treewidth

作     者：Araujo, Julio Sales, Claudia Linhares Sau, Ignasi Silva, Ana 

作者机构：Univ Fed Ceara Dept Matemat Fortaleza Ceara Brazil Univ Fed Ceara Dept Comp Fortaleza Ceara Brazil Univ Montpellier CNRS LIRMM Montpellier France 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2019年第771卷

页      面：39-48页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：French grant DEMOGRAPH [ANR-16-CE40-0028] French grant ESIGMA [ANR-17-CE23-0010] CNPq-Brazil [459466/2014-3, 310234/2015-8, 401519/2016-3] 

主　　题：Proper orientation number Weighted proper orientation number Minimum maximum indegree Trees Treewidth Parameterized complexity W[1]-hardness 

摘      要：Given a simple graph G, a weight function w : E (G) - N \ (0), and an orientation D of G, we define mu(-)(D) = max(vev(G)) w(D)(-)(v), where w(D)(-)(v) = Sigma(-)(mu is an element of ND)(v)w(uv). We say that D is a weighted proper orientation of G if w(D)(-)(u) not equal w(D)(-),(v) whenever u and v are adjacent. We introduce the parameter weighted proper orientation number of G, denoted by (X) over right arrow (G, w), which is the minimum, over all weighted proper orientations D of G, of mu(-) (D). When all the weights are equal to 1, this parameter is equal to the proper orientation number of G, which has been object of recent studies and whose determination is NP -hard in general, but polynomial -time solvable on trees. Here, we prove that the equivalent decision problem of the weighted proper orientation number (i.e., (X) over right arrow (G, w) = k?) is (weakly) NP -complete on trees but can be solved by a pseudo -polynomial time algorithm whose running time depends on k. Furthermore, we present a dynamic programming algorithm to determine whether a general graph G on n vertices and treewidth at most tw satisfies (X) over right arrow (G, w) = k, running in time O(2t(w2) . k(3tw) . tw n), and we complement this result by showing that the problem is W[11 -hard on general graphs parameterized by the treewidth of G, even if the weights are polynomial in n. (C) 2018 Elsevier B.V. All rights reserved.