Can I read Contracting Graphs to Split Graphs and Threshold Graphs on EtoBox?

Contracting Graphs to Split Graphs and Threshold Graphs by Cai, Leizhen; Guo, Chengwei is a scholarly article available to read on EtoBox.

What is Contracting Graphs to Split Graphs and Threshold Graphs about?

We study the parameterized complexity of Split Contraction and Threshold Contraction. In these problems we are given a graph G and an integer k and asked whether G can be modified into a split graph or a threshold graph, respectively, by contracting at most k edges. We present an FPT algorithm for Split Contraction, and prove that Threshold Contraction on split graphs, i.e., contracting an input split graph to a threshold graph, is FPT when parameterized by the number of contractions. To give a complete picture, we show that these two problems admit no polynomial kernels unless NP\subseteq coNP/poly.

Author

Cai, Leizhen; Guo, Chengwei

Published

2013

Language

EN