On the (non-)existence of polynomial kernels for $P_l$-free edge modification problems. Guillemot, S., Paul, C., & Perez, A. Technical Report 2010. arXiv:1007.4011![On the (non-)existence of polynomial kernels for $P_l$-free edge modification problems [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper abstract bibtex Given a graph $G=(V,E)$ and an integer $k$, an edge modification problem for a graph property $Π$ consists in deciding whether there exists a set of edges $F$ of size at most $k$ such that the graph $H=(V,E▵ F)$ satisfies the property $Π$. In the $Π$ edge-completion problem, the set $F$ of edges is constrained to be disjoint from $E$; in the $Π$ edge-deletion problem, $F$ is a subset of $E$; no constraint is imposed on $F$ in the $Π$ edge-edition problem. A number of optimization problems can be expressed in terms of graph modification problems which have been extensively studied in the context of parameterized complexity. When parameterized by the size $k$ of the edge set $F$, it has been proved that if $Π$ is an hereditary property characterized by a finite set of forbidden induced subgraphs, then the three $Π$ edge-modification problems are FPT. It was then natural to ask whether these problems also admit a polynomial size kernel. Using recent lower bound techniques, Kratsch and Wahlström answered this question negatively. However, the problem remains open on many natural graph classes characterized by forbidden induced subgraphs. Kratsch and Wahlström asked whether the result holds when the forbidden subgraphs are paths or cycles and pointed out that the problem is already open in the case of $P_4$-free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that parameterized cograph edge modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for the $P_l$-free and $C_l$-free edge-deletion problems for large enough $l$.
@TechReport{guillemot10nonexistence,
author = {Sylvain Guillemot and Christophe Paul and Anthony Perez},
title = {On the (non-)existence of polynomial kernels for $P_l$-free edge modification problems},
year = {2010},
note = {arXiv:1007.4011},
abstract = {Given a graph $G=(V,E)$ and an integer $k$, an edge modification problem for a graph property $\Pi$ consists in deciding whether there exists a set of edges $F$ of size at most $k$ such that the graph $H=(V,E\vartriangle F)$ satisfies the property $\Pi$. In the $\Pi$ edge-completion problem, the set $F$ of edges is constrained to be disjoint from $E$; in the $\Pi$ edge-deletion problem, $F$ is a subset of $E$; no constraint is imposed on $F$ in the $\Pi$ edge-edition problem.
A number of optimization problems can be expressed in terms of graph modification problems which have been extensively studied in the context of parameterized complexity. When parameterized by the size $k$ of the edge set $F$, it has been proved that if $\Pi$ is an hereditary property characterized by a finite set of forbidden induced subgraphs, then the three $\Pi$ edge-modification problems are FPT. It was then natural to ask whether these problems also admit a polynomial size kernel.
Using recent lower bound techniques, Kratsch and Wahlstr\"om answered this question negatively. However, the problem remains open on many natural graph classes characterized by forbidden induced subgraphs.
Kratsch and Wahlstr\"om asked whether the result holds when the forbidden subgraphs are paths or cycles and pointed out that the problem is already open in the case of $P_4$-free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that parameterized cograph edge modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for the $P_l$-free and $C_l$-free edge-deletion problems for large enough $l$.},
file = {GuillemotEtAl_NonExistencePolynomialKernels_CoRR_2010.pdf:2010/GuillemotEtAl_NonExistencePolynomialKernels_CoRR_2010.pdf:PDF},
keywords = {jena;},
owner = {marcusL},
timestamp = {Mon, 05 Dec 2011 18:04:25 +0100},
url = {http://arxiv.org/abs/1007.4011},
}
Downloads: 0
{"_id":"27tTAn5CvyLmvuPHr","bibbaseid":"guillemot-paul-perez-onthenonexistenceofpolynomialkernelsforplfreeedgemodificationproblems-2010","author_short":["Guillemot, S.","Paul, C.","Perez, A."],"bibdata":{"bibtype":"techreport","type":"techreport","author":[{"firstnames":["Sylvain"],"propositions":[],"lastnames":["Guillemot"],"suffixes":[]},{"firstnames":["Christophe"],"propositions":[],"lastnames":["Paul"],"suffixes":[]},{"firstnames":["Anthony"],"propositions":[],"lastnames":["Perez"],"suffixes":[]}],"title":"On the (non-)existence of polynomial kernels for $P_l$-free edge modification problems","year":"2010","note":"arXiv:1007.4011","abstract":"Given a graph $G=(V,E)$ and an integer $k$, an edge modification problem for a graph property $Π$ consists in deciding whether there exists a set of edges $F$ of size at most $k$ such that the graph $H=(V,E▵ F)$ satisfies the property $Π$. In the $Π$ edge-completion problem, the set $F$ of edges is constrained to be disjoint from $E$; in the $Π$ edge-deletion problem, $F$ is a subset of $E$; no constraint is imposed on $F$ in the $Π$ edge-edition problem. A number of optimization problems can be expressed in terms of graph modification problems which have been extensively studied in the context of parameterized complexity. When parameterized by the size $k$ of the edge set $F$, it has been proved that if $Π$ is an hereditary property characterized by a finite set of forbidden induced subgraphs, then the three $Π$ edge-modification problems are FPT. It was then natural to ask whether these problems also admit a polynomial size kernel. Using recent lower bound techniques, Kratsch and Wahlström answered this question negatively. However, the problem remains open on many natural graph classes characterized by forbidden induced subgraphs. Kratsch and Wahlström asked whether the result holds when the forbidden subgraphs are paths or cycles and pointed out that the problem is already open in the case of $P_4$-free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that parameterized cograph edge modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for the $P_l$-free and $C_l$-free edge-deletion problems for large enough $l$.","file":"GuillemotEtAl_NonExistencePolynomialKernels_CoRR_2010.pdf:2010/GuillemotEtAl_NonExistencePolynomialKernels_CoRR_2010.pdf:PDF","keywords":"jena;","owner":"marcusL","timestamp":"Mon, 05 Dec 2011 18:04:25 +0100","url":"http://arxiv.org/abs/1007.4011","bibtex":"@TechReport{guillemot10nonexistence,\n author = {Sylvain Guillemot and Christophe Paul and Anthony Perez},\n title = {On the (non-)existence of polynomial kernels for $P_l$-free edge modification problems},\n year = {2010},\n note = {arXiv:1007.4011},\n abstract = {Given a graph $G=(V,E)$ and an integer $k$, an edge modification problem for a graph property $\\Pi$ consists in deciding whether there exists a set of edges $F$ of size at most $k$ such that the graph $H=(V,E\\vartriangle F)$ satisfies the property $\\Pi$. In the $\\Pi$ edge-completion problem, the set $F$ of edges is constrained to be disjoint from $E$; in the $\\Pi$ edge-deletion problem, $F$ is a subset of $E$; no constraint is imposed on $F$ in the $\\Pi$ edge-edition problem. \nA number of optimization problems can be expressed in terms of graph modification problems which have been extensively studied in the context of parameterized complexity. When parameterized by the size $k$ of the edge set $F$, it has been proved that if $\\Pi$ is an hereditary property characterized by a finite set of forbidden induced subgraphs, then the three $\\Pi$ edge-modification problems are FPT. It was then natural to ask whether these problems also admit a polynomial size kernel.\nUsing recent lower bound techniques, Kratsch and Wahlstr\\\"om answered this question negatively. However, the problem remains open on many natural graph classes characterized by forbidden induced subgraphs.\nKratsch and Wahlstr\\\"om asked whether the result holds when the forbidden subgraphs are paths or cycles and pointed out that the problem is already open in the case of $P_4$-free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that parameterized cograph edge modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for the $P_l$-free and $C_l$-free edge-deletion problems for large enough $l$.},\n file = {GuillemotEtAl_NonExistencePolynomialKernels_CoRR_2010.pdf:2010/GuillemotEtAl_NonExistencePolynomialKernels_CoRR_2010.pdf:PDF},\n keywords = {jena;},\n owner = {marcusL},\n timestamp = {Mon, 05 Dec 2011 18:04:25 +0100},\n url = {http://arxiv.org/abs/1007.4011},\n}\n\n","author_short":["Guillemot, S.","Paul, C.","Perez, A."],"key":"guillemot10nonexistence","id":"guillemot10nonexistence","bibbaseid":"guillemot-paul-perez-onthenonexistenceofpolynomialkernelsforplfreeedgemodificationproblems-2010","role":"author","urls":{"Paper":"http://arxiv.org/abs/1007.4011"},"keyword":["jena;"],"metadata":{"authorlinks":{}}},"bibtype":"techreport","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","dataSources":["C5FtkvWWggFfMJTFX"],"keywords":["jena;"],"search_terms":["non","existence","polynomial","kernels","free","edge","modification","problems","guillemot","paul","perez"],"title":"On the (non-)existence of polynomial kernels for $P_l$-free edge modification problems","year":2010}