### Abstract

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 proposed, 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.

Original language | English |
---|---|

Title of host publication | Proceeding ACSC '05 Proceedings of the Twenty-eighth Australasian conference on Computer Science |

Editors | Vladimir Estivill-Castro |

Place of Publication | Sydney, NSW |

Publisher | Australian Computer Society |

Pages | 183-192 |

Number of pages | 10 |

Volume | 38 |

ISBN (Print) | 1920682201, 9781920682200 |

Publication status | Published - Feb 2005 |

Event | 28th Australasian Computer Science Conference, ACSC - 2005 - Newcastle, Australia Duration: 31 Jan 2005 → 3 Feb 2005 |

### Other

Other | 28th Australasian Computer Science Conference, ACSC - 2005 |
---|---|

Country | Australia |

City | Newcastle |

Period | 31/01/05 → 3/02/05 |

## Fingerprint Dive into the research topics of 'A two-pronged attack on the dragon of intractability'. Together they form a unique fingerprint.

## Cite this

*Proceeding ACSC '05 Proceedings of the Twenty-eighth Australasian conference on Computer Science*(Vol. 38, pp. 183-192). Sydney, NSW: Australian Computer Society.