On finding a satisfactory partition in an undirected graph: algorithm design and results

A satisfactory partition is a partition of undirected-graph vertices such that the partition has only two nonempty parts, and every vertex has at least as many adjacent vertices in its part as it has in the other part. Generally, the problem of determining whether a given undirected graph has a satisfactory partition is known to be NP-complete. In this paper, we show that for a given undirected graph with $n$ vertices, a satisfactory partition (if any exists) can be computed recursively with a recursion tree of depth of $\mathcal{O}(\ln n)$ in expectation. Subsequently, we show that a satisfactory partition for those undirected graphs with recursion tree depth meeting the expectation can be computed in time $\mathcal{O}(n^3{2}^{\mathcal{O}(\ln n)})$.