Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
An FPT 2-approximation for tree-cut decomposition
Kim E., Oum S., Paul C., Sau I., Thilikos D. Algorithmica80 (1):116-135,2018.Type:Article
Date Reviewed: May 7 2018

Fixed-parameter tractable (FPT) computational-complexity classification seeks to measure complexity as functions of problems’ parameters. The algorithm presented in this 20-page advanced paper concerns the FPT approach to “constructive parameterized algorithms for computing the tree-cut width of a graph.”

The introductory section posits tree-cut width as an alternative to the treewidth class of graph invariants aimed at enhancing the tractability of NP-hard problems in graph decomposition. The authors’ first result is, that given an integer w, it is NP-hard to decide that a graph G has a tree-cut width tcw(G) of at most w. (The “2-approximation” of the paper’s title indicates the algorithm’s tcw as being at most 2w.) The paper’s algorithm determines either that a graph’s tcw is greater than w, or yields a tree-cut decomposition whose width is at most 2w.

A quantitative comparison of tree-cut-width against treewidth is cited as a proposition: If tcw(G) is equal to w, then treewidth(G) is at most 2w2+3w. There follows a proof that this bound is “asymptotically optimal.” This proof is intricate and delicate.

The paper’s 2-approximation algorithm is presented in the third section, which continues with close and intricate reasoning that also contains many local definitions and resolution of special cases. The subsequent section, “Piecing Everything Together,” serves well in reorienting the reader toward the main result of this paper.

This well-crafted, well-written, and well-organized paper is aimed at experts. It has the weight of an advanced monograph, and will amply reward the careful reader.

Reviewer:  George Hacken Review #: CR146020 (1807-0389)
Bookmark and Share
  Featured Reviewer  
 
Approximation (G.1.2 )
 
 
Algorithm Design And Analysis (G.4 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Approximation": Date
Computing surfaces of constant mean curvature with singularities
Hewgill D. Computing 32(1): 81-92, 1984. Type: Article
Mar 1 1985
A method for the calculation of eigenfunction expansions
Michell J., Drake J., Bracho S. Mathematics and Computers in Simulation XXVI(5): 443-447, 1984. Type: Article
May 1 1985
Calculation of special functions: the gamma function, the exponential integrals and error-like functions
van der Laan C., Temme N., Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands, 1984. Type: Book (9789789061962779)
Jan 1 1986
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