In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory
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'' (also called ''nodes'' or ''points'') which are conn ...
, the intersection number of a graph
is the smallest number of elements in a representation of
as an
intersection graph
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...
of
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. T ...
s. In such a representation, each vertex is represented as a set, and two vertices are connected by an edge whenever their sets have a common element. Equivalently, the intersection number is the smallest number of
cliques
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
needed to
cover all of the edges of
.
A set of cliques that cover all edges of a graph is called a clique edge cover or edge clique cover, or even just a clique cover, although the last term is ambiguous: a
clique cover
In graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that us ...
can also be a set of cliques that cover all vertices of a graph. Sometimes "covering" is used in place of "cover". As well as being called the intersection number, the minimum number of these cliques has been called the ''R''-content, edge clique cover number, or clique cover number. The problem of computing the intersection number has been called the intersection number problem, the intersection graph basis problem, covering by cliques, the edge clique cover problem, and the keyword conflict problem.
Every graph with
vertices and
edges has intersection number at most
. The intersection number is
NP-hard to compute or approximate, but
fixed-parameter tractable
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...
.
Definitions
Intersection graphs
Let
be any
family of sets
In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets, set fami ...
, allowing sets in
to be repeated. Then the
intersection graph
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...
of
is an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
that has a vertex for each set in
and an edge between each two sets that have a nonempty intersection. Every graph can be represented as an intersection graph in this way. The intersection number of the graph is the smallest number
such that there exists a representation of this type for which the union of the sets in
has
elements. The problem of finding an intersection representation of a graph with a given number of elements is known as the intersection graph basis problem.
Clique edge covers
![Erdős–Faber–Lovász conjecture](https://upload.wikimedia.org/wikipedia/commons/f/fa/Erd%C5%91s%E2%80%93Faber%E2%80%93Lov%C3%A1sz_conjecture.svg)
An alternative definition of the intersection number of a graph
is that it is the smallest number of
cliques
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
in
(
complete subgraphs of
) that together cover all of the edges of
. A set of cliques with this property is known as a clique edge cover or edge clique cover, and for this reason the intersection number is also sometimes called the edge clique cover number.
Equivalence
The equality of the intersection number and the edge clique cover number is straightforward to prove. In one direction, suppose that
is the intersection graph of a family
of sets whose union
has
elements. Then for any element
, the subset of vertices of
corresponding to sets that contain
forms a clique: any two vertices in this subset are adjacent, because their sets have a nonempty intersection containing
. Further, every edge in
is contained in one of these cliques: if an edge comes from a non-empty intersection of sets containing an element
, then that edge is contained in the clique for
. Therefore, the edges of
can be covered by
cliques, one per element of
.
In the other direction, if a graph
can be covered by
cliques, then each vertex
of
may be represented by a subset of the cliques, the ones that contain vertex
. Two of these subsets, for two vertices
and
, have a nonempty intersection if and only if there is a clique in the intersection that contains both of them, if and only if there is an edge
included in one of the covering cliques.
Applications
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
, it can be represented as an intersection graph of
-dimensional unit
hypercubes (implying that its
boxicity
In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969.
The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection graph of axis-parallel boxes. That is, there mu ...
is at most
), or as an intersection graph of
-dimensional unit
hypersphere
In mathematics, an -sphere or a hypersphere is a topological space that is homeomorphic to a ''standard'' -''sphere'', which is the set of points in -dimensional Euclidean space that are situated at a constant distance from a fixed point, call ...
s (its sphericity is at most
).
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
In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic oper ...
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. Similarly, in
computational geometry, representations based on the intersection number have been considered as a compact representation for
visibility graph In computational geometry and robot motion planning, a visibility graph is a graph of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. Each node in the graph represents a point location, and each edge rep ...
s, but there exist geometric inputs for which this representation requires a near-quadratic number of cliques.
Another class of applications comes from
scheduling
A schedule or a timetable, as a basic time-management tool, consists of a list of times at which possible tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order in which such things are ...
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. In the design of
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs tha ...
s for
very long instruction word
Very long instruction word (VLIW) refers to instruction set architectures designed to exploit instruction level parallelism (ILP). Whereas conventional central processing units (CPU, processor) mostly allow programs to specify instructions to exe ...
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.
Shephard and Vetta observe that the intersection number of any network equals the minimum number of constraints needed in an
integer programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective ...
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
An optical fiber, or optical fibre in Commonwealth English, is a flexible, transparent fiber made by drawing glass (silica) or plastic to a diameter slightly thicker than that of a human hair. Optical fibers are used most often as a means t ...
communications networks, these intersection numbers are small, explaining the relative ease of solving certain optimization problems in allocating bandwidth on the networks.
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.
In the analysis of
food web
A food web is the natural interconnection of food chains and a graphical representation of what-eats-what in an ecological community. Another name for food web is consumer-resource system. Ecologists can broadly lump all life forms into one o ...
s 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
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one v ...
representing predator-prey relations by drawing an edge
in the competition graph whenever there exists a prey species
such that the predator-prey relation graph has edges
and
. Every competition graph must have at least one
isolated vertex
In discrete mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of ver ...
, 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
vertices, at most
of them can be the prey of more than one other species, so the competition number is at least the intersection number
Edge clique covers have also been used to infer the existence of
protein complex
A protein complex or multiprotein complex is a group of two or more associated polypeptide chains. Protein complexes are distinct from multienzyme complexes, in which multiple catalytic domains are found in a single polypeptide chain.
Protein ...
es, systems of mutually interacting proteins, from
protein–protein interaction
Protein–protein interactions (PPIs) are physical contacts of high specificity established between two or more protein molecules as a result of biochemical events steered by interactions that include electrostatic forces, hydrogen bonding and th ...
networks describing only the pairwise interactions between proteins. More generally, Guillaume and Latapy have argued that, for
complex network
In the context of network theory, a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in networks representing real ...
s 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.
Upper bounds
Trivially, a graph with
edges has intersection number at most
. Each edge is itself a two-vertex clique. There are
of these cliques and together they cover all the edges. It is also true that every graph with
vertices has intersection number at most
. More strongly, the edges of every
-vertex graph can be covered by at most
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
cliques, and the two removed vertices contribute at most
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
cliques total. This generalizes
Mantel's theorem that a
triangle-free graph
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 g ...
has at most
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.
An even tighter bound is possible when the number of edges is strictly greater than
. Let
be the number of pairs of vertices that are not connected by an edge in the given graph
, and let
be the unique integer for which
. Then the intersection number of
is at most
. Graphs that are the
complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-clas ...
of a
sparse graph
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected by one edge). The opposite, a graph with only a few edges, is a sparse graph. The distinction ...
have small intersection numbers: the intersection number of any
-vertex graph
is at most
, where
is the
base of the natural logarithm and
is the maximum
degree of the complement graph of
.
It follows from deep results on the structure of
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.
A claw is another name for the complete bipartite graph ''K''1,3 (that is, a star graph comprising three edges, three leaves, ...
s 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. An important subclass of the claw-free graphs are the
line graph
In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...
s, graphs representing edges and touching pairs of edges of some other graph
. An optimal clique cover of the line graph
may be formed with one clique for each triangle in
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.
In the
Erdős–Rényi–Gilbert model of
random graph
In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs ...
s, in which all graphs on
labeled vertices are equally likely (or equivalently, each edge is present or absent, independently of other edges, with probability
) the intersection number of an
-vertex random graph is with high probability
smaller by a factor of
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.
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.
Computational complexity
Testing whether a given graph
has intersection number at most a given number
is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
. 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
In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90- degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length a ...
of
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 , and independently introduced by .
A split graph may have m ...
s.
The problem of computing the intersection number is, however,
fixed-parameter tractable
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...
: 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
. This may be shown by observing that there are at most
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. Therefore, in polynomial time the input can be reduced to a smaller
kernel
Kernel may refer to:
Computing
* Kernel (operating system), the central component of most operating systems
* Kernel (image processing), a matrix used for image convolution
* Compute kernel, in GPGPU programming
* Kernel method, in machine learn ...
with at most
vertices and
edges. Applying an
exponential time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...
search procedure over subsets of edges of this kernel gives time
,
double exponential in
. The double-exponential dependence on
cannot be reduced to single exponential by a kernelization of polynomial size, unless the
polynomial hierarchy
In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. ...
collapses, and if the
exponential time hypothesis
In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved more quickly than exponential t ...
is true then double-exponential dependence is necessary regardless of whether kernelization is used. On graphs of bounded
treewidth
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...
, dynamic programming on a
tree decomposition
In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.
Tree decompositions are also called junction trees ...
of the graph can find the intersection number in linear time, but simpler algorithms based on finite sets of reduction rules do not work.
The problem cannot be approximated in polynomial time with an
approximation ratio
An approximation is anything that is intentionally similar but not exactly equal to something else.
Etymology and usage
The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...
better than
, for some constant
, and the best approximation ratio is known is better than the trivial
by only a polylogarithmic factor. 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.
More efficient algorithms are known for certain special classes of graphs. The intersection number of an
interval graph
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 ...
is always equal to its number of
maximal clique
In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is compl ...
s, which may be computed in polynomial time. More generally, in
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 c ...
s, 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
, forms a clique for
and its later neighbors whenever at least one of the edges incident to
is not covered by any earlier clique. It is also possible to find the intersection number in
linear time in
circular-arc graphs. 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. 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. On
planar graphs, computing the intersection number exactly remains NP-hard, but it has a
polynomial-time approximation scheme
In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems).
A PTAS is an algorithm which takes an insta ...
based on
Baker's technique.
See also
*
Bipartite dimension
In the mathematical fields of graph theory and combinatorial optimization, the bipartite dimension or biclique cover number of a graph ''G'' = (''V'', ''E'') is the minimum number of bicliques (that is complete bipartite subgraphs), ...
, the smallest number of bicliques needed to cover all edges of a graph
*
Clique cover
In graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that us ...
, the NP-hard problem of finding a small number of cliques that cover all vertices of a graph
References
External links
*{{mathworld, title=Intersection Number, urlname=IntersectionNumber, mode=cs2
Graph invariants
Intersection classes of graphs