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

View Profile

Publication details for Dr Barnaby Martin

Martin, B., Paulusma, D. & van Leeuwen, E.J. (2018), Disconnected Cuts in Claw-free Graphs, in Azar, Yossi, Bast, Hannah & Herman, Grzegorz eds, Leibniz International Proceedings in Informatics (LIPIcs) 112: 26th Annual European Symposium on Algorithms (ESA 2018). Helsinki, Finland., Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Dagstuhl, Germany, 61:1--61:14.

Author(s) from Durham


A disconnected cut of a connected graph is a vertex cut that itself also induces a disconnected
subgraph. The corresponding decision problem is called Disconnected Cut. It is known that
Disconnected Cut is NP-hard on general graphs, while polynomial-time algorithms exist for
several graph classes. However, the complexity of the problem on claw-free graphs remained an
open question. Its connection to the complexity of the problem to contract a claw-free graph to
the 4-vertex cycle C4 led Ito et al. (TCS 2011) to explicitly ask to resolve this open question. We
prove that Disconnected Cut is polynomial-time solvable on claw-free graphs, answering the
question of Ito et al. The basis for our result is a decomposition theorem for claw-free graphs of
diameter 2, which we believe is of independent interest and builds on the research line initiated by
Chudnovsky and Seymour (JCTB 2007–2012) and Hermelin et al. (ICALP 2011). On our way to
exploit this decomposition theorem, we characterize how disconnected cuts interact with certain
cobipartite subgraphs, and prove two further algorithmic results, namely that Disconnected
Cut is polynomial-time solvable on circular-arc graphs and line graphs.