Cygan, Marek, Kratsch, Stefan, Pilipczuk, Marcin, Pilipczuk, Michał and Wahlström, Magnus (2014) Clique cover and graph separation : new incompressibility results. ACM Transactions on Computation Theory, Volume 6 (Number 2). pp. 1-19. doi:10.1145/2594439 ISSN 1942-3454.

Preview

PDF WRAP_1371795-cs-270115-main.pdf - Accepted Version - Requires a PDF viewer. Download (446Kb) | Preview

Request Changes to record.

Abstract

The field of kernelization studies polynomial-time preprocessing routines for hard problems in the framework of parameterized complexity. In this article, we show that, unless the polynomial hierarchy collapses to its third level, the following parameterized problems do not admit a polynomial-time preprocessing algorithm that reduces the size of an instance to polynomial in the parameter:

---Edge Clique Cover, parameterized by the number of cliques, ---Directed Edge/Vertex Multiway Cut, parameterized by the size of the cutset, even in the case of two terminals, ---Edge/Vertex Multicut, parameterized by the size of the cutset, and ---k-Way Cut, parameterized by the size of the cutset.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science, Engineering and Medicine > Science > Centre for Scientific Computing
Library of Congress Subject Headings (LCSH):	Graph theory, Kernel functions
Journal or Publication Title:	ACM Transactions on Computation Theory
Publisher:	ACM
ISSN:	1942-3454
Official Date:	May 2014
Dates:	Date Event May 2014 Published
Volume:	Volume 6
Number:	Number 2
Number of Pages:	19
Page Range:	pp. 1-19
DOI:	10.1145/2594439
Status:	Peer Reviewed
Publication Status:	Published
Date of first compliant deposit:	28 December 2015
Date of first compliant Open Access:	28 December 2015

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads