Graph sandwich problem

Last updated

In graph theory and computer science, the graph sandwich problem is a problem of finding a graph that belongs to a particular family of graphs and is "sandwiched" between two other graphs, one of which must be a subgraph and the other of which must be a supergraph of the desired graph.

Graph theory Area of discrete mathematics

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

Computer science Study of the theoretical foundations of information and computation

Computer science is the study of processes that interact with data and that can be represented as data in the form of programs. It enables the use of algorithms to manipulate, store, and communicate digital information. A computer scientist studies the theory of computation and the practice of designing software systems.

Contents

Graph sandwich problems generalize the problem of testing whether a given graph belongs to a family of graphs, and have attracted attention because of their applications and as a natural generalization of recognition problems. [1]

Problem statement

More precisely, given a vertex set V, a mandatory edge set E1, and a larger edge set E2, a graph G = (V, E) is called a sandwich graph for the pair G1 = (V, E1), G2 = (V, E2) if E1 ⊆ E ⊆ E2. The graph sandwich problem for property Π is defined as follows: [2] [3]

Graph Sandwich Problem for Property Π:
Instance: Vertex set V and edge sets E1 ⊆ E2 ⊆ V × V.
Question: Is there a graph G = (V, E) such that E1 ⊆ E ⊆ E2 and G satisfies property Π ?

The recognition problem for a class of graphs (those satisfying a property Π) is equivalent to the particular graph sandwich problem where E1 = E2, that is, the optional edge set is empty.

Computational complexity

The graph sandwich problem is NP-complete when Π is the property of being a chordal graph, comparability graph, permutation graph, chordal bipartite graph, or chain graph. [2] [4] It can be solved in polynomial time for split graphs, [2] [5] threshold graphs, [2] [5] and graphs in which every five vertices contain at most one four-vertex induced path. [6] The complexity status has also been settled for the H-free graph sandwich problems for each of the four-vertex graphs H. [7]

Chordal graph

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 comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, containment graphs, and divisor graphs. An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order.

Permutation graph graph whose vertices represent the elements of a permutation

In mathematics, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation if it is prime with respect to the modular decomposition.

Related Research Articles

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

In graph theory, two graphs and are homeomorphic if there is a graph isomorphism from some subdivision of to some subdivision of . If the edges of a graph are thought of as lines drawn from one vertex to another, then two graphs are homeomorphic to each other in the graph-theoretic sense precisely if they are homeomorphic in the sense in which the term is used in topology.

Interval graph the intersection graph of a collection of intervals of the real line

In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals.

Clique (graph theory) subset of the vertices of a node-link graph that are all adjacent to each other

In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.

Perfect graph type of graph (mathematical structure)

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. Equivalently stated in symbolic terms an arbitrary graph is perfect if and only if we have:

In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.

Cograph a type of graph, formed recursively by complementation and disjoint union operations

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.

In graph theory, a clique graph of an undirected graph G is another graph K(G) that represents the structure of cliques in G.

Triangle-free graph undirected graph in which no three vertices form a triangle of edges

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

Split graph

In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer, and independently introduced by Tyshkevich and Chernyak (1979).

Clique-width

In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs. It is defined as the minimum number of labels needed to construct by means of the following 4 operations :

  1. Creation of a new vertex v with label i
  2. Disjoint union of two labeled graphs G and H
  3. Joining by an edge every vertex labeled i to every vertex labeled j, where
  4. Renaming label i to label j
Distance-hereditary graph

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.

Trivially perfect graph

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs.

In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.

In the mathematical area of graph theory, an undirected graph G is strongly chordal if it is a chordal graph and every cycle of even length in G has an odd chord, i.e., an edge that connects two vertices that are an odd distance (>1) apart from each other in the cycle.

Skew partition

In graph theory, a skew partition of a graph is a partition of its vertices into two subsets, such that the induced subgraph formed by one of the two subsets is disconnected and the induced subgraph formed by the other subset is the complement of a disconnected graph. Skew partitions play an important role in the theory of perfect graphs.

In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals. Based on these two types of interval representations, these graphs are also called unit interval graphs or proper interval graphs; they form a subclass of the interval graphs.

In the mathematical area of graph theory, a chordal bipartite graph is a bipartite graph B = (X,Y,E) in which every cycle of length at least 6 in B has a chord, i.e., an edge that connects two vertices that are a distance > 1 apart from each other in the cycle. A better name would be weakly chordal and bipartite since chordal bipartite graphs are in general not chordal as the induced cycle of length 4 shows.

References

  1. ↑ Golumbic, Martin Charles; Trenk, Ann N. (2004), "Chapter 4. Interval probe graphs and sandwich problems", Tolerance Graphs, Cambridge, pp. 63–83.
  2. 1 2 3 4 Golumbic, Martin Charles; Kaplan, Haim; Shamir, Ron (1995), "Graph sandwich problems", J. Algorithms, 19: 449–473, doi:10.1006/jagm.1995.1047 .
  3. ↑ Golumbic, Martin Charles (2004), Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, 57 (2nd ed.), Elsevier, p. 279.
  4. ↑ de Figueiredo, C. M. H.; Faria, L.; Klein, S.; Sritharan, R. (2007), "On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs", Theoretical Computer Science , 381 (1–3): 57–67, doi:10.1016/j.tcs.2007.04.007, MR   2347393 .
  5. 1 2 Mahadev, N.V.R.; Peled, Uri N. (1995), Threshold Graphs and Related Topics, Annals of Discrete Mathematics, 57, North-Holland, pp. 19–22.
  6. ↑ Dantas, S.; Klein, S.; Mello, C.P.; Morgana, A. (2009), "The graph sandwich problem for P4-sparse graphs", Discrete Mathematics , 309: 3664–3673, doi:10.1016/j.disc.2008.01.014 .
  7. ↑ Dantas, Simone; de Figueiredo, Celina M.H.; Maffray, Frédéric; Teixeira, Rafael B. (2013), "The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem", Discrete Applied Mathematics: Available online 11 October 2013, doi:10.1016/j.dam.2013.09.004 .

Further reading

Digital object identifier Character string used as a permanent identifier for a digital object, in a format controlled by the International DOI Foundation

In computing, a digital object identifier (DOI) is a persistent identifier or handle used to identify objects uniquely, standardized by the International Organization for Standardization (ISO). An implementation of the Handle System, DOIs are in wide use mainly to identify academic, professional, and government information, such as journal articles, research reports and data sets, and official publications though they also have been used to identify other types of information resources, such as commercial videos.

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.