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.
|January 2020||March 2020|
Events for 11 February 2020
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 email@example.com for more information about this event.
Contact firstname.lastname@example.org for more information about this event.