Intersection number (graph theory)
Encyclopedia
In the mathematical field of graph theory
, the intersection number of a graph is the smallest number of elements in a representation of as an intersection graph
of finite sets. Equivalently, it is the smallest number of cliques
needed to cover all of the edges of .
(allowing sets in to be repeated); then the intersection graph
of is an undirected graph that has a vertex for each member of and an edge between each two members 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 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.
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.
The equivalence between the two directions 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 of , 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, because an edge corresponds to a nonempty intersection and an intersection is nonempty if it contains at least one element of . 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 the set of cliques that contain that vertex.
It is also true that every graph with vertices has intersection number at most . More strongly, the edges of every -vertex graph can be partitioned into at most cliques, all of which are either single edges or triangles. This generalizes Mantel's theorem that a triangle-free graph
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 p 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
of a sparse graph have small intersection numbers: the intersection number of any -vertex graph is at most , where is the base of the natural logarithm
and d is the degree
of the complement graph of .
. Therefore, it is also NP-hard to compute the intersection number of a given graph.
The problem of computing the intersection number is, however, fixed-parameter tractable
: that is, there is a function such that, when the intersection number is , the time to compute it is proportional to a polynomial in the graph size and . More specifically, 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 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
with at most vertices; applying an exponential time backtracking
search procedure to this kernel leads to a function that is double exponential in . It is an open problem whether a polynomial-size kernel exists, and whether the dependence on can be reduced to single exponential.
More efficient algorithms are also 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. More generally, in chordal graph
s, the intersection number may be computed by an algorithm that considers the vertices in an elimination ordering of the graph 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.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the intersection number of a graph is the smallest number of elements in a representation of as an intersection graph
Intersection graph
In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...
of finite sets. Equivalently, it is the smallest number of cliques
Clique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
needed to cover all of the edges of .
Intersection graphs
Let be a family of setsFamily 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...
(allowing sets in to be repeated); then the intersection graph
Intersection graph
In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...
of is an undirected graph that has a vertex for each member of and an edge between each two members 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 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
An alternative definition of the intersection number of a graph is that it is the smallest number of cliquesClique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
in (complete
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
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.
The equivalence between the two directions 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 of , 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, because an edge corresponds to a nonempty intersection and an intersection is nonempty if it contains at least one element of . 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 the set of cliques that contain that vertex.
Upper bounds
Trivially, a graph with edges has intersection number at most , for each edge forms a clique and these cliques together 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 partitioned into at most cliques, all of which are either single edges or triangles. This generalizes Mantel's theorem that a triangle-free graph
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 girth ≥ 4, graphs with no induced 3-cycle, or locally...
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 p 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
Complement graph
In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two 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...
of a sparse graph have small intersection numbers: the intersection number of any -vertex graph is at most , where is the base of the natural logarithm
E (mathematical constant)
The mathematical constant ' is the unique real number such that the value of the derivative of the function at the point is equal to 1. The function so defined is called the exponential function, and its inverse is the natural logarithm, or logarithm to base...
and d is the degree
Degree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...
of the complement graph of .
Computational complexity
Testing whether a given graph has intersection number at most a given number is NP-completeNP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
. Therefore, it is also NP-hard to compute the intersection number of a given graph.
The problem of computing the intersection number is, however, fixed-parameter tractable
Parameterized complexity
Parameterized complexity is a branch of computational complexity theory in computer science that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input. The complexity of a problem is then measured as a function in those...
: that is, there is a function such that, when the intersection number is , the time to compute it is proportional to a polynomial in the graph size and . More specifically, 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 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
Kernelization
In computer science, a kernelization is an efficient algorithm that preprocesses instances of decision problems by mapping them to equivalent instances with a guaranteed upper bound on the size of the output, called the kernel of the instance. Kernelization is often achieved by applying a set of...
with at most vertices; applying an exponential time backtracking
Backtracking
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
search procedure to this kernel leads to a function that is double exponential in . It is an open problem whether a polynomial-size kernel exists, and whether the dependence on can be reduced to single exponential.
More efficient algorithms are also known for certain special classes of graphs. The intersection number of an interval graph
Interval graph
In graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...
is always equal to its number of maximal cliques, which may be computed in polynomial time. More generally, in chordal graph
Chordal graph
In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
s, the intersection number may be computed by an algorithm that considers the vertices in an elimination ordering of the graph 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.
See also
- Bipartite dimensionBipartite dimensionIn the mathematical field of graph theory, the bipartite dimension of a graph G = is the minimum number of bicliques, that is, complete bipartite subgraphs, needed to cover all edges in E. A collection of bicliques covering all edges in G is called a biclique edge cover, or sometimes...
, the smallest number of bicliques needed to cover all edges of a graph - Clique coverClique coverIn computational complexity theory, finding a minimum clique cover is a graph-theoretical NP-complete problem. The problem was one of Richard Karp's original 21 problems shown NP-complete in his 1972 paper "Reducibility Among Combinatorial Problems"....
, the NP-complete problem of finding a small number of cliques that cover all vertices of a graph