Indifference graph

Last updated
An indifference graph, formed from a set of points on the real line by connecting pairs of points whose distance is at most one Indifference graph.svg
An indifference graph, formed from a set of points on the real line by connecting pairs of points whose distance is at most one

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. [1] Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals (intervals none of which contains any other one). 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.

Contents

Equivalent characterizations

Forbidden induced subgraphs for the indifference graphs: the claw, sun, and net (top, left-right) and cycles of length four or more (bottom) Forbidden indifference subgraphs.svg
Forbidden induced subgraphs for the indifference graphs: the claw, sun, and net (top, left–right) and cycles of length four or more (bottom)

The finite indifference graphs may be equivalently characterized as

For infinite graphs, some of these definitions may differ.

Properties

Because they are special cases of interval graphs, indifference graphs have all the properties of interval graphs; in particular they are a special case of the chordal graphs and of the perfect graphs. They are also a special case of the circle graphs, something that is not true of interval graphs more generally.

In the Erdős–Rényi model of random graphs, an -vertex graph whose number of edges is significantly less than will be an indifference graph with high probability, whereas a graph whose number of edges is significantly more than will not be an indifference graph with high probability. [9]

The bandwidth of an arbitrary graph is one less than the size of the maximum clique in an indifference graph that contains as a subgraph and is chosen to minimize the size of the maximum clique. [10] This property parallels similar relations between pathwidth and interval graphs, and between treewidth and chordal graphs. A weaker notion of width, the clique-width, may be arbitrarily large on indifference graphs. [11] However, every proper subclass of the indifference graphs that is closed under induced subgraphs has bounded clique-width. [12]

Every connected indifference graph has a Hamiltonian path. [13] An indifference graph has a Hamiltonian cycle if and only if it is biconnected. [14]

Indifference graphs obey the reconstruction conjecture: they are uniquely determined by their vertex-deleted subgraphs. [15]

Algorithms

As with higher dimensional unit disk graphs, it is possible to transform a set of points into their indifference graph, or a set of unit intervals into their unit interval graph, in linear time as measured in terms of the size of the output graph. The algorithm rounds the points (or interval centers) down to the nearest smaller integer, uses a hash table to find all pairs of points whose rounded integers are within one of each other (the fixed-radius near neighbors problem), and filters the resulting list of pairs for the ones whose unrounded values are also within one of each other. [16]

It is possible to test whether a given graph is an indifference graph in linear time, by using PQ trees to construct an interval representation of the graph and then testing whether a vertex ordering derived from this representation satisfies the properties of an indifference graph. [4] It is also possible to base a recognition algorithm for indifference graphs on chordal graph recognition algorithms. [14] Several alternative linear time recognition algorithms are based on breadth-first search or lexicographic breadth-first search rather than on the relation between indifference graphs and interval graphs. [17] [18] [19] [20]

Once the vertices have been sorted by the numerical values that describe an indifference graph (or by the sequence of unit intervals in an interval representation) the same ordering can be used to find an optimal graph coloring for these graphs, to solve the shortest path problem, and to construct Hamiltonian paths and maximum matchings, all in linear time. [4] A Hamiltonian cycle can be found from a proper interval representation of the graph in time , [13] but when the graph itself is given as input, the same problem admits linear-time solution that can be generalized to interval graphs. [21] [22]

List coloring remains NP-complete even when restricted to indifference graphs. [23] However, it is fixed-parameter tractable when parameterized by the total number of colors in the input. [12]

Applications

In mathematical psychology, indifference graphs arise from utility functions, by scaling the function so that one unit represents a difference in utilities small enough that individuals can be assumed to be indifferent to it. In this application, pairs of items whose utilities have a large difference may be partially ordered by the relative order of their utilities, giving a semiorder. [1] [24]

In bioinformatics, the problem of augmenting a colored graph to a properly colored unit interval graph can be used to model the detection of false negatives in DNA sequence assembly from complete digests. [25]

See also

Related Research Articles

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.

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G).

Edge coloring an assignment of colors to the edges of a graph so that no two edges that share an endpoint have the same color as each other

In graph theory, an 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.

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.

Complement graph

In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there. It is not, however, the set complement of the graph; only the edges are complemented.

Cograph

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, the treewidth of an undirected graph is a number associated with the graph. Treewidth may be defined in several equivalent ways: the size of the largest vertex set in a tree decomposition of the graph, the size of the largest clique in a chordal completion of the graph, the maximum order of a haven describing a strategy for a pursuit-evasion game on the graph, or the maximum order of a bramble, a collection of connected subgraphs that all touch each other.

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.

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).

Claw-free graph

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

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 and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

Hamiltonian decomposition

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 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.

In graph theory, the tree-depth of a connected undirected graph G is a numerical invariant of G, the minimum height of a Trémaux tree for a supergraph of G. This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages. Intuitively, where the treewidth graph width parameter measures how far a graph is from being a tree, this parameter measures how far a graph is from being a star.

Caterpillar tree

In graph theory, a caterpillar or caterpillar tree is a tree in which all the vertices are within distance 1 of a central path.

Graph power

In graph theory, a branch of mathematics, the kth powerGk of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: G2 is called the square of G, G3 is called the cube of G, etc.

Leaf power

In the mathematical area of graph theory, a k-leaf power of a tree is a graph whose vertices are the leaves of and whose edges connect pairs of leaves whose distance in is at most . That is, is an induced subgraph of the graph power , induced by the leaves of . For a graph constructed in this way, is called a k-leaf root of .

References

  1. 1 2 3 4 5 6 Roberts, Fred S. (1969), "Indifference graphs", Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press, New York, pp. 139–146, MR   0252267 .
  2. 1 2 Bogart, Kenneth P.; West, Douglas B. (1999), "A short proof that "proper = unit"", Discrete Mathematics , 201 (1–3): 21–23, arXiv: math/9811036 , doi:10.1016/S0012-365X(98)00310-0, MR   1687858 .
  3. Wegner, G. (1967), Eigenschaften der Nerven homologisch-einfacher Familien im Rn, Ph.D. thesis, Göttingen, Germany: Göttingen University. As cited by Hell & Huang (2004).
  4. 1 2 3 Looges, Peter J.; Olariu, Stephan (1993), "Optimal greedy algorithms for indifference graphs", Computers & Mathematics with Applications, 25 (7): 15–25, doi: 10.1016/0898-1221(93)90308-I , MR   1203643 .
  5. Jackowski, Zygmunt (1992), "A new characterization of proper interval graphs", Discrete Mathematics , 105 (1–3): 103–109, doi: 10.1016/0012-365X(92)90135-3 , MR   1180196 .
  6. 1 2 Gutierrez, M.; Oubiña, L. (1996), "Metric characterizations of proper interval graphs and tree-clique graphs", Journal of Graph Theory, 21 (2): 199–205, doi:10.1002/(SICI)1097-0118(199602)21:2<199::AID-JGT9>3.0.CO;2-M, MR   1368745 .
  7. Mertzios, George B. (2008), "A matrix characterization of interval and proper interval graphs", Applied Mathematics Letters, 21 (4): 332–337, doi: 10.1016/j.aml.2007.04.001 , MR   2406509 .
  8. 1 2 Brandstädt, Andreas; Hundt, Christian; Mancini, Federico; Wagner, Peter (2010), "Rooted directed path graphs are leaf powers", Discrete Mathematics, 310: 897–910, doi: 10.1016/j.disc.2009.10.006 .
  9. Cohen, Joel E. (1982), "The asymptotic probability that a random graph is a unit interval graph, indifference graph, or proper interval graph", Discrete Mathematics , 40 (1): 21–24, doi: 10.1016/0012-365X(82)90184-4 , MR   0676708 .
  10. Kaplan, Haim; Shamir, Ron (1996), "Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques", SIAM Journal on Computing, 25 (3): 540–561, doi:10.1137/S0097539793258143, MR   1390027 .
  11. Golumbic, Martin Charles; Rotics, Udi (1999), "The clique-width of unit interval graphs is unbounded", Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999), Congressus Numerantium, 140, pp. 5–17, MR   1745205 .
  12. 1 2 Lozin, Vadim V. (2008), "From tree-width to clique-width: excluding a unit interval graph", Algorithms and computation, Lecture Notes in Comput. Sci., 5369, Springer, Berlin, pp. 871–882, doi:10.1007/978-3-540-92182-0_76, MR   2539978 .
  13. 1 2 Bertossi, Alan A. (1983), "Finding Hamiltonian circuits in proper interval graphs", Information Processing Letters, 17 (2): 97–101, doi:10.1016/0020-0190(83)90078-9, MR   0731128 .
  14. 1 2 Panda, B. S.; Das, Sajal K. (2003), "A linear time recognition algorithm for proper interval graphs", Information Processing Letters, 87 (3): 153–161, doi:10.1016/S0020-0190(03)00298-9, MR   1986780 .
  15. von Rimscha, Michael (1983), "Reconstructibility and perfect graphs", Discrete Mathematics, 47 (2–3): 283–291, doi: 10.1016/0012-365X(83)90099-7 , MR   0724667 .
  16. Bentley, Jon L.; Stanat, Donald F.; Williams, E. Hollins, Jr. (1977), "The complexity of finding fixed-radius near neighbors", Information Processing Letters , 6 (6): 209–212, doi:10.1016/0020-0190(77)90070-9, MR   0489084 .
  17. Corneil, Derek G.; Kim, Hiryoung; Natarajan, Sridhar; Olariu, Stephan; Sprague, Alan P. (1995), "Simple linear time recognition of unit interval graphs", Information Processing Letters, 55 (2): 99–104, CiteSeerX   10.1.1.39.855 , doi:10.1016/0020-0190(95)00046-F, MR   1344787 .
  18. Herrera de Figueiredo, Celina M.; Meidanis, João; Picinin de Mello, Célia (1995), "A linear-time algorithm for proper interval graph recognition", Information Processing Letters, 56 (3): 179–184, doi:10.1016/0020-0190(95)00133-W, MR   1365411 .
  19. Corneil, Derek G. (2004), "A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs", Discrete Applied Mathematics, 138 (3): 371–379, doi: 10.1016/j.dam.2003.07.001 , MR   2049655 .
  20. Hell, Pavol; Huang, Jing (2004), "Certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs", SIAM Journal on Discrete Mathematics , 18 (3): 554–570, doi:10.1137/S0895480103430259, MR   2134416 .
  21. Keil, J. Mark (1985), "Finding Hamiltonian circuits in interval graphs", Information Processing Letters, 20 (4): 201–206, doi:10.1016/0020-0190(85)90050-X, MR   0801816 .
  22. Ibarra, Louis (2009), "A simple algorithm to find Hamiltonian cycles in proper interval graphs", Information Processing Letters, 109 (18): 1105–1108, doi:10.1016/j.ipl.2009.07.010, MR   2552898 .
  23. Marx, Dániel (2006), "Precoloring extension on unit interval graphs", Discrete Applied Mathematics, 154 (6): 995–1002, doi: 10.1016/j.dam.2005.10.008 , MR   2212549 .
  24. Roberts, Fred S. (1970), "On nontransitive indifference", Journal of Mathematical Psychology, 7: 243–258, doi:10.1016/0022-2496(70)90047-7, MR   0258486 .
  25. Goldberg, Paul W.; Golumbic, Martin C.; Kaplan, Haim; Shamir, Ron (2009), "Four strikes against physical mapping of DNA", Journal of Computational Biology, 2 (2), doi:10.1089/cmb.1995.2.139, PMID   7497116 .