Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Polynomial kernelization for removing induced claws and diamonds

Tools
- Tools
+ Tools

Cygan, Marek, Pilipczuk, Marcin, Pilipczuk, Michał, van Leeuwen, Erik Jan and Wrochna, Marcin (2015) Polynomial kernelization for removing induced claws and diamonds. In: 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), Munich, Germany, 17-19 Jun 2015. Published in: Graph-Theoretic Concepts in Computer Science : 41st International Workshop, WG 2015, Garching, Germany, June 17-19, 2015, Revised Papers, 9224 pp. 450-455. ISBN 9783662531730.

[img] PDF
WRAP_1371795-cs-140815-claw-diamond-deletion.pdf - Accepted Version - Requires a PDF viewer.

Download (714Kb)
Official URL: http://dx.doi.org/10.1007/978-3-662-53174-7_31

Request Changes to record.

Abstract

A graph is called (claw,diamond)-free if it contains neither a claw (a K1,3) nor a diamond (a K4 with an edge removed) as an induced subgraph. Equivalently, (claw,diamond)-free graphs can be characterized as line graphs of triangle-free graphs, or as linear dominoes, i.e., graphs in which every vertex is in at most two maximal cliques and every edge is in exactly one maximal clique.
In this paper we consider the parameterized complexity of the (claw,diamond)-free Edge Deletion problem, where given a graph G and a parameter k, the question is whether one can remove at most k edges from G to obtain a (claw,diamond)-free graph. Our main result is that this problem admits a polynomial kernel. We complement this finding by proving that, even on instances with maximum degree 6, the problem is NP-complete and cannot be solved in time 2o(k)⋅|V(G)|O(1) unless the Exponential Time Hypothesis fail

Item Type: Conference Item (Paper)
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Polynomials, Graph theory
Series Name: Lecture Notes in Computer Science
Journal or Publication Title: Graph-Theoretic Concepts in Computer Science : 41st International Workshop, WG 2015, Garching, Germany, June 17-19, 2015, Revised Papers
Publisher: Springer
ISBN: 9783662531730
Editor: Mayr , Ernst W.
Official Date: 2015
Dates:
DateEvent
2015Accepted
Volume: 9224
Page Range: pp. 450-455
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Date of first compliant deposit: 25 May 2016
Date of first compliant Open Access: 6 September 2016
Funder: Narodowe Centrum Nauki [Polish National Science Center]
Grant number: DEC-2013/11/D/ST6/03073, DEC-2012/05/D/ST6/03214
Conference Paper Type: Paper
Title of Event: 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015)
Type of Event: Conference
Location of Event: Munich, Germany
Date(s) of Event: 17-19 Jun 2015
Related URLs:
  • Publisher
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us