Weighted proper orientations of trees and graphs of bounded treewidth

DOI10.1016/J.TCS.2018.11.013MaRDI QIDQ2632010zbMATHOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 17 May 2019

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

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)

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$.

Recommendations

• On the semi-proper orientations of graphs
• Weighted coloring in trees
• Weighted coloring in trees
• On the proper orientation number of chordal graphs
• The complexity of the proper orientation number

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A \(c^k n\) 5-approximation algorithm for treewidth
• Fundamentals of parameterized complexity
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Graph minors. III. Planar tree-width
• Graph theory
• Monadic second order logic on graphs with local cardinality constraints
• On the proper orientation number of bipartite graphs
• On variations of the subset sum problem
• Parameterized algorithms
• Proper orientation of cacti
• Proper orientations of planar bipartite graphs
• Reducibility among combinatorial problems
• The complexity of the proper orientation number
• Treewidth. Computations and approximations
• Weighted coloring in trees
• Which problems have strongly exponential complexity?

Cited in

(9)

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

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)