Parallel anytime branch and bound algorithm for finding the treewidth of graphs

Project reference: 2116

In this project, students will develop an efficient parallel algorithm for determining good upper bounds, if not the exact value, of a quantity called treewidth for arbitrary graphs. While computing the treewidth of an arbitrary graph is known to be an NP hard problem, being able to find good upper bounds for the treewidth is very useful for many important applications. One area where this is particularly important is in simulating quantum computers. Notably, in 2019 Google demonstrated the capabilities of their quantum processing unit, known as the sycamore chip. To validate the correctness of the chip’s output, simulations of the chip had to be carried out, a task which can easily become infeasible if not done efficiently. A serial algorithm was used to compute an upper bound for the treewidth of a graph associated with the chip and the result was used to determine an efficient simulation scheme for the device. Better upper bounds lead to better simulation schemes. As such, a tool for utilising parallel computing to find good upper bounds for the treewidth of a graph would be valuable for the development of such devices.

Computing approximations of the treewidth has important applications many other areas including extracting information from social networks (https://arxiv.org/abs/1411.1546), inference of probabilistic graphical models (https://arxiv.org/abs/1206.3240) and was one of the topics of the PACE 2017 challenge.

More concretely, the algorithm to be developed by the student will use the branch and bound paradigm to search through the set of elimination orderings for a graph provided by the user. An elimination ordering of a graph is an ordering of the graph’s vertices for elimination, where eliminating a vertex means connecting all of its neighbours together before removing it from the graph entirely. The width of an elimination ordering is the maximum number of neighbours any one vertex has when it is eliminated according to that ordering. The treewidth of a graph can be defined as the minimum width over all possible elimination orders.

To find the elimination ordering (EO) with the optimal treewidth involves searching over all the possible EOs of the graph. Since the number EOs grows extremely fast as the size of the graph is increased, searching all possibilities quickly becomes intractable for even for modest sized graphs. The branch and bound algorithm works by maintaining upper and lower bounds for the treewidth and using these

to avoid whole ranges of EOs which we can tell in advance will not have optimal treewidth. Implementing this algorithm in parallel presents some interesting trade-offs. It’s possible to implement this algorithm as an embarrassingly parallel problem with no communication between processes, which will avoid synchronisation issues and communication overhead but will mean additional work for each process.

Julialang is the preferred language for this challenge as it provides the high-level abstractions of interpreted languages like Python with the speed of compiled languages like C and Fortran. It is also possible to use Python or C++ if the student has a strong preference.

[Graphic in Section 9]
An example of a tree decomposition. Image taken from Adcock et al “Tree decompositions and social graphs” https://arxiv.org/pdf/2012.13349

Project Co-mentor: John Brennan

Site Co-ordinator: Simon Wong

Participants: Oliver Legg, Valentin Trophime

Learning Outcomes:
The students will gain experience of developing, debugging and profiling parallel programs which use MPI as well as experience with graph algorithms. They will also be exposed to the branch and bound programming paradigm which can be applied to many problems. They will also improve their general programming skills and gain experience of working as part of a team.

Student Prerequisites (compulsory):
Some experience and exposure to scientific programming and graph theory would be beneficial. Ability to read and understand technical literature containing equations and algorithm outlines.

Student Prerequisites (desirable):
N/A

Training Materials:

• Paper describing anytime branch and bound tree width algorithm: http://arxiv.org/abs/1207.4109
• The Julialang manual https://docs.julialang.org/en/v1/
• Course material on parallelism using Julialang https://mitmath.github.io/18337/
• Paper describing a parallel branch and bound treewidth algorithm: http://people.iiis.tsinghua.edu.cn/~yuanyang/files/final_version.pdf

Workplan:

Week 1: Training week

Week 2: Introduction to Julia, treewidth theory, relevant graph packages.

Week 3: (Plan due) Read Gogate and Yang Yuan papers, understand
Basic branch and bound algorithm without sophisticated pruning heuristics.

Week 4: Implement basic anytime algorithm, run several instances in parallel with random search orders.

Week 5: Get different processes to search different branches of the search space. Include Yuan’s lower bound pruning technique (requires inter process communication).

Week 6: Include Yuan’s similar group heuristic. Profile and optimise the implementation.

Week 7: Apply developed algorithms to example problem instances from the PACE 2017 challenge and from examples uses as part of the QuantEx project.

Week 8: Write report and prepare presentation.

Final Product Description:

1. A program to compute an elimination ordering of minimal width for an arbitrary graph within a duration of time specified by the user.
2. Benchmark results showing the quality of solutions found and the scaling with different numbers of cores and nodes.

Adapting the Project: Increasing the Difficulty:
There are several non-trivial heuristics described in the papers by Gogate and Yuan for improving the efficiency of the algorithm which could be included.

Adapting the Project: Decreasing the Difficulty:
Inter process communication can be reduced by omitting the need to select branches of the search space for each process, instead branches could be selected at random on each process. Additional optional heuristics can be left out and sample code can be provided to accelerate progress..

Resources:
The students will require access to a laptop/workstation on which they can install development tools and compilers. They will also be provided with access to cluster resources for developing, profiling and benchmarking runs.

Organisation:

ICHEC-Irish Centre for High-End Computing