6
$\begingroup$

Given a (finite, simple, undirected) graph $\mathcal{G} = (V, E)$, an edge binning associates each $e_{ij} \in E$ with one or the other of its vertices $v_i, v_j \in V$. Let $c_i$ be the number of edges associated with vertex $v_i$ in a given edge binning. Find an edge binning such that $\max_{v_i \in V}(c_i)$ is minimized.

Is this (or its dual) a well-known problem, or reducible to a well-known problem?

Edit:

The proper formal problem statement follows (derived from Asahiro 2009), with $d^+(u)$ denoting the outdegree of vertex $u$.

Minimum Maximum Outdegree: Given a finite, simple, undirected graph $\mathcal{G}= (V, E)$, find an orientation $\Lambda$ of $\mathcal{G}$ that minimizes $\max_{u \in V}[d^+_\Lambda(u)]$.

This can equivalently be stated in terms of indegree.

Note that Asahiro et al. primarily study the problem involving a weighted graph and weighted outdegree, which is generally NP-hard.

$\endgroup$
5
  • $\begingroup$ V. Venkateswaran, "Minimizing Maximum Indegree," Disc. Appl. Math., vol. 143, 2004, pp. 374-378. $\endgroup$ Mar 2, 2011 at 16:25
  • $\begingroup$ Y. Asahiro, E. Miyano, H. Ono, and K. Zenmyo, "Graph Orientation Algorithms To Minimize the Maximum Outdegree," Int. J. Found. Comput. Sci., vol. 18, 2007, pp. 197-215. $\endgroup$ Mar 2, 2011 at 16:25
  • $\begingroup$ Y. Asahiro, J. Jansson, E. Miyano, H. Ono, and K. Zenmyo, "Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree," J. Comb. Optim., Nov. 2009, pp. 1-19. $\endgroup$ Mar 2, 2011 at 16:25
  • $\begingroup$ K. Lee, J. Leung, and M. L. Pinedo, "A Note on Graph Balancing Problems with Restrictions," Info. Proc. Lett., vol. 110, no. 1, 2009, pp. 24-29. $\endgroup$ Mar 2, 2011 at 16:26
  • $\begingroup$ This is also a variation of unrelated parallel machine scheduling, specifically the $P|M_j, |M_j| \leq 2|C_{\max}$ problem (see M. Pinedo, Scheduling: Theory, Algorithms, and Systems, Second Edition, Prentice-Hall, 2002). $\endgroup$ Mar 2, 2011 at 16:29

3 Answers 3

10
$\begingroup$

This problem is equivalent to the graph orientation problem also known as the graph balancing problem. One is given an undirected graph and has to give an orientation of the edges which minimizes the maximum out-degree. If this value is $k$, then the graph is called $k$-orientable. Here are some articles on the topic "Graph Orientation Algorithms to Minimize the Maximum Outdegree", and "A note on graph balancing problems with restrictions".

$\endgroup$
1
8
$\begingroup$

Let me also state an explicit criterion of the existence of orientation with out-degrees at most $d$: any induced subgraph on some, say, $k$ vertices contains at most $dk$ edges. This is clearly necessary, and the proof that it is sufficient is not hard: orient edges arbitrarily and consider the following procedure.

If out-degree of some vertex $a$ is at least $d+1$, then consider the set of vertices $x$, for which there exist oriented path from $a$. If all out-degrees of such vertices are at least $d$, then the set of them contradicts to our assumption. If degree of $x$ is less then $d$, then invert all edges on the path from $a$ to $x$.

Repeating this stuff we kill all high (more then $d$) out-degree after a finite number of steps.

$\endgroup$
2
  • $\begingroup$ This is, of course, the best answer. $\endgroup$
    – Gil Kalai
    Feb 28, 2011 at 16:46
  • $\begingroup$ Reminds me of Hall's Marriage Theorem. Can one prove one from the other? $\endgroup$ Feb 28, 2011 at 22:31
1
$\begingroup$

The problem of finding the smallest maximum indegree (or outdegree) is equivalent to finding the smallest number of pseudoforests to cover the graph, a.k.a. pseudoarboricity. For a polynomial-time matroid-based algorithm (also for the arboricity), see

Harold N. Gabow, Herbert H. Westermann. Forests, Frames, and Games: Algorithms for Matroid Sums and Applications. Algorithmica 7(5&6): 465-497 (1992)

A partition into p pseudoforests can be converted into a p-orientation, and vice versa, in linear time. For this and an approximation scheme, see

Lukasz Kowalik. Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures. ISAAC 2006: 557-566

[Note that Lemma 2 in this paper is insufficiently stated for the approximation scheme to work, but this can be easily repaired.]

The relaxation of the problem (where every edge can be fractionally assigned to its two ends) is dual to the densest subgraph problem. Moreover, if you round up the optimum solution of the relaxation, you have exactly the pseudoarboricity. For a list of references as well as a combination of the Kowalik and Gabow-Westermann algorithms and experimental results, see

Markus Blumenstock. Fast Algorithms for Pseudoarboricity. ALENEX 2016: 113-126

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.