Hard Graph Problems - Theory and in Practice

SUMMARY: We will study the maximum weight clique and maximum edge weight clique problems, developing new algorithms, compiling a set of realistic benchmark instances which researchers can use to compare algorithms, and analysing the search tree explored by algorithms to better understand how they work in practice and how they may be improved.

CONTEXT: Graphs---collections of nodes, with edges between some pairs of nodes---are a fundamental mathematical object. The maximum clique problem is the task of finding, for a given graph, as large a set of nodes as possible such that each pair of nodes in the set are joined by an edge. In the context of a social network, we can view this as the problem of finding as large a group of mutual friends as possible. This, and related problems, have a wide range of practical applications in fields such as biology and computer vision.

AIMS & OBJECTIVES: Our project will study two generalisations of the maximum clique problem. In the first of these, maximum weight clique (MWC), each node has a weight and we seek to find a group of pairwise-adjacent vertices with as high a total weight as possible. This is a well known problem with applications including the winner determination problem in combinatorial auctions (in which participants bid on bundles, rather than individual items). The second problem we will consider is maximum edge weight clique (MEWC), in which each edge has a weight.

We will develop and implement new algorithms to solve these problems. We will explore encodings of the problems that can be solved directly by existing general-purpose solvers, and also develop new customised algorithms for the problems. We will develop both exact algorithms, which are guaranteed to find an optimal solution, and heuristic algorithms which do not always find an optimal solution but may find a good solution much more quickly in practice.

We also investigate kernalisations, where a problem is pre-processed and compressed (and expanded once solved), and filtering steps (to remove redundant vertices and edges) that can be applied as a pre-process or within search.

We will perform empirical studies to understand problem features that influence the performance of algorithms. We will also examine the search tree that is explored by each algorithm, to better understand its behaviour and to seek ways to reduce the amount of work that must be carried out to find a solution.

We will develop theory to explain why some problem instances are hard and others are easy. This theory will be tested empirically and used to guide the engineering of new algorithms and heuristics.

A weakness of the existing literature on MWC is that the benchmark instances used to compare the performance of algorithms are generated in a very artificial way, and bear little resemblance to real-world problems. We will compile a benchmark set of more realistic instances. This will be of use to us in our experiments, and will be a valuable resource for other researchers investigating this and related problems.

APPLICATIONS: We will explore new applications of MWC and MEWC. As one concrete example, we will use MWC to find the optimal solution to the kidney exchange problem---a problem which is already used in practice by the NHS to assign living organ donors to patients. We believe that MWC algorithms will be an effective and simple technique for solving the kidney exchange problem, and could be combined with existing techniques to enable kidney-exchange algorithms to scale to international schemes which are likely to exist in the near future.

We will develop software that encodes binary constraint satisfaction problems (CSPs)---a very general class of problem---as MWC, and will therefore be able to use MWC solvers to solve many types of practical problems such as scheduling and vehicle routing. We will compare the performance of this solution technique with existing CSP solvers.