In graph theory, a split of an undirected graph is a cut whose cut-set forms a complete bipartite graph. A graph is prime if it has no splits. The splits of a graph can be collected into a tree-like structure called the split decomposition or join decomposition, which can be constructed in linear time. This decomposition has been used for fast recognition of circle graphs and distance-hereditary graphs, as well as for other problems in graph algorithms.
Splits and split decompositions were first introduced by Cunningham (1982), who also studied variants of the same notions for directed graphs.[1]
Definitions
editA cut of an undirected graph is a partition of the vertices into two nonempty subsets, the sides of the cut. The subset of edges that have one endpoint in each side is called a cut-set. When a cut-set forms a complete bipartite graph, its cut is called a split. Thus, a split can be described as a partition of the vertices of the graph into two subsets X and Y, such that every neighbor of X in Y is adjacent to every neighbor of Y in X.[2]
A cut or split is trivial when one of its two sides has only one vertex in it; every trivial cut is a split. A graph is said to be prime (with respect to splits) if it has no nontrivial splits.[2]
Two splits are said to cross if each side of one split has a non-empty intersection with each side of the other split. A split is called strong when it is not crossed by any other split. As a special case, every trivial split is strong. The strong splits of a graph give rise to a structure called the split decomposition or join decomposition of the graph. This decomposition can be represented by a tree whose leaves correspond one-to-one with the given graph, and whose edges correspond one-to-one with the strong splits of the graph, such that the partition of leaves formed by removing any edge from the tree is the same as the partition of vertices given by the associated strong split.[2]
Each internal node i of the split decomposition tree of a graph G is associated with a graph Gi, called the quotient graph for node i. The quotient graph can be formed by deleting i from the tree, forming subsets of vertices in G corresponding to the leaves in each of the resulting subtrees, and collapsing each of these vertex sets into a single vertex. Every quotient graph has one of three forms: it may be a prime graph, a complete graph, or a star.[2]
A graph may have exponentially many different splits, but they are all represented in the split decomposition tree, either as an edge of the tree (for a strong split) or as an arbitrary partition of a complete or star quotient graph (for a split that is not strong).[2]
Examples
editIn a complete graph or complete bipartite graph, every cut is a split.
In a cycle graph of length four, the partition of the vertices given by 2-coloring the cycle is a nontrivial split, but for cycles of any longer length there are no nontrivial splits.
A bridge of a graph that is not 2-edge-connected corresponds to a split, with each side of the split formed by the vertices on one side of the bridge. The cut-set of the split is just the single bridge edge, which is a special case of a complete bipartite subgraph. Similarly, if v is an articulation point of a graph that is not 2-vertex-connected, then the graph has multiple splits in which v and some but not all of the components formed by its deletion are on one side, and the remaining components are on the other side. In these examples, the cut-set of the split forms a star.
Algorithms
editCunningham (1982) already showed that it is possible to find the split decomposition in polynomial time.[1] After subsequent improvements to the algorithm,[3][4] linear time algorithms were discovered by Dahlhaus (2000)[5] and Charbit, de Montgolfier & Raffinot (2012).[2]
Applications
editSplit decomposition has been applied in the recognition of several important graph classes:
- A distance-hereditary graph is a graph whose split decomposition contains no prime quotients. Based on this characterization, it is possible to use the split decomposition to recognize distance-hereditary graphs in linear time.[6][7]
- Parity graphs can be recognized in linear time as the graphs in which each split quotient is either complete or bipartite.[8]
- A circle graph is the intersection graph of a family of chords of a circle. A given graph is a circle graph if and only if each of the quotients of its split decomposition is a circle graph, so testing whether a graph is a circle graph can be reduced to the same problem on the prime quotient graphs of the graph. More, when a circle graph is prime, the combinatorial structure of the set of chords representing it is uniquely determined, which simplifies the task of recognizing this structure. Based on these ideas, it is possible to recognize circle graphs in polynomial time.[3]
Split decomposition has also been used to simplify the solution of some problems that are NP-hard on arbitrary graphs:[9]
- As Cunningham (1982) already observed, the maximum independent set of any graph may be found by a dynamic programming algorithm on a bottom-up traversal of its split decomposition tree. At each node we choose the maximum weight independent set on its quotient graph, weighted by the sizes of the independent sets already computed at child nodes.[1]
- Although another algorithm given by Cunningham (1982) is flawed, a similar bottom-up traversal can be used to compute the maximum clique of a graph by combining computations of weighted maximum cliques in its quotient graphs.[9]
- Rao (2008) also presents algorithms for connected dominating sets, complete dominating sets, and graph coloring.[9]
These methods can lead to polynomial time algorithms for graphs in which each quotient graph has a simple structure that allows its subproblem to be computed efficiently. For instance, this is true of the graphs in which each quotient graph has constant size.[9]
References
edit- ^ a b c Cunningham, William H. (1982), "Decomposition of directed graphs", SIAM Journal on Algebraic and Discrete Methods, 3 (2): 214–228, doi:10.1137/0603021, MR 0655562.
- ^ a b c d e f Charbit, Pierre; de Montgolfier, Fabien; Raffinot, Mathieu (2012), "Linear time split decomposition revisited", SIAM Journal on Discrete Mathematics, 26 (2): 499–514, arXiv:0902.1700, doi:10.1137/10080052X, MR 2967479.
- ^ a b Gabor, Csaba P.; Supowit, Kenneth J.; Hsu, Wen Lian (1989), "Recognizing circle graphs in polynomial time", Journal of the ACM, 36 (3): 435–473, doi:10.1145/65950.65951, MR 1072233.
- ^ Ma, Tze Heng; Spinrad, Jeremy (1994), "An O(n2) algorithm for undirected split decomposition", Journal of Algorithms, 16 (1): 145–160, doi:10.1006/jagm.1994.1007, MR 1251842.
- ^ Dahlhaus, Elias (2000), "Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition", Journal of Algorithms, 36 (2): 205–240, doi:10.1006/jagm.2000.1090, MR 1769515.
- ^ Gavoille, Cyril; Paul, Christophe (2003), "Distance labeling scheme and split decomposition", Discrete Mathematics, 273 (1–3): 115–130, doi:10.1016/S0012-365X(03)00232-2, MR 2025945.
- ^ Gioan, Emeric; Paul, Christophe (2012), "Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs", Discrete Applied Mathematics, 160 (6): 708–733, arXiv:0810.1823, doi:10.1016/j.dam.2011.05.007.
- ^ Cicerone, Serafino; Di Stefano, Gabriele (1997), "On the equivalence in complexity among basic problems on bipartite and parity graphs", Algorithms and computation (Singapore, 1997), Lecture Notes in Comput. Sci., vol. 1350, Springer, Berlin, pp. 354–363, doi:10.1007/3-540-63890-3_38, ISBN 978-3-540-63890-2, MR 1651043.
- ^ a b c d Rao, Michaël (2008), "Solving some NP-complete problems using split decomposition", Discrete Applied Mathematics, 156 (14): 2768–2780, doi:10.1016/j.dam.2007.11.013, MR 2451095.