Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Research & business

Research lectures, seminars and events

The events listed in this area are research seminars, workshops and lectures hosted by Durham University departments and research institutes. If you are not a member of the University, but  wish to enquire about attending one of the events please contact the organiser or host department.


 

February 2020
SunMonTueWedThuFriSat
January 2020 March 2020
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29

Events for 11 February 2020

Siani Smith: Computing Independent Transversals for H-Free Graphs of Bounded Diameter

1:00pm, E245

Several important graph transversal problems can also be viewed as graph modification problems. For example 3-Colouring can be viewed as deciding whether some independent set can be deleted from a graph to leave it bipartite whilst Independent Odd Cycle transver- sal is the problem of deciding whether there exists such a set of size at most k. Similarly, Near-Bipartiteness is the problem of deciding whether some independent set of vertices can be deleted from a graph to obtain a forest whilst Independent Feedback Vertex Set requires deciding whether there exists such a set of size at most k.

All these problems are NP-complete even after restricting the input to classes of H-free graphs for many graphs H (a graph is H-free if it does not contain H as an induced subgraph). However, this may change once we bound some graph parameter in addition (which may imply the graph class is no longer hereditary). For example, it can be observed that the computational complexity of all problems restricted to claw-free graphs jumps from being NP-complete to being constant-time solvable if we assume any constant upper bound on the diameter of the graph. Starting from this initial observation, we determine the complexity of the above problems for H-free graphs, exploiting the effect of additionally bounding the diameter of the input graph in order to obtain new polynomial-time results.

The talk is based on joint work with: Barnaby Martin and Daniel Paulusma

Contact algorithms.complexity@dur.ac.uk for more information about this event.


Public Lecture: Pilgrimage, Miracle and Art with Dr Robert Maniura

5:45pm to 7:15pm, Town Hall, Durham City

Contact admin.imems@durham.ac.uk for more information about this event.