The solution of some random NP-hard problems in polynomial expected time

Abstract

The average-case complexity of recognising some NP-complete properties is examined, when the instances are randomly selected from those which have the property. We carry out this analysis for

1.

(1) Graph k-colourability. We describe an O(n²) expected time algorithm for n-vertex graphs, with k constant.

2.

(2) Small equitable cut. We describe an O(n³) expected time algorithm for finding and verifying, the minimum equitable cut in a 2n-vertex graph G, condition on G having one with at most $\text{(1 − ϵ)n}{}^2\text{2}$ edges.

3.

(3) Partitioning a 2n vertex graph into two sparse vertex induced subgraphs of a given class. We describe an O(n³) expected time algorithm for computing such a partition.

4.

(4) The number problem 3-PARTITION. We describe an O(n²) expected time algorithm for problems with 3n integers.