Unidentified Combinatorial Problem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T20:52:05Z http://mathoverflow.net/feeds/question/56891 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/56891/unidentified-combinatorial-problem Unidentified Combinatorial Problem Aaron Mavrinac 2011-02-28T12:28:51Z 2011-03-02T16:37:36Z <p>Given a (finite, simple, undirected) graph $\mathcal{G} = (V, E)$, an <em>edge binning</em> 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.</p> <p>Is this (or its dual) a well-known problem, or reducible to a well-known problem?</p> <p><strong>Edit:</strong></p> <p>The proper formal problem statement follows (derived from Asahiro 2009), with $d^+(u)$ denoting the outdegree of vertex $u$.</p> <p><em>Minimum Maximum Outdegree</em>: 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)]$.</p> <p>This can equivalently be stated in terms of indegree.</p> <p>Note that Asahiro et al. primarily study the problem involving a weighted graph and weighted outdegree, which is generally NP-hard.</p> http://mathoverflow.net/questions/56891/unidentified-combinatorial-problem/56896#56896 Answer by Gjergji Zaimi for Unidentified Combinatorial Problem Gjergji Zaimi 2011-02-28T13:14:36Z 2011-02-28T13:14:36Z <p>This problem is equivalent to the <em>graph orientation problem</em> also known as the <em>graph balancing problem</em>. 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 <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.3168" rel="nofollow">"Graph Orientation Algorithms to Minimize the Maximum Outdegree"</a>, and <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6V0F-4XC57MY-1&amp;_user=10&amp;_coverDate=12%2F01%2F2009&amp;_rdoc=1&amp;_fmt=high&amp;_orig=gateway&amp;_origin=gateway&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_searchStrId=1658729844&amp;_rerunOrigin=google&amp;_acct=C000050221&amp;_version=1&amp;_urlVersion=0&amp;_userid=10&amp;md5=b4bf2d7406f62116349beae9938fe3b2&amp;searchtype=a" rel="nofollow">"A note on graph balancing problems with restrictions"</a>.</p> http://mathoverflow.net/questions/56891/unidentified-combinatorial-problem/56898#56898 Answer by Fedor Petrov for Unidentified Combinatorial Problem Fedor Petrov 2011-02-28T14:01:12Z 2011-02-28T22:16:43Z <p>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.</p> <p>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 deree of $x$ is less then $d$, then invert all edges on the path from $a$ to $x$. </p> <p>Repeating this stuff we kill all high (more then $d$) out-degree after a fnite number of steps.</p>