Carving width

Carving width is NP-hard in general, but may be computed in polynomial time in planar graphs.^[1] It may be approximated to within a constant of the same approximation ratio as balanced cuts,^[3] for which the current best approximation ratio is ${\displaystyle O({\sqrt {\log n}})}$.^[4] It is also fixed-parameter tractable: for any fixed ${\displaystyle k}$, testing whether the carving width is at most ${\displaystyle k}$, and if so finding a hierarchical clustering that realizes that width, can be performed in linear time.^[5] In general, computing the carving width exactly, on a multigraph with ${\displaystyle n}$ vertices and ${\displaystyle m}$ edges, may be done in time ${\displaystyle O(2^{n}n^{3}\log n\log \log n\log m)}$.^[6]

The carving width is only one of several graph width parameters that measure how tree-like a given graph is. Others include the treewidth and branchwidth. The branchwidth of a graph is defined similarly to carving width, using hierarchical clusterings, but of the edges of a graph rather than of its vertices; these are called branch-decompositions. A carving of a graph can be converted into a branch decomposition by attaching each graph edge to one of its two endpoints, and expanding each leaf of a carving into a subtree representing its attached edges. Using this construction, it can be shown that for any graph, the carving width is greater than or equal to half the branch width, and is less than or equal to the degree times the branchwidth. Because treewidth and branchwidth are always within constant factors of each other, similar bounds can be used to relate carving width to treewidth.^[7]

Another width parameter, defined by the numbers of edges spanning cuts in a graph, is its cutwidth, defined using a linear ordering on the vertices of a graph and the system of partitions separating earlier from later vertices in this ordering.^[5] Unlike carving width, this system of partitions does not include a partition separating each vertex from the remaining vertices, so (despite using a more restricted class of families of cuts) the cutwidth can be smaller than the carving width. However, the carving width is always at most the maximum of the cutwidth and the maximum degree of a graph.^[7]