# Intro

Ph.D student at Durham University. Part of the Algorithms and Complexity group in the Department of Engineering and Computer Sciences.

# Teaching

Computer Systems (Level 1) - Lab Demonstrator
Programming Paradigms (Level 2) - Lab Demonstrator
Distributed Computing (MSc) - Lab Demonstrator

# Durham University (2013 - 2017)

### Ph.D in Computer Science

Research area: Graph Theory, Computational Complexity [ACiD]
Supervisor: Daniel Paulusma
Second supervisor: Matthew Johnson

# Durham University (2010 - 2013)

### B.Sc. Honours in Natural Sciences (Physics and Computer Science)

Dissertation: A study of Ant Colony Algorithms and a potential application in Graph Drawing [link]
Supervisor: Daniel Paulusma

# Ph.D (2013 - 2017)

## Vertex Surjective H-colouring

Paper: P. Golovach, M. Johnson, B. Martin, D. Paulusma and A. Stewart,
Surjective H-Colouring: New Hardness Results,
Lecture Notes in Computer Science, to appear.
[arΧiv]

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)

Paper: M. Cochefert, J-F. Couturier, P. Golovach, D. Kratsch, D. Paulusma and A. Stewart,
Squares of Low Maximum Degree,
Discrete Applied Mathematics, to appear.
[arΧiv]

Paper: 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.
[preprint]

Presented: IWOCA 2016, Helsinki, Finland

Paper: 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.
[arΧiv]

Presented: SWAT 2016, Reykjavik, Iceland

Paper: P. Golovach, D. Kratsch, D. Paulusma and A. Stewart,
Squares of Low Clique Number,
Electronic Notes in Discrete Mathematics 55, 195-198 doi.
[preprint]

Presented: CTW 2016, Gargnano, Italy

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)

Paper: 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.
[preprint]

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)

Paper: 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.
[preprint]

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)

URL: community.dur.ac.uk/canoe.club
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)

URL: omgubuntu.co.uk
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.

# Kayaking

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.

Qualifications:

• 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

Results:
• 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)

Leagues:
• 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)