Computing at Glasgow University
Paper ID: 9351

Triangle Packing with Constraint Programming

Publication Type: Conference Proceedings
Appeared in: 9th International Workshop on Constraint Modelling and Reformulation (ModRef 2010)
Page Numbers : 1-15
Publisher: N/A
Year: 2010

In vertex disjoint triangle packing we are given a simple undirected graph G and we have to select the maximum number of triangles such that each triangle is composed of three adjacent vertices and each pair of triangles selected has no vertex in common. The problem is NP-hard and APX-complete. We present three constraint models and apply them to the optimisation and decision problem (attempting to pack n/3 triangles in a graph with n vertices). In the decision problem we observe a phase transition from satisfiability to unsatisfiability, with a complexity peak at the point where 50% of instances are satisfiable, and this is expected. We characterise this phase transition theoretically with respect to constrainedness. However, when we apply a mixed integer programming model to the decision problem the complexity peak disappears.

Keywords: triangle packing, constraint programming, phase transition, mixed integer programming, constrainedness

PDF Bibtex entry Endnote XML