The grant is for research in Constraint Network Tractability: Beyond Structure and Language.
Constraint Satisfaction is a very general way of specifying feasibility questions: Scheduling, Machine Vision, Timetabling, Machine Allocation, Delivery Routing are all classic examples.
Such problems are computationally hard so a considerable effort has been invested into finding when particular classes may have practicable algorithms. This work has been successful but has concentrated so far on restricting the structure or language allowed when specifying instances.
In this work Professor Cohen will be working with Professor Cooper from the University of Toulouse, and Professor Jeavons and Dr Zivny from the University of Oxford, to find a unifying theory for the known tractability results. Their unique and ambitious contribution is to characterise tractable cases by forbidding small patterns which embody the reasons for hardness.
The hope is that the list of such forbidden patterns is amenable to a unifying theory. The team will be working on this research for three years.
