3
$\begingroup$

I have graph creation problem.

Given a set of nodes of graph, and node constraints such as given every node's number of neighbors (degree). I am also provided with the total number of triangles in the graph. Given the above constraints ($n+1$), I have to generate a graph that satisfies all the constraints.

I know that given nodes' degrees, it is possible to construct using Havel–Hakimi algorithm a graph satisfying node degrees. But I am not sure how to fulfill the total triangle count constraint and if it makes the problem NP-hard.

$\endgroup$
  • $\begingroup$ Are nodes labelled? In other words, is the condition like a graph of three nodes $A,B,C$ and $B$ where the degree of $A$ is 1, degree of $B$ is 1 and the degree of $C$ is 0? Or is it like a graph of three nodes $A,B,C$ where the multi-set of degrees of $A,B,C$ is $\{0,1, 1\}$? $\endgroup$ – Apass.Jack Jan 17 at 20:08
  • $\begingroup$ @Apass.Jack I don't see how that makes the problem any different. Once you have a solution you can relabel the nodes any way you like. $\endgroup$ – Tom van der Zanden Jan 17 at 20:39
  • $\begingroup$ @TomvanderZanden Thanks. I lost my mind for a moment. $\endgroup$ – Apass.Jack Jan 17 at 21:12
  • 1
    $\begingroup$ I was thinking of simplifying the problem of creating a graph to creating a graph maximum possibles triangles. The addition of individual edge acts a value by increasing the number of triangles which turns out to be a supermodular function with obvious degree constraints. Is there any supermodular function that this problem can be reduced to? $\endgroup$ – learner Jan 18 at 0:19
0
$\begingroup$

This is just a begining of reflexion. I hope it will help. This is not a solution for the very general case but some points that can reduce the problem.

If you consider triangles as unique 3-cliques, you know how many triangles are provided by a k-clique:

  • 3-clique : 1 triangle
  • 4-clique : 4 triangles
  • 5-clique : 10 triangles
  • k-clique : C(k, 3) triangles

Thus the number of triangles you have to provide is a combination of these numbers: N = 1*a + 4*b + 10*c ...

You also know that building a clique requires nodes with sufficient neighboors. A k-clique requires k nodes having k-1 edges. And any node with only one edge cannot create any triangle.

On a short example : 10 nodes with (5, 5, 4, 4, 3, 3, 2, 2, 1, 1) edges. A 5-clique is not possible. I think this can do up to 12 triangles with 3 different 4 cliques (5, 5, 4a, 4b), (5, 5, 4a, 3a), (5, 5, 4b, 3b). The remaining (2, 2, 1, 1) cannot provide any triangle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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