Carving width

In graph theory, the carving width of a graph is a number, defined from the graph, that describes the number of edges separating the clusters in a hierarchical clustering of the graph vertices.

Definition and examples

The carving width is defined in terms of hierarchical clusterings of the vertices of a given graph, called "carvings". A carving can be described as an unrooted binary tree whose leaves are labeled with the vertices of the given graph. Removing any edge from this tree partitions the tree into two subtrees, and correspondingly partitions the vertices of the tree into two clusters. The vertex clusters, formed in this way, constitute a laminar set family: any two vertex clusters (not just the two complementary clusters formed by removing the same edge) are either disjoint, or one is contained in the other. The width of a carving, defined in this way, is the maximum number of edges that connect two complementary clusters. The carving width of the graph is the minimum width of any hierarchical clustering. ^[1]

The graphs of carving width one are exactly the matchings. The graphs of carving width two are exactly those formed from disjoint unions of path graphs and cycle graphs. The graphs of carving width three are the subcubic partial 2-trees. This means that their maximum degree is three and that they are subgraphs of series-parallel graphs. All other graphs have carving width at least four. ^[2]

Computational complexity

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]

Related parameters

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]

References

1. Seymour, Paul D.; Thomas, Robin (1994), "Call routing and the ratcatcher", Combinatorica, 14 (2): 217–241, doi:10.1007/BF01215352, S2CID   7508434
2. Belmonte, Rémy; van 't Hof, Pim; Kamiński, Marcin; Paulusma, Daniël; Thilikos, Dimitrios M. (2013), "Characterizing graphs of small carving-width", Discrete Applied Mathematics , 161 (13–14): 1888–1893, doi: 10.1016/j.dam.2013.02.036 , MR   3056995
3. Khuller, Samir; Raghavachari, Balaji; Young, Neal (April 1994), "Designing multi-commodity flow trees", Information Processing Letters, 50 (1): 49–55, arXiv: cs/0205077 , doi:10.1016/0020-0190(94)90044-2
4. Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009), "Expander flows, geometric embeddings and graph partitioning" (PDF), Journal of the ACM , 56 (2): A5:1–A5:37, doi:10.1145/1502793.1502794, MR   2535878, S2CID   263871111
5. Thilikos, Dimitrios M.; Serna, Maria J.; Bodlaender, Hans L. (2000), "Constructive linear time algorithms for small cutwidth and carving-width", in Lee, D. T.; Teng, Shang-Hua (eds.), Algorithms and Computation, 11th International Conference, ISAAC 2000, Taipei, Taiwan, December 18-20, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1969, Springer, pp. 192–203, doi:10.1007/3-540-40996-3_17, ISBN   978-3-540-41255-7
6. Oum, Sang-il (2009), "Computing rank-width exactly", Information Processing Letters, 109 (13): 745–748, CiteSeerX   10.1.1.483.6708 , doi:10.1016/j.ipl.2009.03.018, MR   2527717
7. Eppstein, David (2018), "The effect of planarization on width", Journal of Graph Algorithms & Applications, 22 (3): 461–481, arXiv: 1708.05155 , doi:10.7155/jgaa.00468, S2CID   28517765