Cutwidth

In graph theory, the cutwidth of an undirected graph is the smallest integer ${\displaystyle k}$ with the following property: there is an ordering of the vertices of the graph, such that every cut obtained by partitioning the vertices into earlier and later subsets of the ordering is crossed by at most ${\displaystyle k}$ edges. That is, if the vertices are numbered ${\displaystyle v_{1},v_{2},\dots v_{n}}$, then for every ${\displaystyle \ell =1,2,\dots n-1}$, the number of edges ${\displaystyle v_{i}v_{j}}$ with ${\displaystyle i\leq \ell }$ and ${\displaystyle j>\ell }$ is at most ${\displaystyle k}$.^[1]

A graph of cutwidth 2. For the left-to-right vertex ordering shown, each vertical line crosses at most two edges.

The cutwidth of a graph has also been called its folding number.^[1] Both the vertex ordering that produces the cutwidth, and the problem of computing this ordering and the cutwidth, have been called minimum cut linear arrangement.^[2]

Relation to other parameters

Cutwidth is related to several other width parameters of graphs. In particular, it is always at least as large as the treewidth or pathwidth of the same graph. However, it is at most the pathwidth multiplied by ${\displaystyle O(\Delta )}$ , or the treewidth multiplied by ${\displaystyle O(\Delta \log n)}$  where ${\displaystyle \Delta }$  is the maximum degree and ${\displaystyle n}$  is the number of vertices.^[3][4] If a family of graphs has bounded maximum degree, and its graphs do not contain subdivisions of complete binary trees of unbounded size, then the graphs in the family have bounded cutwidth.^[4] In subcubic graphs (graphs of maximum degree three), the cutwidth equals the pathwidth plus one.^[5]

The cutwidth is greater than or equal to the minimum bisection number of any graph. This is minimum possible number of edges from one side to another for a partition of the vertices into two subsets of equal size (or as near equal as possible). Any linear layout of a graph, achieving its optimal cutwidth, also provides a bisection with the same number of edges, obtained by partitioning the layout into its first and second halves. The cutwidth is less than or equal to the maximum degree multiplied by the graph bandwidth, the maximum number of steps separating the endpoints of any edge in a linear arrangement chosen to minimize this quantity.^[6] Unlike bandwidth, cutwidth is unchanged when edges are subdivided into paths of more than one edge. It is closely related to the "topological bandwidth", the minimum bandwidth that can be obtained by subdividing edges of a given graph. In particular, for any tree it is sandwiched between the topological bandwidth ${\displaystyle b^{*}}$  and a slightly larger number, ${\displaystyle b^{*}+\log _{2}b^{*}+2}$ .^[1]

Another parameter, defined similarly to cutwidth in terms of numbers of edges spanning cuts in a graph, is the carving width. However, instead of using a linear ordering of vertices and a linear sequence of cuts, as in cutwidth, carving width uses cuts derived from a hierarchical clustering of vertices, making it more closely related to treewidth or branchwidth and less similar to the other width parameters involving linear orderings such as pathwidth or bandwidth.^[7]

Cutwidth can be used to provide a lower bound on another parameter, the crossing number, arising in the study of graph drawings. The crossing number of a graph is the minimum number of pairs of edges that intersect, in any drawing of the graph in the plane where each vertex touches only the edges for which it is an endpoint. In graphs of bounded degree, the crossing number is always at least proportional to the square of the cutwidth. A more precise bound, applying to graphs where the degrees are not bounded, is:^[8]

$${\displaystyle \operatorname {crossings} (G)\geq {\frac {1}{1176}}\operatorname {cutwidth} (G)^{2}-\sum _{v\in V(G)}\left({\frac {\deg(v)}{4}}\right)^{2}.}$$

 

Here, the correction term, proportional to the sum of squared degrees, is necessary to account for the existence of planar graphs whose squared cutwidth is proportional to this quantity but whose crossing number is zero.^[8] In another style of graph drawing, book embedding, vertices are arranged on a line and edges are arranged without crossings into separate half-plane pages meeting at this line. The page width of a book embedding has been defined as the largest cutwidth of any of the pages, using the same vertex ordering.^[9]

Computational complexity

The cutwidth can be found, and a linear layout of optimal width constructed, in time ${\displaystyle O(n\log n)}$  for a tree of ${\displaystyle n}$  vertices.^[10] For more general graphs, it is NP-hard. It remains NP-hard even for planar graphs of maximum degree three, and a weighted version of the problem (minimizing the weight of edges across any cut of a linear arrangement) is NP-hard even when the input is a tree.^[11]

Cutwidth is one of many problems of optimal linear arrangement that can be solved exactly in time ${\displaystyle O(n2^{n})}$  by the Held-Karp algorithm, using dynamic programming.^[12] A faster quantum algorithm with time ${\displaystyle O(1.817^{n})}$  is also known.^[13] Additionally, it is fixed-parameter tractable: for any fixed value of ${\displaystyle c}$ , it is possible to test whether a graph has cutwidth at most ${\displaystyle c}$ , and if so find an optimal vertex ordering for it, in linear time.^[2] More precisely, in terms of both ${\displaystyle n}$  and ${\displaystyle c}$ , the running time of this algorithm is ${\textstyle 2^{O(c^{2})}n}$ .^[14] An alternative parameterized algorithm, more suitable for graphs in which a small number of vertices have high degree (making the cutwidth large) instead solves the problem in time polynomial in ${\displaystyle n}$  when the graph has a vertex cover of bounded size, by transforming it into an integer programming problem with few variables and polynomial bounds on the variable values. It remains open whether the problem can be solved efficiently for graphs of bounded treewidth, which would subsume both of the parameterizations by cutwidth and vertex cover number.^[15]

Cutwidth has a polynomial-time approximation scheme for dense graphs,^[16] but for graphs that might not be dense the best approximation ratio known is ${\textstyle O{\bigl (}(\log n)^{3/2}{\bigr )}}$ .^[17] This comes from a method of Tom Leighton and Satish Rao for reducing approximate cutwidth to minimum bisection number, losing a factor of ${\displaystyle \log _{2}n}$  in the approximation ratio, by using recursive bisection to order the vertices.^[18] Combining this recursive bisection method with another method of Sanjeev Arora, Rao, and Umesh Vazirani for approximating the minimum bisection number,^[19] gives the stated approximation ratio.^[17] Under the small set expansion hypothesis, it is not possible to achieve a constant approximation ratio.^[17]

Applications

 

A channel routing problem, in which pairs of numbered pins must be connected along horizontal "channels" in a rectangular area

 

Solution using five channels

An early motivating application for cutwidth involved channel routing in VLSI design, in which components arranged along the top and bottom of a rectangular region of an integrated circuit should be connected by conductors that connect pairs pins attached to the components. If the components are free to be arranged into different left-to-right orders, but the pins of each component must remain contiguous, then this can be translated into a problem of choosing a linear arrangement of a graph with a vertex for each component and an edge for each pin-to-pin connection. The cutwidth of the graph controls the number of channels needed to route the circuit.^[5]

In protein engineering, an assumption that an associated graph has bounded cutwidth has been used to speed up the search for mRNA sequences that simultaneously code for a given protein sequence and fold into a given secondary structure.^[20]

A weighted variant of the problem applying to directed acyclic graphs, and only allowing linear orderings consistent with the orientation of the graph edges, has been applied to schedule a sequence of computational tasks in a way that minimizes the maximum amount of memory required in the schedule, both for the tasks themselves and to maintain the data used for task-to-task communication.^[21] In database theory, the NP-hardness of the cutwidth problem has been used to show that it is also NP-hard to schedule the transfer of blocks of data between a disk and main memory when performing a join, in order to avoid repeated transfers of the same block while fitting the computation within a limited amount of main memory.^[22]

In graph drawing, as well as being applied in the lower bound for crossing number,^[8] cutwidth has been applied in the study of a specific type of three-dimensional graph drawing, in which the edge are represented as disjoint polygonal chains with at most one bend, the vertices are placed on a line, and all vertices and bend points must have integer coordinates. For drawings of this type, the minimum volume of a bounding box of the drawing must be at least proportional to the cutwidth multiplied by the number of vertices. There always exists a drawing with this volume, with the vertices placed on an axis-parallel line.^[23]

References

1. Chung, Fan R. K. (1985). "On the cutwidth and the topological bandwidth of a tree" (PDF). SIAM Journal on Algebraic and Discrete Methods. 6 (2): 268–277. doi:10.1137/0606026. MR 0778007.
2. Thilikos, Dimitrios M.; Serna, Maria; Bodlaender, Hans L. (2005). "Cutwidth I: A linear time fixed parameter algorithm" (PDF). Journal of Algorithms. 56 (1): 1–24. doi:10.1016/j.jalgor.2004.12.001. MR 2146375.
3. Korach, Ephraim; Solel, Nir (1993). "Tree-width, path-width, and cutwidth". Discrete Applied Mathematics. 43 (1): 97–101. doi:10.1016/0166-218X(93)90171-J. MR 1218045.
4. Chung, F. R. K.; Seymour, P. D. (1989). "Graphs with small bandwidth and cutwidth" (PDF). Discrete Mathematics. 75 (1–3): 113–119. doi:10.1016/0012-365X(89)90083-6. MR 1001391.
5. Makedon, Fillia; Sudborough, Ivan Hal (1989). "On minimizing width in linear layouts". Discrete Applied Mathematics. 23 (3): 243–265. doi:10.1016/0166-218X(89)90016-4. MR 0996137.
6. Díaz, Josep; Petit, Jordi; Serna, Maria (September 2002). "A survey of graph layout problems" (PDF). ACM Computing Surveys. 34 (3): 313–356. doi:10.1145/568522.568523.
7. Seymour, Paul D.; Thomas, Robin (1994). "Call routing and the ratcatcher". Combinatorica. 14 (2): 217–241. doi:10.1007/BF01215352.
8. Djidjev, Hristo N.; Vrt'o, Imrich (2003). "Crossing numbers and cutwidths". Journal of Graph Algorithms and Applications. 7 (3): 245–251. doi:10.7155/jgaa.00069. MR 2112230.
9. Stöhr, Elena (1988). "A trade-off between page number and page width of book embeddings of graphs". Information and Computation. 79 (2): 155–162. doi:10.1016/0890-5401(88)90036-3. MR 0968104.
10. Yannakakis, Mihalis (1985). "A polynomial algorithm for the min-cut linear arrangement of trees". Journal of the ACM. 32 (4): 950–988. doi:10.1145/4221.4228. MR 0810346.
11. Monien, B.; Sudborough, I. H. (1988). "Min cut is NP-complete for edge weighted trees". Theoretical Computer Science. 58 (1–3): 209–229. doi:10.1016/0304-3975(88)90028-X. MR 0963264.
12. Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M. (2012). "A note on exact algorithms for vertex ordering problems on graphs". Theory of Computing Systems. 50 (3): 420–432. doi:10.1007/s00224-011-9312-0. hdl:1956/4556. MR 2885638. S2CID 9967521.
13. Ambainis, Andris; Balodis, Kaspars; Iraids, Jānis; Kokainis, Martins; Prūsis, Krišjānis; Vihrovs, Jevgēnijs (2019). "Quantum speedups for exponential-time dynamic programming algorithms". In Chan, Timothy M. (ed.). Proceedings of the Thirtieth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6–9, 2019. Society for Industrial and Applied Mathematics. pp. 1783–1793. arXiv:1807.05209. doi:10.1137/1.9781611975482.107. MR 3909576.
14. Giannopoulou, Archontia C.; Pilipczuk, Jean-Florent, Michałand Raymond; Thilikos, Dimitrios M.; Wrochna, Marcin (2019). "Cutwidth: obstructions and algorithmic aspects" (PDF). Algorithmica. 81 (2): 557–588. doi:10.1007/s00453-018-0424-7. MR 3910081.{{cite journal}}: CS1 maint: multiple names: authors list (link)
15. Fellows, Michael R.; Lokshtanov, Daniel; Misra, Neeldhara; Rosamond, Frances A.; Saurabh, Saket (2008). "Graph layout problems parameterized by vertex cover" (PDF). In Hong, Seok-Hee; Nagamochi, Hiroshi; Fukunaga, Takuro (eds.). Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15–17, 2008, Proceedings. Lecture Notes in Computer Science. Vol. 5369. Springer. pp. 294–305. doi:10.1007/978-3-540-92182-0_28.
16. Arora, Sanjeev; Frieze, Alan; Kaplan, Haim (2002). "A new rounding procedure for the assignment problem with applications to dense graph arrangement problems". Mathematical Programming. 92 (1, Ser. A): 1–36. doi:10.1007/s101070100271. MR 1892295.
17. Wu, Yu; Austrin, Per; Pitassi, Toniann; Liu, David (2014). "Inapproximability of treewidth, one-shot pebbling, and related layout problems". Journal of Artificial Intelligence Research. 49: 569–600. doi:10.1613/jair.4030. MR 3195329.
18. Leighton, Tom; Rao, Satish (1999). "Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms". Journal of the ACM. 46 (6): 787–832. doi:10.1145/331524.331526. MR 1753034.
19. Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009). "Expander flows, geometric embeddings and graph partitioning" (PDF). Journal of the ACM. 56 (2): Art. 5, 37. doi:10.1145/1502793.1502794. MR 2535878.
20. Blin, Guillaume; Fertin, Guillaume; Hermelin, Danny; Vialette, Stéphane (2008). "Fixed-parameter algorithms for protein similarity search under mRNA structure constraints". Journal of Discrete Algorithms. 6 (4): 618–626. doi:10.1016/j.jda.2008.03.004. MR 2463425.
21. Kayaaslan, Enver; Lambert, Thomas; Marchal, Loris; Uçar, Bora (2018). "Scheduling series-parallel task graphs to minimize peak memory". Theoretical Computer Science. 707: 1–23. doi:10.1016/j.tcs.2017.09.037. MR 3734396.
22. Fotouhi, Farshad; Pramanik, Sakti (1991). "Problem of optimizing the number of block accesses in performing relational join is NP-hard". Information Processing Letters. 38 (5): 271–275. doi:10.1016/0020-0190(91)90070-X. MR 1114421.
23. Morin, Pat; Wood, David R. (2004). "Three-dimensional 1-bend graph drawings". Journal of Graph Algorithms and Applications. 8 (3): 357–366. doi:10.7155/jgaa.00095. MR 2176967.