Time complexity of n-vertex subgraph enumeration?

It looks like the algorithm has a bug because after the recursive call, it is possible that nodes that appear in combination also appear in connectedSoFar, so the check that connectedSoFar.size() + combination.size() equals n seems incorrect, as it might count a node twice.

It looks like the algorithm has a bug because after the recursive call, it is possible that nodes that appear in combination also appear in connectedSoFar, so the check that connectedSoFar.size() + combination.size() equals n seems incorrect, as it might count a node twice. Anyway, otherwise to analyze the algorithm, you have 2d elements in the powerset; every operation in the "elase" branch takes O(n) time because connectedSoFar and combination together can't contain more than n nodes. Adding elements to connectedSoFar then takes O(n log n) time because |combination| ≤ n.

The iteration over combination nodes happens O(n) times; within it there is O(d) operation to construct the hash set k and then recursive call. Denote then the complexity of the procedure by X(n) where n is the parameter. You have X(n) ~ 2d (n + n log n + n (d + X(n - 1))) because in the recursive call you have added at least one vertex to the graph so in practice the parameter n in the recursive call decreases virtually by at least one.

Simplify this to X(n) ~ 2d (n (1 + d + log n + X(n - 1))) because d is constant, mark D = 2d, eliminate the constant 1, and you get X(n) ~ D n (d + log n + X(n - 1)) which you can analyze as X(n) ~ (2d)n n! (d + log n) showing that your algorithm is really a time hog :).

Thanks a lot for this in-depth analysis! Looks like it really is a time hog, luckily I don't need it to be very efficient - but perhaps someone here can point me to a better way of doing this. Thanks again.

– Nejc Saje May 29 at 21:02.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.