2
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – Philip
    Commented Apr 9, 2014 at 11:35
  • $\begingroup$ 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. $\endgroup$
    – Ehsan
    Commented Apr 9, 2014 at 14:18
  • $\begingroup$ 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. $\endgroup$
    – Philip
    Commented Apr 9, 2014 at 14:43
  • $\begingroup$ 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). $\endgroup$
    – Ehsan
    Commented Apr 9, 2014 at 14:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .