Intersection number (graph theory)

In the mathematical field of graph theory, the intersection number of a graph G = (V,E) is the smallest number of elements in a representation of G as an intersection graph of finite sets. Equivalently, it is the smallest number of cliques needed to cover all of the edges of G.[1][2]

Intersection graphs

Let F be a family of sets (allowing sets in F to be repeated); then the intersection graph of F is an undirected graph that has a vertex for each member of F and an edge between each two members that have a nonempty intersection. Every graph can be represented as an intersection graph in this way.[3] The intersection number of the graph is the smallest number k such that there exists a representation of this type for which the union of F has k elements.[1] The problem of finding an intersection representation of a graph with a given number of elements is known as the intersection graph basis problem.[4]

Clique edge covers

A graph with intersection number four. The four shaded regions indicate cliques that cover all the edges of the graph.

An alternative definition of the intersection number of a graph G is that it is the smallest number of cliques in G (complete subgraphs of G) that together cover all of the edges of G.[1][5] 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.[6]

The equality of the intersection number and the edge clique cover number is straightforward to prove. In one direction, suppose that G is the intersection graph of a family F of sets whose union U has k elements. Then for any element x of U, the subset of vertices of G corresponding to sets that contain x forms a clique: any two vertices in this subset are adjacent, because their sets have a nonempty intersection containing x. Further, every edge in G 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 U. Therefore, the edges of G can be covered by k cliques, one per element of U. In the other direction, if a graph G can be covered by k cliques, then each vertex of G may be represented by the set of cliques that contain that vertex.[5]

Upper bounds

Trivially, a graph with m edges has intersection number at most m, for each edge forms a clique and these cliques together cover all the edges.[7]

It is also true that every graph with n vertices has intersection number at most n2/4. More strongly, the edges of every n-vertex graph can be partitioned into at most n2/4 cliques, all of which are either single edges or triangles.[2][5] This generalizes Mantel's theorem that a triangle-free graph has at most n2/4 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 n2/4. Let p be the number of pairs of vertices that are not connected by an edge in the given graph G, and let t be the unique integer for which t(t − 1) ≤ p < t(t + 1). Then the intersection number of G is at most p + t.[2][8]

Graphs that are the complement of a sparse graph have small intersection numbers: the intersection number of any n-vertex graph G is at most 2e2(d + 1)2ln n, where e is the base of the natural logarithm and d is the maximum degree of the complement graph of G.[9]

Computational complexity

Testing whether a given graph G has intersection number at most a given number k is NP-complete.[4][10][11] 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 f such that, when the intersection number is k, the time to compute it is at most the product of f(k) and a polynomial in n. This may be shown by observing that there are at most 2k 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 with at most 2k vertices; applying an exponential time backtracking search procedure to this kernel leads to a function f that is double exponential in k.[12] The double-exponential dependence on k cannot be reduced to single exponential by a kernelization of polynomial size, unless the polynomial hierarchy collapses,[13] and if the exponential time hypothesis is true then double-exponential dependence is necessary regardless of whether kernelization is used.[14]

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.[15][16] 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 and that, for each vertex v, forms a clique for v and its later neighbors whenever at least one of the edges incident to v is not covered by any earlier clique.[16]

See also

References

  1. 1 2 3 Gross, Jonathan L.; Yellen, Jay (2006), Graph Theory and its Applications, CRC Press, p. 440, ISBN 978-1-58488-505-4.
  2. 1 2 3 4 Roberts, Fred S. (1985), "Applications of edge coverings by cliques", Discrete Applied Mathematics 10 (1): 93–109, doi:10.1016/0166-218X(85)90061-7, MR 770871.
  3. ↑ Szpilrajn-Marczewski, E. (1945), "Sur deux propriétés des classes d'ensembles", Fund. Math. 33: 303–307, MR 0015448.
  4. 1 2 Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5, Problem GT59.
  5. 1 2 3 Erdős, Paul; Goodman, A. W.; Pósa, Louis (1966), "The representation of a graph by set intersections" (PDF), Canadian Journal of Mathematics 18 (1): 106–112, doi:10.4153/CJM-1966-014-3, MR 0186575.
  6. ↑ Michael, T. S.; Quint, Thomas (2006), "Sphericity, cubicity, and edge clique covers of graphs", Discrete Applied Mathematics 154 (8): 1309–1313, doi:10.1016/j.dam.2006.01.004.
  7. ↑ Balakrishnan, V. K. (1997), Schaum's outline of theory and problems of graph theory, McGraw-Hill Professional, p. 40, ISBN 978-0-07-005489-9.
  8. ↑ Lovász, L. (1968), "On covering of graphs", in Erdős, P.; Katona, G., Proceedings of the Colloquium held at Tihany, Hungary, 1966, Academic Press, pp. 231–236. As cited by Roberts (1985).
  9. ↑ Alon, Noga (1986), "Covering graphs by the minimum number of equivalence relations" (PDF), Combinatorica 6 (3): 201–206, doi:10.1007/bf02579381.
  10. ↑ Orlin, J. (1977), "Contentment in graph theory: covering graphs with cliques", Proc. Kon. Ned. Acad. Wet., Series A 80: 406–424, doi:10.1016/1385-7258(77)90055-5. As cited by Roberts (1985).
  11. ↑ Kou, L. T.; Stockmeyer, L. J.; Wong, C. K. (1978), "Covering edges by cliques with regard to keyword conflicts and intersection graphs", Communications of the ACM 21 (2): 135–139, doi:10.1145/359340.359346.
  12. ↑ Gramm, Jens; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf (2009), "Data reduction and exact algorithms for clique cover" (PDF), Journal of Experimental Algorithmics 13 (2): 2–15, doi:10.1145/1412228.1412236.
  13. ↑ Cygan, Marek; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus (2012), "Clique cover and graph separation: New incompressibility results", in Czumaj, Artur; Mehlhorn, Kurt; Pitt, Andrew; et al., Automata, Languages, and Programming: 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, Lecture Notes in Computer Science 7391, pp. 254–265, arXiv:1111.0570, doi:10.1007/978-3-642-31594-7_22, ISBN 978-3-642-31593-0.
  14. ↑ Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał (2013), "Known algorithms for EDGE CLIQUE COVER are probably optimal", Proc. 24th ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), arXiv:1203.1754.
  15. ↑ Opsut, R. J.; Roberts, F. S. (1981), "On the fleet maintenance, mobile radio frequency, task assignment, and traffic phasing problems", in Chartrand, G.; Alavi, Y.; Goldsmith, D. L.; Lesniak-Foster, L.; Lick, D. R., The Theory and Applications of Graphs, New York: Wiley, pp. 479–492. As cited by Roberts (1985).
  16. 1 2 Scheinerman, Edward R.; Trenk, Ann N. (1999), "On the fractional intersection number of a graph" (PDF), Graphs and Combinatorics 15 (3): 341–351, doi:10.1007/s003730050068.

External links

This article is issued from Wikipedia - version of the Sunday, January 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.