Before revision:  The best lower bounds come from conjectures about the solvability of the k-clique problem and a reduction from k-clique to k-cut , and show that solving k-cut is likely to require time \Omega(n^k).
After revision:  The best lower bounds come from conjectures about the solvability of the k-clique problem , and show that solving k-cut is likely to require time \Omega(n^k).