William Pettersson

William Pettersson

Headshot of William Pettersson
William Pettersson, Research Associate
School of Computing Science, University of Glasgow,
Glasgow, United Kingdom G12 8QQ

Email: william@ewpettersson.se
XMPP: william@ewpettersson.se


I am a mathematician, and currently employed as a research associate at the University of Glasgow in the School of Computing Science where I am part of the Formal Analysis, Theory and Algorithms group. I am currently working on the IP-MATCH EPSRC project, under the supervision of Dr David Manlove. The goal of this research is to allow the best possible allocation of resources. One particular application of this work which we are directly studying is the allocation of kidney donors to patients [10]. My research has taken me from graph decompositions through combinatorial and computational topology and into linear and integer programming. In much of this work, I have devised or used innovative algorithms to help solve my particular problems.

I also have a strong interest in computing, reaching from the algorithms I use in my research to the complex world of information security. I have practical experience with coding at all levels, from assembly for the HC12 through C, and C++ all the way to Python, PHP and Perl. Details on some of these projects are available below.

As a student I have played integral roles in the organisation of various social functions as a part of the Mathematics Students Society. I have been a member of the Host Scientific Committee for the 2013 International Olympiad in Informatics and was involved with the Queensland Informatics & Programming Club to train high school students in informatics.
Swedish flag
Section separator

Research Interests

Stable Matching Problems

A matching to a stable matching problem is stable if, given some agents with preferences, no pair of agents will both prefer to break with the given matching. These types of matchings are applicable to the allocation of people and/or resources, including assigning junior doctors to training positions at hospitals or teachers to schools. These preferences can come with some of the following properties:
  • ties — these happen if an agent cannot sufficiently differentiate between two or more options, and
  • incompleteness — some options may be unsuitable or unacceptable, or a person may not wish to offer preferences over all options, so they present an incomplete list of preferences over only some options.
If both ties and incompleteness are present, then finding a stable matching of largest size is NP-Hard. I have worked on preprocessing techniques and models [9] for solving such problems, and am very interested in the specific parameters or structures of when such problems become hard, in both theoretic and practical senses.

Graph Decompositions

A decomposition of K7 I study the existence of decompositions and factorisations of
  • complete graphs [1],
  • bi-partite graphs [2],
  • circulant graphs [1], and
  • multigraphs.
I also apply computational techniques to problems in this field.

Multi-objective optimisation

I have designed and implemented [3] many multi-objective integer optimisation algorithms [4,5] to solve such problems far faster. This is achieved through the use of parallel techniques and online communication between workers.

Combinatorial and computational topology

The Regina logo
  • Development of Regina, a mathematical software suite for 3-manifold topologists
  • Census enumeration algorithms, and their complexity [7,8]
  • Calculations of quantum invariants
  • Algorithms on triangulations
  • Spine codes of 3-manifolds [1]
  • Properties of Pachner graphs
Section separator

Software projects


moip_aira is an implementation of a parallel multi-objective integer programming algorithm that aims for perfect parallelisation. It has been improved through multiple research papers, and offers many different ways to improve running times through various tweaks and overhauls.

Graph theory

graphlib is a library of graph decomposition techniques that were used to find various decompositions and factorisations which were in turn used to solve the cycle decomposition problem for complete graphs.

rook_decomp is a small program that is currently trying to find a decomposition of the complete bipartite graph on 2n vertices into copies of the rook graph Kn.


My Github page lists many other projects that I have at some point worked on.

Combinatorial and computational topology

The Regina logo
Regina - Software for 3-manifold topology and normal surface theory

I am one of the developers of Regina, a suite of mathematical software for 3-manifold topologists. It focuses on the study of 3-manifold triangulations and normal surfaces. I also maintain the Gentoo packages for Regina. For official downloads for other distributions, see http://regina.sourceforge.net.

Gentoo packages for Regina are available in a layman overlay. Once layman has been installed, you can install the overlay by running # layman -a regina-gentoo. You will then be able to install Regina with # emerge regina. Note that version 9999 of Regina in the overlay will always update to the latest GIT revision, which may or may not work at any given time.

Section separator


Particulars Status Pre-print
B. Burton, S. Cabello, S. Kratsch, W. Pettersson The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex SIAM Journal on Discrete Mathematics 2019; doi: 10.1137/18M1168704 Published arXiv
Péter Biró et al. Modelling and Optimisation in European Kidney Exchange Programmes European Journal of Operational Research 2019; doi: 10.1016/j.ejor.2019.09.006 Published
C. McCreesh, W. Pettersson, P. Prosser Understanding the empirical hardness of random optimisation problems Lecture Notes in Computer Science 2019; doi: 10.1007/978-3-030-30047-7_20 Accepted
W. Pettersson, M. Ozlen Multi-Objective Mixed Integer Programming: An Objective Space Algorithm AIP Conference Proceedings 2019; doi: 10.1063/1.5090006 Published arXiv
M. Delorme, S. García, J. Gondzio, J. Kalcsics, D. Manlove, W. Pettersson Mathematical models for stable matching problems with ties and incomplete lists. European Journal of Operational Research 2019; doi: 10.1016/j.ejor.2019.03.017 Published arXiv
W. Pettersson and M. Ozlen. Multi-objective integer programming: Synergistic parallel approaches. INFORMS Journal on Computing 2019; doi: 10.1287/ijoc.2018.0875 Published arXiv
W. Pettersson and M. Ozlen. A parallel approach to bi-objective integer programming, Australian and New Zealand Industrial and Applied Mathematics Journal. 2017; doi: 10.21914/anziamj.v58i0.11724 Published arXiv
B. Burton, S. Cabello, S. Kratsch, W. Pettersson. The parameterized complexity of finding a 2-sphere in a simplicial complex, 34th International Symposium on Theoretical Aspects of Computer Science (STACS 2017) 2017; doi: 10.4230/LIPIcs.STACS.2017.18 Published arXiv
B. Burton and W. Pettersson. An edge-based framework for enumerating 3-manifold triangulations, 31st International Symposium on Computational Geometry (SoCG 2015) 2015; doi: 10.4230/LIPIcs.SOCG.2015.270 Published arXiv
D. Bryant, D. Horsley, and W. Pettersson. Cycle decompositions V: Complete graph into cycles of arbitrary lengths, Proceedings of the London Mathematical Society 2014; doi: 10.1112/plms/pdt051 Published arXiv
D. Bryant, P. Danziger and W. Pettersson. Bipartite 2-factorisations of complete multipartite graphs, Journal of Graph Theory vol. 78, issue 4. April 2015;, pp.287-294 doi: 10.1002/jgt.21806 Published
B. Burton and W. Pettersson. Fixed parameter tractable algorithms in combinatorial topology, Lecture Notes in Computer Science vol. 8591, 2014, pp.200-311. doi: 10.1007/978-3-319-08783-2_26 Published arXiv
W. Pettersson. Computational Graph Theory, PhD Thesis Oct 17 2014 Accepted Self hosted
Section separator


At The University of Queensland
As a teaching assistant:
  • 2014 : MATH4303 Advanced Combinatorics
  • 2011-2014 : MATH3301 Graph Theory and Design Theory
  • 2010-2014 : MATH3302 Coding and Cryptography
  • 2010-2014 : MATH1061 Discrete Mathematics
  • 2011-2013 : MATH3500 Problems and Applications in Modern Mathematics
  • 2011 : MATH4302 Combinatorial Designs
  • 2010 : MATH3306 Set Theory and Logic
Chalk drawing of cat on blackboard
Section separator