License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.61
URN: urn:nbn:de:0030-drops-95249
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9524/
Go to the corresponding LIPIcs Volume Portal

Martin, Barnaby ; Paulusma, Daniël ; van Leeuwen, Erik Jan

Disconnected Cuts in Claw-free Graphs

pdf-format:
LIPIcs-ESA-2018-61.pdf (0.4 MB)

Abstract

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 C_4 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.

BibTeX - Entry

@InProceedings{martin_et_al:LIPIcs:2018:9524,
  author =	{Barnaby Martin and Dani{\"e}l Paulusma and Erik Jan van Leeuwen},
  title =	{{Disconnected Cuts in Claw-free Graphs}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{61:1--61:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Yossi Azar and Hannah Bast and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9524},
  URN =		{urn:nbn:de:0030-drops-95249},
  doi =		{10.4230/LIPIcs.ESA.2018.61},
  annote =	{Keywords: disconnected cut, surjective homomorphism, biclique cover, claw-freeness}
}

Keywords: disconnected cut, surjective homomorphism, biclique cover, claw-freeness
Collection: 26th Annual European Symposium on Algorithms (ESA 2018)
Issue Date: 2018
Date of publication: 14.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI