Weighted proper orientations of trees and graphs of bounded treewidth

DOI10.1016/J.TCS.2018.11.013zbMATH Open1421.68104arXiv1804.03884OpenAlexW2962762415WikidataQ128890262 ScholiaQ128890262MaRDI QIDQ2632010FDOQ2632010

Yanyan Li

Publication date: 17 May 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Given a simple graph $G$, a weight function $w:E(G)ightarrowmathbbNsetminus0$, and an orientation $D$ of $G$, we define $m{u}^{-}(D)=ma{x}_{vinV(G)}{w}_D^{-}(v)$, where $w_D^{-}(v)=su{m}_{uin{N}_D^{-}(v)}w(uv)$. We say that $D$ is a weighted proper orientation of $G$ if $w_D^{-}(u)eq{w}_D^{-}(v)$ whenever $u$ and $v$ are adjacent. We introduce the parameter weighted proper orientation number of $G$, denoted by $overrightarrowchi(G,w)$, which is the minimum, over all weighted proper orientations $D$ of $G$, of $m{u}^{-}(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., $overrightarrowchi(G,w)leqk$?) 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 $sftw$ satisfies $overrightarrowchi(G,w)leqk$, running in time $O(2^{{sftw}^2}cdot{k}^{3sftw}cdotsftwcdotn)$, 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$.

Full work available at URL: https://arxiv.org/abs/1804.03884

zbMATH Keywords

treestreewidthparameterized complexityproper orientation number\(\mathsf{W} [1\)-hardness]minimum maximum indegreeweighted proper orientation number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Title not available (Why is that?)
• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• Which problems have strongly exponential complexity?
• Parameterized Algorithms
• Treewidth. Computations and approximations
• The complexity of the proper orientation number
• Proper orientation of cacti
• On the proper orientation number of bipartite graphs
• Graph minors. III. Planar tree-width
• A \(c^k n\) 5-approximation algorithm for treewidth
• On variations of the subset sum problem
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Proper orientations of planar bipartite graphs
• Ruling out FPT algorithms for weighted coloring on forests
• Weighted Coloring in Trees
• Monadic second order logic on graphs with local cardinality constraints

Cited In (9)

• On the proper orientation number of chordal graphs
• ON SEVERAL PROPERTIES OF A CLASS OF PREFERENTIAL ATTACHMENT TREES—PLANE-ORIENTED RECURSIVE TREES
• Isometric copies of directed trees in orientations of graphs
• Trimming weighted graphs of bounded treewidth
• Note on (semi-)proper orientation of some triangulated planar graphs
• On the semi-proper orientations of graphs
• On the in-out-proper orientations of graphs
• On the proper arc labeling of directed graphs
• Proper orientation, proper biorientation and semi-proper orientation numbers of graphs

This page was built for publication: Weighted proper orientations of trees and graphs of bounded treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2632010)