Intersection number (graph theory)
The intersection number is NP-hard to compute or approximate, but fixed-parameter tractable.
forms a clique: any two vertices in this subset are adjacent, because their sets have a nonempty intersection containing
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.
[16] 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.
[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.
[17] 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.
[18][19] 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
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.
Restoring the two removed vertices, cover edges to their shared neighbors by triangles, leaving edges to unshared neighbors as two-vertex cliques.
[2] An even tighter bound is possible when the number of edges is strictly greater than
be the number of pairs of vertices that are not connected by an edge in the given graph
[6] It follows from deep results on the structure of claw-free graphs that, when a connected
-vertex claw-free graph has at least three independent vertices, it has intersection number at most
It remains an unsolved problem whether this is true of all claw-free graphs without requiring them to have large independent sets.
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.
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.
[28] 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
multiplied by a larger but computable function of the intersection number
[5][30] Therefore, in polynomial time the input can be reduced to a smaller kernel with at most
cannot be reduced to single exponential by a kernelization of polynomial size, unless the polynomial hierarchy collapses,[31] and if the exponential time hypothesis is true then double-exponential dependence is necessary regardless of whether kernelization is used.
[29] On graphs of bounded treewidth, dynamic programming on a tree decomposition of the graph can find the intersection number in linear time,[32][21] but simpler algorithms based on finite sets of reduction rules do not work.
[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.
[35][36] 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
[36] It is also possible to find the intersection number in linear time in circular-arc graphs.
[38][39] On planar graphs, computing the intersection number exactly remains NP-hard, but it has a polynomial-time approximation scheme based on Baker's technique.
