Intersection number (graph theory)

The representation of a graph as an abstract intersection graph of sets can be used to construct more concrete geometric intersection representations of the same graph. In particular, if a graph has intersection number ${\displaystyle k}$, it can be represented as an intersection graph of ${\displaystyle k}$-dimensional unit hypercubes (implying that its boxicity is at most ${\displaystyle k}$), or as an intersection graph of ${\displaystyle k}$-dimensional unit hyperspheres (its sphericity is at most ${\displaystyle k}$).[4]

A clique cover can be used as a kind of adjacency labelling scheme for a graph, in which one labels each vertex by a binary value with a bit for each clique, zero if it does not belong to the clique and one if it belongs. Then two vertices are adjacent if and only if the bitwise and of their labels is nonzero. The length of the labels is the intersection number of the graph. This method was used in an early application of intersection numbers, for labeling a set of keywords so that conflicting keywords could be quickly detected, by E. Kellerman of IBM. For this reason, another name for the problem of computing intersection numbers is the keyword conflict problem.[13][14] Similarly, in computational geometry, representations based on the intersection number have been considered as a compact representation for visibility graphs, but there exist geometric inputs for which this representation requires a near-quadratic number of cliques.[15]

Another class of applications comes from scheduling problems in which multiple users of a shared resource should be scheduled for time slots, in such a way that incompatible requests are never scheduled for the same time slot but all pairs of compatible requests are given at least one time slot together. The intersection number of a graph of compatibilities gives the minimum number of time slots needed for such a schedule.[2] In the design of compilers for very long instruction word computers, a small clique cover of a graph of incompatible operations can be used to represent their incompatibilities by a small number of artificial resources, allowing resource-based scheduling techniques to be used to assign operations to instruction slots.[16]

Shephard and Vetta observe that the intersection number of any network equals the minimum number of constraints needed in an integer programming formulation of the problem of computing maximum independent sets, in which one has a 0-1 variable per vertex and a constraint that in each clique of a clique cover the variables sum to at most one. They argue that, for the intersection graphs of paths in certain fiber optic communications networks, these intersection numbers are small, explaining the relative ease of solving certain optimization problems in allocating bandwidth on the networks.[3]

In statistics and data visualization, edge clique covers of a graph representing statistically indistinguishable pairs of variables are used to produce compact letter displays that assist in visualizing multiple pairwise comparisons, by assigning a letter or other visual marker for each clique and using these to provide a graphical representation of which variables are indistinguishable.[17][18]

In the analysis of food webs describing predator-prey relationships among animal species, a competition graph or niche overlap graph is an undirected graph in which the vertices represent species, and edges represent pairs of species that both compete for the same prey. These can be derived from a directed acyclic graph representing predator-prey relations by drawing an edge ${\displaystyle u-v}$ in the competition graph whenever there exists a prey species ${\displaystyle w}$ such that the predator-prey relation graph has edges ${\displaystyle u\to w}$ and ${\displaystyle v\to w}$. Every competition graph must have at least one isolated vertex, and the competition number of an arbitrary graph represents the smallest number of isolated vertices that could be added to make it into a competition graph. Biologically, if part of a competition graph is observed, then the competition number represents the smallest possible number of unobserved prey species needed to explain it. The competition number is at most equal to the intersection number: one can transform any undirected graph into a competition graph by adding a prey species for each clique in an edge clique cover. However, this relation is not exact, because it is also possible for the predator species to be prey of other species. In a graph with ${\displaystyle n}$ vertices, at most ${\displaystyle n-2}$ of them can be the prey of more than one other species, so the competition number is at least the intersection number minus ${\displaystyle n-2}$.[19]

Edge clique covers have also been used to infer the existence of protein complexes, systems of mutually interacting proteins, from protein–protein interaction networks describing only the pairwise interactions between proteins.[20] More generally, Guillaume and Latapy have argued that, for complex networks of all types, replacing the network by a bipartite graph connecting its vertices to the cliques in a clique cover highlights the structure in the network.[21]

Trivially, a graph with ${\displaystyle m}$ edges has intersection number at most ${\displaystyle m}$. Each edge is itself a two-vertex clique. There are ${\displaystyle m}$ of these cliques and together they cover all the edges.[22] It is also true that every graph with ${\displaystyle n}$ vertices has intersection number at most ${\displaystyle \lfloor n^{2}/4\rfloor }$. More strongly, the edges of every ${\displaystyle n}$-vertex graph can be covered by at most ${\displaystyle \lfloor n^{2}/4\rfloor }$ cliques, all of which are either single edges or triangles. An algorithm for finding this cover is simple: remove any two adjacent vertices and inductively cover the remaining graph. Restoring the two removed vertices, cover edges to their shared neighbors by triangles, leaving edges to unshared neighbors as two-vertex cliques. The inductive cover has at most ${\displaystyle \lfloor (n-2)^{2}/4\rfloor }$ cliques, and the two removed vertices contribute at most ${\displaystyle n-1}$ cliques, maximized when all other vertices are unshared neighbors and the edge between the two vertices must be used as a clique. Adding these two quantities gives ${\displaystyle \lfloor n^{2}/4\rfloor }$ cliques total.[2][12] This generalizes Mantel's theorem that a triangle-free graph has at most ${\displaystyle \lfloor n^{2}/4\rfloor }$ edges, for in a triangle-free graph the only optimal clique edge cover has one clique per edge and therefore the intersection number equals the number of edges.[2]

An even tighter bound is possible when the number of edges is strictly greater than ${\displaystyle {\tfrac {n^{2}}{4}}}$. Let ${\displaystyle p}$ be the number of pairs of vertices that are not connected by an edge in the given graph ${\displaystyle G}$, and let ${\displaystyle t}$ be the unique integer for which ${\displaystyle (t-1)t\leq p<t(t+1)}$. Then the intersection number of ${\displaystyle G}$ is at most ${\displaystyle p+t}$.[2][23] Graphs that are the complement of a sparse graph have small intersection numbers: the intersection number of any ${\displaystyle n}$-vertex graph ${\displaystyle G}$ is at most ${\displaystyle 2e^{2}(d+1)^{2}\ln n}$, where ${\displaystyle e}$ is the base of the natural logarithm and ${\displaystyle d}$ is the maximum degree of the complement graph of ${\displaystyle G}$.[6]

It follows from deep results on the structure of claw-free graphs that, when a connected ${\displaystyle n}$-vertex claw-free graph has at least three independent vertices, it has intersection number at most ${\displaystyle n}$. It remains an unsolved problem whether this is true of all claw-free graphs without requiring them to have large independent sets.[8] An important subclass of the claw-free graphs are the line graphs, graphs representing edges and touching pairs of edges of some other graph ${\displaystyle G}$. An optimal clique cover of the line graph ${\displaystyle L(G)}$ may be formed with one clique for each triangle in ${\displaystyle G}$ that has two or three degree-2 vertices, and one clique for each vertex that has degree at least two and is not a degree-two vertex of one of these triangles. The intersection number is the number of cliques of these two types.[7]

In the Erdős–Rényi–Gilbert model of random graphs, in which all graphs on ${\displaystyle n}$ labeled vertices are equally likely (or equivalently, each edge is present or absent, independently of other edges, with probability ${\displaystyle {\tfrac {1}{2}}}$) the intersection number of an ${\displaystyle n}$-vertex random graph is with high probability

$${\displaystyle \Theta \left({\frac {n^{2}}{\log ^{2}n}}\right),}$$

smaller by a factor of ${\displaystyle \log ^{2}n}$ than the number of edges. In these graphs, the maximum cliques have (with high probability) only a logarithmic number of vertices, implying that this many of them are needed to cover all edges. The tricker part of the bound is proving that it is possible to find enough logarithmically-sized cliques to cover many edges, allowing the remaining leftover edges to be covered by two-vertex cliques.[24][25]

Much of the early research on intersection numbers involved calculating these numbers on various specific graphs, such as the graphs formed by removing a complete subgraph or a perfect matching from a larger complete graph.[26]

Testing whether a given graph ${\displaystyle G}$ has intersection number at most a given number ${\displaystyle k}$ is NP-complete.[10][7][14] Therefore, it is also NP-hard to compute the intersection number of a given graph. In turn, the hardness of the intersection number has been used to prove that it is NP-complete to recognize the squares of split graphs.[27]

The problem of computing the intersection number is, however, fixed-parameter tractable: that is, it can be solved in an amount of time bounded by a polynomial in ${\displaystyle n}$ multiplied by a larger but computable function of the intersection number ${\displaystyle k}$.[5][28] This may be shown by observing that there are at most ${\displaystyle 2^{k}}$ distinct closed neighborhoods in the graph – two vertices that belong to the same set of cliques have the same neighborhood – and that the graph formed by selecting one vertex per closed neighbood has the same intersection number as the original graph.[5][29] Therefore, in polynomial time the input can be reduced to a smaller kernel with at most ${\textstyle 2^{k}}$ vertices and ${\displaystyle O(4^{k})}$ edges. Applying an exponential time dynamic programming search procedure over subsets of edges of this kernel gives time ${\displaystyle 2^{O(4^{k})}+n^{O(1)}}$, double exponential in ${\displaystyle k}$.[5][28] The double-exponential dependence on ${\displaystyle k}$ cannot be reduced to single exponential by a kernelization of polynomial size, unless the polynomial hierarchy collapses,[30] and if the exponential time hypothesis is true then double-exponential dependence is necessary regardless of whether kernelization is used.[28] On graphs of bounded treewidth, dynamic programming on a tree decomposition of the graph can find the intersection number in linear time,[31][20] but simpler algorithms based on finite sets of reduction rules do not work.[31]

The problem cannot be approximated in polynomial time with an approximation ratio better than ${\displaystyle n^{c}}$, for some constant ${\displaystyle c}$,[32] and the best approximation ratio is known is better than the trivial ${\displaystyle O(n^{2})}$ by only a polylogarithmic factor.[5] Researchers in this area have also investigated the computational efficiency of heuristics, without guarantees on the solution quality they produce, and their behavior on real-world networks.[5][33]

More efficient algorithms are known for certain special classes of graphs. The intersection number of an interval graph is always equal to its number of maximal cliques, which may be computed in polynomial time.[34][35] More generally, in chordal graphs, the intersection number may be computed by an algorithm that considers the vertices in an elimination ordering of the graph (an ordering in which each vertex and its later neighbors form a clique) and that, for each vertex ${\displaystyle v}$, forms a clique for ${\displaystyle v}$ and its later neighbors whenever at least one of the edges incident to ${\displaystyle v}$ is not covered by any earlier clique.[35] It is also possible to find the intersection number in linear time in circular-arc graphs.[36] However, although these graphs have only a polynomial number of cliques to choose among for the cover, having few cliques alone is not enough to make the problem easy: there exist families of graphs with polynomially many cliques for which the intersection number remains NP-hard.[9] The intersection number can also be found in polynomial time for graphs whose maximum degree is five, but is NP-hard for graphs of maximum degree six.[37][38] On planar graphs, computing the intersection number exactly remains NP-hard, but it has a polynomial-time approximation scheme based on Baker's technique.[20]

• Bipartite dimension, the smallest number of bicliques needed to cover all edges of a graph
• Clique cover, the NP-hard problem of finding a small number of cliques that cover all vertices of a graph

• Weisstein, Eric W., "Intersection Number", MathWorld