A Two-Pronged Attack on the Dragon of Intractability

Gilmour, S. and Dras, M.

One approach to tractably finding a solution to an NP-complete optimisation problem is heuristic, where the solution is inexact but quickly found; another approach is to reduce the problem in such a way that the reduction has the same solution as the original but is simpler, and then to solve the reduction, noting that this reduction is still NP-complete. It is possible to combine the two approaches with the goal of taking advantage of both the speed of the heuristic approach and the exactness of the reduction, but this is typically done only in a simple way. The aim of this paper is to begin exploring the range of ways in which these two classes of approach can be combined, using vertex cover as a problem instance. We take as our reduction method the one used under parameterized complexity, where the problem is reduced through the application of kernelisation rules. For our heuristic we use Ant Colony Optimisation (ACO), where a set of 'ants' chooses a solution via distributed interaction; the search space 'terrain' that these ants traverse can be either flat or, as in a recent proposal, preconfigured by templates. In this paper, we investigate kernelisation rules as a notion of template that is richer than has previously been pro- posed, show that under three different models of combination the approach outperforms standard ACO for vertex cover, and analyse the solutions generated by the combination models with respect to each other.

Cite as: Gilmour, S. and Dras, M. (2005). A Two-Pronged Attack on the Dragon of Intractability. In Proc. Twenty-Eighth Australasian Computer Science Conference (ACSC2005), Newcastle, Australia. CRPIT, 38. Estivill-Castro, V., Ed. ACS. 183-192.

(from crpit.com) (local if available)