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.
