Ph.D student at Durham University. Part of the Algorithms and Complexity group in the Department of Engineering and Computer Sciences.
Computer Systems (Level 1) - Lab Demonstrator
Programming Paradigms (Level 2) - Lab Demonstrator
Distributed Computing (MSc) - Lab Demonstrator
The Hut Group (2017 -)
Graduate Software Engineer
Durham University (2013 - 2017)
Ph.D in Computer Science
Durham University (2010 - 2013)
B.Sc. Honours in Natural Sciences (Physics and Computer Science)
King Edward VI School, Southampton (2008 - 2010)
A Levels in Maths, Further Maths, Physics and Chemistry
Ph.D (2013 - 2017)
Vertex Surjective H-colouring
P. Golovach, M. Johnson, B. Martin, D. Paulusma and A. Stewart,
Surjective H-Colouring: New Hardness Results,
Lecture Notes in Computer Science, to appear.
Presented: CiE 2017, Turku, Finland
Abstract: A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices f(u) and f(v) of H whenever there is an edge between vertices u and v of G. The H-Colouring problem is to decide whether or not a graph G allows a homomorphism to a fixed graph H. We continue a study on a variant of this problem, namely the Surjective H-Colouring problem, which imposes the homomorphism to be vertex-surjective. We build upon previous results and show that this problem is NP-complete for every connected graph H that has exactly two vertices with a self-loop as long as these two vertices are not adjacent. As a result, we can classify the computational complexity of Surjective H-Colouring for every graph H on at most four vertices.
Square Roots of Graphs with Low Clique Number (2016)
M. Cochefert, J-F. Couturier, P. Golovach, D. Kratsch, D. Paulusma and A. Stewart,
Squares of Low Maximum Degree,
Discrete Applied Mathematics, to appear.
P. Golovach, D. Kratsch, D. Paulusma and A. Stewart,
Finding Cactus Roots in Polynomial Time,
Theory of Computing Systems, submitted.
Lecture Notes in Computer Science 9843, 361-372 doi.
Presented: IWOCA 2016, Helsinki, Finland
P. Golovach, D. Kratsch, D. Paulusma and A. Stewart,
A Linear Kernel for Finding Square Roots of Almost Planar Graphs,
Leibniz International Proceedings in Informatics 53, 4:1-4:14 doi.
Presented: SWAT 2016, Reykjavik, Iceland
Abstract: A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are of distance 2 of each other. The Square Root problem is that of deciding whether a given graph admits a square root. This problem is only known to be NP-complete for chordal graphs and polynomial-time solvable for non-trivial minor-closed graph classes and a very limited number of other graph classes. By developing a general technique, based on bounding the treewidth of a graph, we prove that Square Root is polynomial-time solvable on various graph classes of low clique number, including graphs of maximum degree at most 6, graphs of maximum average degree less than 46/11 and 3-degenerate graphs.
Minimal Disconnected Cuts in Planar Graphs (2015)
M. Kamiński, D. Paulusma, A. Stewart and D. M. Thilikos,
Minimal Disconnected Cuts in Planar Graphs,
Networks 68 (2016) 250-259 doi.
Lecture Notes in Computer Science 9210, 243-254 doi.
Presented: FCT 2015, Gdańsk, Poland
Abstract: The problem of finding a disconnected cut in a graph is NP-hard in general but polynomial-time solvable on planar graphs. The problem of finding a minimal disconnected cut is also NP-hard but its computational complexity is not known for planar graphs. We show that it is polynomial-time solvable on 3-connected planar graphs but NP-hard for 2-connected planar graphs. Our technique for the first result is based on a structural characterization of minimal disconnected cuts in 3-connected K3,3-free-minor graphs and on solving a topological minor problem in the dual. We show that the latter problem can be solved in polynomial-time even on general graphs. In addition we show that the problem of finding a minimal connected cut of size at least 3 is NP-hard for 2-connected apex graphs.
Complexity of Parallel Knock-Out on Pk-free graphs (2014)
M. Johnson, D. Paulusma and A. Stewart,
Knocking out Pk-free graphs,
Discrete Applied Mathematics 190 (2015) 100-108 doi.
Lecture Notes in Computer Science 8635, 396-407 doi.
Presented: BCTCS’14, Loughborough, UK; MFCS 2014, Budapest, Hungary
Abstract: A parallel knock-out scheme for a graph proceeds in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is KO-reducible if there exists such a scheme that eliminates every vertex in the graph. The Parallel Knock-Out problem is to decide whether a graph G is KO-reducible. This problem is known to be NP-complete and has been studied for several graph classes. We show that the problem is NP-complete even for split graphs, a sub- class of P5-free graphs. In contrast, our main result is that it is linear-time solvable for P4-free graphs (cographs).
Durham University Canoe Club. (2014)
I developed a full website from scratch for the Unviersity Canoe Club. The main function of the website was to allow members to sign up to trips and events, but it also includes a new section and a files sections along with many other features.
B.Sc. Dissertation (2013)
My BSc dissertation looked at Ant Colony Optimization algorithms. I looked at using an Ant Colony algorithm in the field of graph drawing and created a hybrid algorithm which combined an ant colony algorithm with the more commonly used force directed graph drawing algorithm as a local search.
My dissertation was shortlisted for the CREST BSc Final Project prize and I was invited to give a talk on it in London.
Ohso Media, Ltd. (2010 - 2012)
I worked on the redesign of the the OMG! Ubuntu! site in 2010. I also developed and implemented the design for their sister site Ubuntu Gamer which ran for a while in 2011.
Being based in the North East there is a lot of opportunity for kayaking with the the River Swale and the River Tees nearby and with Scotland and North Wales being close enough weekend trips. I mainly do White Water paddling and a bit of Freestyle but I also compete in Polo for Tees Tigers and have applied for ranking in Slalom (C1). I compete for the University in all three discaplines: Polo, Whitewater Racing and Slalom.
- UKCC Level 2 Coach
- BCU 3* White Water
- BCU 3* Open Canoe
- BCU 3* Freestyle (K1)
- Advanced White Water Safety and Rescue
- 16h Outdoor First Aid
- 1st (C2, BUCS WWR 2015/16)
- 1st (C2 Sprint, BUCS WWR 2015/16)
- 1st (Mixed Team, BUCS WWR 2015/16)
- 1st (C2 Sprint, BUCS WWR 2016/17)
- 2nd (Open Team, BUCS WWR 2011/12)
- 2nd (C1, NSR 2013)
- 2nd (C2, BUCS WWR 2014/15)
- 2nd (C2 Sprint, BUCS WWR 2014/15)
- 2nd (C1, NSR 2016)
- 2nd (Mens League, BUCS Polo 2015/16)
- 3rd (C1, BUCS WWR 2015/16)
- 3rd (C1 Sprint, BUCS WWR 2015/16)
- 3rd (C2, BUCS WWR 2016/17)
- 3rd (Open Team, BUCS Slalom 2016/17)
- 4th (C1, BUCS WWR 2014/15)
- 4th (Mixed Team, BUCS WWR 2014/15)
- Canoe Polo: National League - Div 4: Tees Tigers B (3rd 2015/16, 2nd 2016/17)
- Canoe Polo: Local League (Yorkshire) - Div 3: Durham University (1st 2015)