
arXiv: 2008.07967
handle: 21.11116/0000-0006-8BA6-2
For a family of graphs $\mathcal{G}$, the $\mathcal{G}$-\textsc{Contraction} problem takes as an input a graph $G$ and an integer $k$, and the goal is to decide if there exists $F \subseteq E(G)$ of size at most $k$ such that $G/F$ belongs to $\mathcal{G}$. Here, $G/F$ is the graph obtained from $G$ by contracting all the edges in $F$. In this article, we initiate the study of \textsc{Grid Contraction} from the parameterized complexity point of view. We present a fixed parameter tractable algorithm, running in time $c^k \cdot |V(G)|^{\mathcal{O}(1)}$, for this problem. We complement this result by proving that unless Ð fails, there is no algorithm for \textsc{Grid Contraction} with running time $c^{o(k)} \cdot |V(G)|^{\mathcal{O}(1)}$. We also present a polynomial kernel for this problem.
FOS: Computer and information sciences, parameterized algorithms, Discrete Mathematics (cs.DM), FPT, Lower Bound, Parameterized complexity, tractability and kernelization, 004, contraction problem, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, Grid Contraction, kernelization, Kernelization, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, parameterized algorithms, Discrete Mathematics (cs.DM), FPT, Lower Bound, Parameterized complexity, tractability and kernelization, 004, contraction problem, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, Grid Contraction, kernelization, Kernelization, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
