I'm reading papers on algorithms of maximum independent problem and the basic recursive branching rules is as follows:

Let $G(V,E)$ be an $n$-node undirected, simple graph without loops, and $\alpha(G)$ be the cardinality of an maximum independent set of $G$. If $G$ is empty, output $\alpha(G)=0$(base instance). Otherwise, choose any node $v$ of maximum degree, and output $$\alpha(G)=max\{\alpha(G-\{v\}),1+\alpha(G-N[v])\}$$ where $N[v]$ is the set of $v$ and its neighbors.

The running time of the above algorithm can be bounded as follows:

The recursive calls induce a search tree, where the root is the input instance and the leaves are base instances. Observe that each branching step can be performed in polynomial time(excluding the time needed to solve subproblems). Therefore, the running time of the algorithm is bounded by $O^*(L(n))$, where $L(n)$ is the maximum number of leaves of any search tree generated by a $n$-node graph.

Let us assume $L(n)\le c^n$ for some constant $c\ge 1$. When we branch at node $v$ we generate two subproblems containing $n-1$ and $n-|N[v]|$ nodes.Therefore $c$ has to satisfy $$c^n\ge c^{n-1}+c^{n-|N[v]|} \tag{1}$$

Question I couldn't figure out why inequation $(1)$ holds, and I was wondering the meaning behind the inequation from a more intuitive perspective.

The original paper is rather long and I've tried to describe my question without lose of information. But if you need more information, please let me know in comments, I'll update it.


Your Answer

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

Browse other questions tagged or ask your own question.