Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Parameterized complexity of critical node cuts
Hermelin D., Kaspi M., Komusiewicz C., Navon B. Theoretical Computer Science651 (C):62-75,2016.Type:Article
Date Reviewed: Feb 13 2017

The critical node cut (CNC) problem is defined as follows: given an (undirected) graph G and two integers k and x, decide if k nodes can be removed from G such that in the resulting subgraph there are at most x pairs of vertices connected by a path. It generalizes various families of well-known graph-cut problems and has numerous applications in real life.

This paper investigates the fixed-parameter tractability (FPT) of CNC: choosing a parameter l like the number k above, is there an algorithm with a complexity bound of the form f(l)p(n), where f is an arbitrary function, p a polynomial, and n the number of vertices (or, equivalently, the size of the input)? A related question is whether or not there exists a polynomial kernel for such l: can any given instance of CNC be reduced in polynomial time to an equivalent instance whose size is polynomially bounded in terms of l? The following parameters are considered: the numbers k and x in the above description of the problem, a lower bound y for the number of connected pairs to be removed, the tree width w of G, and any combination of k, x, y, and w.

The resulting questions are answered almost completely; the only one left open is whether CNC is FPT with respect to parameter k+w. Negative results are obtained conditionally, that is, under the assumptions that the polynomial-time hierarchy and the w-hierarchy do not collapse. In a few cases, the answer is trivial; for instance, CNC reduces to the NP-complete problem VERTEX COVER for x=0, so CNC cannot be FPT with respect to x unless P=NP. Otherwise the solution is derived by providing either an algorithm of desired behavior, or a reduction from a problem of known complexity classification, using constructions that are in some cases quite involved.

Reviewer:  Heinrich Rolletschek Review #: CR145063 (1705-0289)
Bookmark and Share
 
Graph Algorithms (G.2.2 ... )
 
 
Security Kernels (D.4.6 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Graph Algorithms": Date
Planar graph decomposition and all pairs shortest paths
Frederickson G. (ed) Journal of the ACM 38(1): 162-204, 1991. Type: Article
Oct 1 1991
High probability parallel transitive-closure algorithms
Ullman J., Yannakakis M. SIAM Journal on Computing 20(1): 100-125, 1991. Type: Article
Dec 1 1991
Clique partitions, graph compression and speeding-up algorithms
Feder T., Motwani R.  Theory of computing (, New Orleans, LA, May 6-8, 1991)1331991. Type: Proceedings
Oct 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy