Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The general Degree Sequence Problem asks for a simple undirected graph (that is a graph without self-loops and with no more than one edge between any pair of nodes) for which it holds that the degrees of the nodes are $D = (d_1, d_2, ..., d_n)$.

From the Erdős–Gallai theorem it follows that such a graph can be found in polynomial time. With some minor modifications it is also possible to ask for a simple undirected bi-partite graph for which it holds that the degrees of the nodes are $D_1 = (d_{1_1}, d_{1_2}, ..., d_{1_n})$ resp. $D_2 = (d_{2_1}, d_{2_2}, ..., d_{2_n})$.

I am interested in a more general case where the graph in question is a k-partite graph and the sets $D_1, D_2, ... D_k$ are given.

Is anybody aware of any results on that? I would suspect the problem to be NP-Hard but i don't (yet) have any proof.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

The problem a hand can be modeled as a restricted degree sequence problem as explained in that paper: http://arxiv.org/pdf/1301.7523v3.pdf

Or as a Degree Sequence Problem with Associated Costs as in http://research.microsoft.com/en-us/um/people/nvishno/site/publications_files/mvdeg02.pdf

Unfortunately, both problems require finding a perfect matching on a graph with $\mathcal{O}(n^2)$ nodes which is impractical.

share|improve this answer

The problem, as I understand it, is not NP-hard. Assuming that the given partition and degree distribution is feasible, a greedy algorithm will give you a $k$-partite graph.

Here is the idea:

Notation :

  • $E(G)$ and $V(G)$ are the edge-set and vertex-set of the graph $G$.
  • $e:v - u$ means $e \in E(G)$ if $v \neq u \in V(G)$.
  • for $v\in V(G)$, $P(v)$ is the largest set such that $v \in P(v)$ and for $u \not \in P(v)$, $e:v-u \not \in E(G)$ (a parition of vertices).

Observation : Let $G$ be a simple $k$-partite graph. Then

  1. Swapping the end-points of any two-edges maintains the degree distribution
  2. If the swap does not introduce self-loops, the simplicity is maintained.
  3. If the new edges are not within the same partition ,the graph stays $k$-paritite.

Note:

  1. Swapping the end-points of edges does not change the number of edges at the corresponding vertices
  2. If there no self-loops then the graph will be simple.
  3. Again, by definition $G$ is $k$-partite and we are assuming the swap is not violating the condition.

Now the following algorithm will find you a $k$-partitte graph based on the provided distribution of degrees

Algorithm :

  • Let $d = [d_1, d_2, ...., d_n]$ be the degree distribution vector
  • while $\exists \;i$ such that $d[i] > 0$:
    • Find $j$ such that $d[j] > 0$ and $v_j \not \in P(v_i)$. If no such vertex exists, return FALSE
    • Add edge $e:v_i - v_j$ to $E(G)$ and let $d[i] \leftarrow d[i] - 1$ and $d[j] \leftarrow d[j] - 1$ by one.
  • return TRUE.

*The algorithm above does not work. It seems to work for the case where the given partition is the smallest.

share|improve this answer
    
Your proof does not show the correctness of your proposed algorithm. In addition, your algorithm is wrong. Suppose you have $D_1 = (1,1)$, $D_2 = (1,1)$, $D_3 = (1,1)$. Your algorithm would create two edges between partitions 1 and 2, leaving partition 3 with no edges to other partitions. As $D_3$ would not be satisfied, your algorithm would return FALSE, although a 3-partite graph exists which satisfies $D_1$, $D_2$, and $D_3$. –  Philip Apr 9 at 11:35
    
You are right about the algorithm returning false. But the problem is that the degree distribution you provided, relates to a bi-partite graph, not a 3-partite, unless I got it wrong again. Did you mean a grpah like this: $v_i, i \in \{1, 2, 3, 4, 5, 6\}$ where $P(v_1) = \{v_1, v_2\}, P(v_3) = \{v_3, v_4\}, P(v_5) = \{v_5, v_6\}$? In such a case, the only graphs satisfying this [that I could think of] seem to be isomorphic to this: $e_1: v_1 - v_3, e_2:v_2 - v_6, e_3: v_4-v_5$. In such a case though, the graph is actually bi-partite. –  Ehsan Apr 9 at 14:18
    
The resulting graph would be both 3-partite and 2-partite. The definition of a k-partite graph is that it can be split up into k partitions of nodes where there is no edge between any two nodes of the same partition. So it is not required that it exists at least one edge between every pair of partitions. –  Philip Apr 9 at 14:43
    
In that case, the comment above is wrong. Also, given this example, it might seem easy that if we could find the min $k$ for $k$-partite graph then we could draw it. But that won't work either and finding min. $k$ is I guess NP-hard (vertex coloring reduction). –  Ehsan Apr 9 at 14:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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