Journal of Algorithms

Volume 10, Issue 4, December 1989, Pages 451-489
Journal of Algorithms

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(n2) expected time algorithm for n-vertex graphs, with k constant.

2.

(2) Small equitable cut. We describe an O(n3) 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 (1 − ϵ)n22 edges.

3.

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

4.

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

Choose an option to locate/access this article:

Check if you have access through your login credentials or your institution.