# Anthony Stewart

## Durham University

# Intro

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

# Contact

**Office:** *E390*

**Email:** *a.g.stewart@durham.ac.uk*

**Phone:** *07852 131188*

# Teaching

*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

**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*

# King Edward VI School, Southampton (2008 - 2010)

### A Levels in Maths, Further Maths, Physics and Chemistry

# 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 *K _{3,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 *P*_{k}-free graphs (2014)

_{k}

**Paper:** *
M. Johnson, D. Paulusma and A. Stewart,
Knocking out P_{k}-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 *P _{5}*-free graphs. In contrast, our main result is that it is linear-time
solvable for

*P*-free graphs (cographs).

_{4}# 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)

**Report:** [download]

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:**

*1*(C2, BUCS WWR 2015/16)^{st}*1*(C2 Sprint, BUCS WWR 2015/16)^{st}*1*(Mixed Team, BUCS WWR 2015/16)^{st}*1*(C2 Sprint, BUCS WWR 2016/17)^{st}*2*(Open Team, BUCS WWR 2011/12)^{nd}*2*(C1, NSR 2013)^{nd}*2*(C2, BUCS WWR 2014/15)^{nd}*2*(C2 Sprint, BUCS WWR 2014/15)^{nd}*2*(C1, NSR 2016)^{nd}*2*(Mens League, BUCS Polo 2015/16)^{nd}*3*(C1, BUCS WWR 2015/16)^{rd}*3*(C1 Sprint, BUCS WWR 2015/16)^{rd}*3*(C2, BUCS WWR 2016/17)^{rd}*3*(Open Team, BUCS Slalom 2016/17)^{rd}*4*(C1, BUCS WWR 2014/15)^{th}*4*(Mixed Team, BUCS WWR 2014/15)^{th}

**Leagues:**

- Canoe Polo:
*National League - Div 4:*Tees Tigers B (3^{rd}2015/16, 2^{nd}2016/17) - Canoe Polo:
*Local League (Yorkshire) - Div 3:*Durham University (1^{st}2015)

**Load video**