Exact algorithms for NP-hard problems
Lead Research Organisation:
Durham University
Department Name: Computer Science
Abstract
We propose to study exact algorithms for NP-hard problems. An algorithm can be seen as a set of constructions for solving a problem. An exact algorithm is an algorithm that solves a problem to optimality. NP-hard problems are a special kind of optimization problems for which most probably no polynomial time (i.e. fast ) algorithm exists. As an example of an NP-hard problem we can consider the travelling salesman problem (TSP). In this problem a travelling salesman has to make a tour through a number of cities starting and returning to city 1 in such a way that the total travel distance is minimal. Of course, it is possible to solve this problem to optimality by computing the distance of every tour and then choosing a tour with minimum distance. This simple algorithm costs a huge amount of computation time. Already in the case of a relatively small number of cities, the problem can not be solved (within reasonable time) on any modern computer that uses this algorithm.Our research will result in faster algorithms for this kind of problems. Even a faster exact algorithm that does not run in polynomial time can already mean that in practice much larger instances (cf. with many cities in TSP) can be solved. Secondly, we hope that our research will lead to a better understanding of NP-hard problems with respect to the (worst-case) time it takes to solve them. Since it is very unlikely to obtain polynomial time algorithms for this kind of problems, we can not expect to develop exact algorithms that are faster than a certain threshold. By developing faster algorithms for a number of NP-hard problems we hope to find out whether thresholds for different problems are somehow related to each other.
Organisations
People |
ORCID iD |
| Daniel Paulusma (Principal Investigator) |
Publications
Broersma H
(2007)
On components of 2-factors in claw-free graphs
in Electronic Notes in Discrete Mathematics
Broersma H
(2010)
Computing sharp 2-factors in claw-free graphs
in Journal of Discrete Algorithms
Broersma H
(2013)
Three complexity results on coloring P k -free graphs
in European Journal of Combinatorics
Broersma H
(2010)
Graph-Theoretic Concepts in Computer Science
Broersma H
(2009)
Sharp Upper Bounds on the Minimum Number of Components of 2-factors in Claw-free Graphs
in Graphs and Combinatorics
Broersma H
(2009)
Upper bounds and algorithms for parallel knock-out numbers
in Theoretical Computer Science
Broersma H
(2011)
Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs
in Algorithmica
Broersma H
(2009)
? -backbone colorings along pairwise disjoint stars and matchings
in Discrete Mathematics
Broersma H
(2007)
Structural Information and Communication Complexity
Broersma H
(2007)
SOFSEM 2007: Theory and Practice of Computer Science
| Description | We studied exact algorithms for NP-hard problems. An algorithm can be seen as a set of constructions for solving a problem. An exact algorithm is an algorithm that solves a problem to optimality. NP-hard problems are a special kind of optimization problems for which most probably no polynomial time (i.e. "fast") algorithm exists. As an example of an NP-hard problem we consider the well-known hamilton cycle problem. In this problem one has to make a tour through a network called a graph that consists of vertices and links between these vertices called edges, such that every vertex is visited exactly once. This problem is NP-hard even for claw-free graphs i.e. graphs with no induced claw (four-vertex star). Finding a fast exact algorithm that solves the hamilton cycle problem is a notorious open problem. 1. Our first main result is a fast exact algorithm that solves the hamilton cycle problem for claw-free graphs. This is the first result for a nontrivial graph class in which the graphs may have arbitrarily large vertex-degree. Afterwards we modified the algorithm for solving the longest cycle problem (a more general problem) in the same time for claw-free graphs. 2. Our second main result is a fast exact algorithm for several graph partitioning problems when we restrict the input graph to graphs with no induced path of certain length. One such problem is the problem of partitioning the vertices of a graph into two connected parts that each contain a set of prespecified vertices. This problem has applications in computational geometry (removing local optima from imprecise terrains). A closely related problem for which we also designed an exact algorithm for the same graph class is the problem of determining the length of a longest path a given graph can be contracted to by using edge contractions only. We emphasize that these types of results are twofold. STEP A. First we characterized the structure of our input graphs. This has led to a new upper bound on the number of components in a 2-factor (spanning subgraph that consists of cycles only) of a claw-free graph. This has also led to a new characterization of the class of P6-free graphs, where P6 denotes the 6-vertex path. Since such results are of independent interest we published them as stand-alone papers. Especially our paper on P6-free graphs has already been cited by several other researchers working in this area. STEP B. We then used our structural results in the design of our algorithms. Due to these results we were able to speed up the running time of our exact algorithms considerably. We mention that we also used our structural results in STEP A to obtain polynomial-time algorithms for several other problems, such as finding a 2-factor in a claw-free graph with a small number of components, colouring the uncoloured vertices of a partially precoloured P6-free graph with at most 3 colours such that any two adjacent vertices are not coloured alike, deciding whether a claw-free graph contains an induced path of odd length between two prespecified vertices, and so on. This has led to the following achievements : - 14 publications in international refereed conferences such as COCOON, CSR, FCT, FSTTCS, ISAAC, MFCS, SOFSEM and WG. - 7 publications in international high-quality journals such as Discrete Applied Mathematics, Graphs and Combinatorics, Journal of Discrete Algorithms, Theoretical Computer Science, and Theory of Computing Systems. It also led to the PhD Thesis "Exploiting structure to cope with NP-hard graph problems: Polynomial and exponential time exact algorithms" successfully defended by the project student Pim van 't Hof on 14 May 2010. |
| Exploitation Route | Our results are fundamental of nature and could lead to further improvements by researchers working in Discrete Mathematics and Theoretical Computer Science. For example, our structural results on P6-free graphs have recently been improved by Schaudt and Camby for all P_k-free graphs (WG 2014, LNCS 8747, 129-138). |
| Sectors | Digital/Communication/Information Technologies (including Software) |
| Description | Coping with NP-hardness: parameterized and exact algorithms |
| Amount | £11,990 (GBP) |
| Organisation | The Royal Society |
| Sector | Charity/Non Profit |
| Country | United Kingdom |
| Start | 03/2011 |
| End | 02/2014 |