Weighted proper orientations of trees and graphs of bounded treewidth
share
Given a simple graph G, a weight function w:E(G)→N∖{0}, and an orientation D of G, we define μ^-(D) = _v ∈ V(G) w_D^-(v), where w^-_D(v) = ∑_u∈ N_D^-(v)w(uv). We say that D is a weighted proper orientation of G if w^-_D(u) ≠ w^-_D(v) whenever u and v are adjacent. We introduce the parameter weighted proper orientation number of G, denoted by χ(G,w), which is the minimum, over all weighted proper orientations D of G, of μ^-(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., χ(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 χ(G,w) ≤ k, running in time O(2^ tw^2· k^3 tw· tw· n), and we complement this result by showing that the problem is W[1]-hard on general graphs parameterized by the treewidth of G, even if the weights are polynomial in n.
READ FULL TEXT