Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Kratsch, Stefan
Wahlström, Magnus

dblp
dblp



Editor(s):

Chen, Jianer
Fomin, Fedor V.

dblp
dblp

Not MPII Editor(s):

Chen, Jianer
Fomin, Fedor V.

BibTeX cite key*:

KratschW2009

Title, Booktitle

Title*:

Two Edge Modification Problems without Polynomial Kernels

Booktitle*:

Parameterized and Exact Computation : 4th International Workshop, IWPEC 2009

Event, URLs

URL of the conference:


URL for downloading the paper:

http://dx.doi.org/10.1007/978-3-642-11269-0_22

Event Address*:

Denmark, Copenhagen

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

10 September 2009

Event End Date:

11 September 2009

Publisher

Name*:

Springer

URL:


Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

5917

Number:


Month:

September

Pages:

264-275

Year*:

2009

VG Wort Pages:

25

ISBN/ISSN:

978-3-642-11268-3

Sequence Number:


DOI:

10.1007/978-3-642-11269-0_22



Note, Abstract, ©


(LaTeX) Abstract:

Given a graph G and an integer k, the Pi Edge Completion/Editing/Deletion problem asks whether it is possible to add, edit, or delete at most k edges in G such that one obtains a graph that fulfills the property Pi. Edge modification problems have received considerable interest from a parameterized point of view. When parameterized by k, many of these problems turned out to be fixed-parameter tractable and some are known to admit polynomial kernelizations, i.e., efficient preprocessing with a size guarantee that is polynomial in k. This paper answers an open problem posed by Cai (IWPEC 2006), namely, whether the Pi Edge Deletion problem, parameterized by the number of deletions, admits a polynomial kernelization when Pi can be characterized by a finite set of forbidden induced subgraphs. We answer this question negatively based on recent work by Bodlaender et al. (ICALP 2008) which provided a framework for proving polynomial lower bounds for kernelizability. We present a graph H on seven vertices such that H-free Edge Deletion and H-free Edge Editing do not admit polynomial kernelizations, unless the polynomial hierarchy collapses. The application of the framework is not immediate and requires a lower bound for a Min Ones SAT problem that may be of independent interest.

Keywords:

Parameterized Complexity, Kernelization, Graph Modification Problems



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{KratschW2009,
AUTHOR = {Kratsch, Stefan and Wahlstr{\"o}m, Magnus},
EDITOR = {Chen, Jianer and Fomin, Fedor V.},
TITLE = {Two Edge Modification Problems without Polynomial Kernels},
BOOKTITLE = {Parameterized and Exact Computation : 4th International Workshop, IWPEC 2009},
PUBLISHER = {Springer},
YEAR = {2009},
VOLUME = {5917},
PAGES = {264--275},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Denmark, Copenhagen},
MONTH = {September},
ISBN = {978-3-642-11268-3},
DOI = {10.1007/978-3-642-11269-0_22},
}


Entry last modified by Anja Becker, 03/08/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
02/04/2010 12:35:13 PM
Revision
1.
0.


Editor
Anja Becker
Stefan Kratsch


Edit Date
08.03.2010 14:25:38
02/04/2010 12:35:13 PM


Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section