Split (graph theory)

Last updated
A graph with two nontrivial strong splits (top) and its split decomposition (bottom). The three quotient graphs are a star (left), a prime graph (center), and a complete graph (right). Split decomposition.svg
A graph with two nontrivial strong splits (top) and its split decomposition (bottom). The three quotient graphs are a star (left), a prime graph (center), and a complete graph (right).

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.

Contents

Splits and split decompositions were first introduced by Cunningham (1982), who also studied variants of the same notions for directed graphs. [1]

Definitions

A 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

In 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

Cunningham (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

Split decomposition has been applied in the recognition of several important graph classes:

Split decomposition has also been used to simplify the solution of some problems that are NP-hard on arbitrary graphs: [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]

Related Research Articles

<span class="mw-page-title-main">Bipartite graph</span> Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Eulerian path</span> Trail in a graph that visits each edge once

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

<span class="mw-page-title-main">Independent set (graph theory)</span> Unrelated vertices in graphs

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

<span class="mw-page-title-main">Edge coloring</span> Problem of coloring a graphs edges such that meeting edges do not match

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.

The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is k-arboric.

<span class="mw-page-title-main">Dual graph</span> Graph representing faces of another graph

In the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.

<span class="mw-page-title-main">Factor-critical graph</span> Graph of n vertices with a perfect matching for every subgraph of n-1 vertices

In graph theory, a mathematical discipline, a factor-critical graph is a graph with n vertices in which every subgraph of n − 1 vertices has a perfect matching.

<span class="mw-page-title-main">Pseudoforest</span> Graph with one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

<span class="mw-page-title-main">Distance-hereditary graph</span> Graph whose induced subgraphs preserve distance

In graph theory, a branch of discrete mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an n-vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

<span class="mw-page-title-main">Hamiltonian decomposition</span>

In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs. In the undirected case a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected.

In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition.

<span class="mw-page-title-main">Odd cycle transversal</span>

In graph theory, an odd cycle transversal of an undirected graph is a set of vertices of the graph that has a nonempty intersection with every odd cycle in the graph. Removing the vertices of an odd cycle transversal from a graph leaves a bipartite graph as the remaining induced subgraph.

<span class="mw-page-title-main">Graham–Pollak theorem</span>

In graph theory, the Graham–Pollak theorem states that the edges of an -vertex complete graph cannot be partitioned into fewer than complete bipartite graphs. It was first published by Ronald Graham and Henry O. Pollak in two papers in 1971 and 1972, in connection with an application to telephone switching circuitry.

References

  1. 1 2 3 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 .
  2. 1 2 3 4 5 6 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 .
  3. 1 2 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 .
  4. ↑ 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 .
  5. ↑ 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 .
  6. ↑ 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 .
  7. ↑ 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 .
  8. ↑ 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 .
  9. 1 2 3 4 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 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.