Graph Orientations Optimizing the Number of Light or Heavy Vertices

Authors

  • Yuichi Asahiro
  • Jesper Jansson
  • Eiji Miyano
  • Hirotaka Ono

DOI:

https://doi.org/10.7155/jgaa.00371

Keywords:

graph orientation , maximum independent set , minimum vertex cover , edge packing , maximum flow

Abstract

This paper introduces four graph orientation problems named MAXIMIZE W-LIGHT, MINIMIZE W-LIGHT, MAXIMIZE W-HEAVY, and MINIMIZE W-HEAVY, where W can be any fixed non-negative integer. In each problem, the input is an undirected, unweighted graph G and the objective is to assign a direction to every edge in G so that the number of vertices with outdegree at most W or at least W in the resulting directed graph is maximized or minimized. A number of results on the computational complexity and polynomial-time approximability of these problems for different values of W and various special classes of graphs are derived. In particular, it is shown that MAXIMIZE 0-LIGHT and MINIMIZE 1-HEAVY are identical to MAXIMUM INDEPENDENT SET and MINIMUM VERTEX COVER, respectively, so by allowing the value of W to vary, we obtain a new generalization of the two latter problems.

Downloads

Download data is not yet available.

Downloads

Published

2024-03-16

How to Cite

Asahiro, Y., Jansson, J., Miyano, E., & Ono, H. (2024). Graph Orientations Optimizing the Number of Light or Heavy Vertices. Journal of Graph Algorithms and Applications, 19(1), 441–465. https://doi.org/10.7155/jgaa.00371

Issue

Section

Articles

Categories