Polynomial kernels for leaf power graph modification problems

Description

Niveau: Supérieur, Doctorat, Bac+8
ar X iv :0 80 9. 28 58 v2 [ cs .D M ] 17 Se p 2 00 8 Polynomial kernels for 3-leaf power graph modification problems? S. Bessy C. Paul A. Perez CNRS, LIRMM, Universite Montpellier 2, France † September 17, 2008 Abstract A graph G = (V,E) is a 3-leaf power iff there exists a tree T whose leaves are V and such that (u, v) ? E iff u and v are at distance at most 3 in T . The 3-leaf power graph edge modification problems, i.e. edition (also known as the closest 3-leaf power), completion and edge-deletion, are FTP when parameterized by the size of the edge set modification. However polynomial kernel was known for none of these three problems. For each of them, we provide cubic kernels that can be computed in linear time for each of these problems. We thereby answer an open problem first mentioned by Dom, Guo, Huffner and Niedermeier [6]. ?Research supported by the ANR anr-blan-0148-06project ”Graph Decomposition on Algorithm (GRAAL)” †e-mail: , , perez@lirmm.

• polynomial kernel


• related critical


• leaf power


• power has


• problem


• edge modification


• clique graph

Sujets

• Problem
• Clique (graph theory)

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 9
• Langue: English

Extrait

0-8410-nalb-rnaRDephra”Gctjero6prahceRes ∗ heANdbytortesupp @yssmriliam-eb:[e-mail],p oionAnglocpmsotiRAAL)” † e orithm(G

Abstract A graph G = ( V E ) is a 3-leaf power iff there exists a tree T whose leaves are V and such that ( u v ) ∈ E iff u and v are at distance at most 3 in T . The 3-leaf power graph edge modification problems, i.e. edition (also known as the closest 3 -leaf power ), completion and edge-deletion, are FTP when parameterized by the size of the edge set modification. However polynomial kernel was known for none of these three problems. For each of them, weprovidecubickernelsthatcanbecomputedinlineartimeforeachoftheseproblems.We therebyansweranopenproblemfirstmentionedbyDom,Guo,H¨uffnerandNiedermeier[6].

Polynomial kernels for 3 -leaf power graph modification problems ∗ S. Bessy C. Paul A. Perez CNRS,LIRMM,Universite´Montpellier2,France † September 17, 2008

1 rezer,pfr.fmmir@l