English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  A Single-exponential FPT Algorithm for the K4-Minor Cover Problem

Kim, E. J., Paul, C., & Philip, G. (2012). A Single-exponential FPT Algorithm for the K4-Minor Cover Problem. In F. V. Fomin, & P. Kaski (Eds.), Algorithm Theory - SWAT 2012 (pp. 119-130). Berlin: Springer.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-BDEF-A Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0023-C080-B
Genre: Conference Paper
Latex : A Single-exponential {FPT} Algorithm for the {K4-Minor} Cover Problem

Files

show Files
hide Files
:
swat-lncs.pdf (Any fulltext), 336KB
 
File Permalink:
-
Name:
swat-lncs.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Kim, Eun Jung1, Author
Paul, Christophe1, Author
Philip, Geevarghese2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: Given an input graph G on \(n\) vertices and an integer k, the parameterized \textscK_4-minor cover} problem asks whether there is a set S of at most k vertices whose deletion results in a K_4-minor free graph or, equivalently, in a graph of treewidth at most 2. The problem can thus also be called \textsc{Treewidth-2 Vertex Deletion}. This problem is inspired by two well-studied parameterized vertex deletion problems, \textsc{Vertex Cover} and \textsc{Feedback Vertex Set}, which can be expressed as \textsc{Treewidth-t Vertex Deletion} problems: t=0 for {\sc Vertex Cover} and t=1 for {\sc Feedback Vertex Set}. While a single-exponential FPT algorithm has been known for a long time for \textsc{Vertex Cover}, such an algorithm for \textsc{Feedback Vertex Set} was devised comparatively recently. While it is known to be unlikely that \textsc{Treewidth-t Vertex Deletion} can be solved in time c^{o(k)}⋅ n^{O(1)}, it was open whether the \textsc{K_4-minor cover} could be solved in single-exponential FPT time, i.e. in c^k⋅ n^{O(1) time. This paper answers this question in the affirmative.

Details

show
hide
Language(s): eng - English
 Dates: 2012
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1007/978-3-642-31155-0_11
BibTex Citekey: KimPaulPhilip2012
Other: Local-ID: B5AB1D87757A6B6EC1257ACE0013F370-KimPaulPhilip2012
 Degree: -

Event

show
hide
Title: 13th Scandinavian Symposium and Workshops on Algorithm Theory
Place of Event: Helsinki, Finland
Start-/End Date: 2012-07-04 - 2012-07-06

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithm Theory - SWAT 2012
  Subtitle : 13th Scandinavian Symposium and Workshops
  Abbreviation : SWAT 2012
Source Genre: Proceedings
 Creator(s):
Fomin, Fedor V.1, Editor
Kaski, Petteri1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 119 - 130 Identifier: ISBN: 978-3-642-31154-3

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 7357 Sequence Number: - Start / End Page: - Identifier: -