Exact and parameterized algorithms (ANR-09-BLAN-0159)

In the classical complexity theory, a problem is considered to be non-tractable if it cannot be solved in polynomial time. But lots of real world problems are naturally modelled by graph optimisation problems which are NP-hard that is for which no polynomial time algorithm exists (unless P=NP). Hence, finding solutions to these problems is an important issue. Sometimes approximate (but non-optimal) solutions are sufficient but in some cases the optimal solution is absolutely required. The aim of the proposed research programme is to develop new techniques to solve exactly NP-hard problems on graphs. To do so, we envisage two approaches which are closely related ways to reduce the combinatorial explosion of NP-hard problems. They have lots of connections ranging from very practical questions in algorithms design to the fundamental complexity theoretical problems.

• The first approach is to find exponential exact algorithms running in time exponenetial with a base c of the exponential as small as possible. Then with the ever-growing computing power, one can hope to handle these problems if c is not too large.
• The second approach is fixed-prameter tractability. Its idea is to isolate problem parameters that can be expected to be small in certain applications and then develop algorithms whose running time is polynomial in the instance size n but depends arbitrarily of these parameters. Hence as long as the parameters are small, the problem may be considered as tractable. Since the choice of suitable parameters allows a great flexibility, fixed-parameter algorithms have found their way into practical applications such diverse as computational biology, database systems, computational linguistics, and automated verification.

The originality of the proposal is to combine tools of graph theory, such as structural theorem, the probabilistic method, the discharging method, and algorithmic tools, such as “measure and conquer”, inclusion-exclusion principle, in order to obtain efficient algorithms. To estimate their practical efficiency, they will be implemented on Mascopt in order to be compared with other algorithms.

Dates: 2009-2013

Partners: I3S (INRIA Sophia-Antipolis, CNRS, Université Nice), LIRMM (CNRS, Université Montpellier), LIFO (Université Orléans)