Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952440 | Theoretical Computer Science | 2016 | 14 Pages |
Abstract
We consider the following graph cut problem called Critical Node Cut (CNC): Given a graph G on n vertices, and two positive integers k and x, determine whether G has a set of k vertices whose removal leaves G with at most x connected pairs of vertices. We analyze this problem in the framework of parameterized complexity. That is, we are interested in whether or not this problem is solvable in f(κ)â
nO(1) time (i.e., whether or not it is fixed-parameter tractable), for various natural parameters κ. We consider four such parameters:
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Danny Hermelin, Moshe Kaspi, Christian Komusiewicz, Barak Navon,