Graph Realization Problem

Question

Given degrees of nodes, is it possible to construct a graph with those degrees, and if yes devise the algorithm?

I know of Handshaking Lemma that describes my problem, and another algorithm for it as follows:

The following algorithm decides if a simple graph can be constructed with given node degrees:

1. Sort the degrees in descending order.

2. If the first degree is $0$ (i.e. all degrees are $0$), then obviously such a graph can be formed (no edges) and you are done.

3. If the first degree has value $d$, then the following $d$ degrees must be greater than $0$. If not, you are done: no such graph can be formed.

4. Take away the first degree (value $d$) and reduce the following $d$ degrees by one (i.e. draw the requested number of edges from the node with highest degree to the nodes with highest degrees among the remaining ones), then continue with step 1 (with now one node less).

This algorithm takes $O(n^2 \log n)$ time where $n$ is number of nodes. Hence computationally very expensive!! Is there an algorithm which solves this problem in $O(n\log n)$ or $O(n)$??

NOTE:Parallel edges and loops are not allowed

Answer 1

Please look into the Erdos-Gallai Theorem. I am not sure of its complexity though, seems $\mathcal O(n^2)$ which all traditional algorithms for recognising graphic degree sequences are.

UPDATE:

Found this paper. Not sure of its correctness, but claims to have a linear algorithm.

Answer 2

We can sort the sequence into bags in $\mathcal O(n \log n)$ and label the bags according to their size:

maxdeg = max(deg)
bags[] = new int[maxdeg] // bags[i] = "number of vertices of degree i"
for i=maxdeg:-1:1 // O(max(deg))
    bags[i] = bags[i] % (i + 1) // remove fully connected subgraphs
    if (bags[i] == 0) continue
    removed = bags[i] - 1 // bags[i] <= i is guaranteed here
    tbags[i-1] = bags[i]
    bags[i] = 0
    if (i > 1)
        j = i-1
        while (removed < i) // At most O(i)
            r = min(bags[j], i-removed)
            removed += r
            bags[j] -= r
            tbags[j-1] = r
            j--
        for k=j:i-1
            bags[k] += tbags[k] // Put back linked vertices with degree reduced by 1
    else
        if isodd(bags[i]) return false
        return true
end

Not sure about worst-case behavior, but this should do in $\mathcal O(n \log n)$ under normal conditions (I expect not having to run through all j every time) A worst-case sequence is bags = ones(maxdeg) and will force $\mathcal O(n^2)$ time unfortunately :(

---

Explanation of the idea:
Storing the number of vertices of degree $x$ saves us from sorting it over and over again. The $i$ highest-degree vertices are found by looking into the highest bags and adding up how many can be removed (removed, r from bag j). Also, when we must visit multiple bags, we ensure that the visitied bags are emptied completely so we wont revisit them. After collecting and removing all vertices, we put every vertex back into the next lowest bag. To prevent cascading a complete graph, bags[i]>=i+1 implies we completely connect $i+1$ degree-$i$ vertices among each other and remove them from the test.

Answer 3

The degree sequence problem asks essentially this, does there exist a graph that achieves the specified degrees of nodes? Also called the graph realization problem.

The Havel-Hakimi algorithm constructs a solution, if one exists, recursively. It has complexity $\Theta(n^2)$, but provides at most a single solution.

The Erdős–Gallai theorem can be recast, according to recent results by Tripathi, Venugopalanb, and West, as a construction of $O(n^3)$ worst case running time: "A short constructive proof of the Erdős-Gallai characterization of graphic lists", Discrete Math. 310, (4) (2010) 833–834.

More recently the Erdős-Gallai Linear algorithm was proposed by Iványi, Lucz, Móri, and Sótér (2011) claimed to have $\Theta(n)$ worst case running time.