Biclique-free graph
In graph theory, a branch of mathematics, a t-biclique-free graph is a graph that has no 2t-vertex complete bipartite graph Kt,t as a subgraph. A family of graphs is biclique-free if there exists a number t such that the graphs in the family are all t-biclique-free. The biclique-free graph families form one of the most general types of sparse graph family. They arise in incidence problems in discrete geometry, and have also been used in parameterized complexity.
Properties
Sparsity
According to the Kővári–Sós–Turán theorem, every n-vertex t-biclique-free graph has O(n2 − 1/t) edges, significantly fewer than a dense graph would have.[1] Conversely, if a graph family is defined by forbidden subgraphs or closed under the operation of taking subgraphs, and does not include dense graphs of arbitrarily large size, it must be t-biclique-free for some t, for otherwise it would include large dense complete bipartite graphs.
As a lower bound, Erdős, Hajnal & Moon (1964) conjectured that every maximal t-biclique-free bipartite graph (one to which no more edges can be added without creating a t-biclique) has at least (t − 1)(n + m − t + 1) edges, where n and m are the numbers of vertices on each side of its bipartition.[2]
Relation to other types of sparse graph family
A graph with degeneracy d is necessarily (d + 1)-biclique-free. Additionally, a biclique-free family of graphs must be nowhere dense, meaning that for every number k, there exists a graph that is not a k-shallow minor of a graph in the family. In particular, if there exists an n-vertex graph that is not a 1-shallow minor, then the family must be n-biclique-free, because all n-vertex graphs are 1-shallow minors of Kn,n. In this way, the biclique-free graph families unify two of the most general classes of sparse graphs.[3]
Applications
Discrete geometry
In discrete geometry, many types of incidence graph are necessarily biclique-free. As a simple example, the graph of incidences between a finite set of points and lines in the Euclidean plane necessarily has no K2,2 subgraph.[4]
Parameterized complexity
Biclique-free graphs have been used in parameterized complexity to develop algorithms that are efficient for sparse graphs with suitably small input parameter values. In particular, finding a dominating set of size k, on t-biclique-free graphs, is fixed-parameter tractable when parameterized by k + t, even though there is strong evidence that this is not possible using k alone as a parameter. Similar results are true for many variations of the dominating set problem.[3] It is also possible to test whether one dominating set of size at most k can be converted to another one by a chain of vertex insertions and deletions, preserving the dominating property, with the same parameterization.[5]
References
- ^ Kővári, T.; T. Sós, V.; Turán, P. (1954), "On a problem of K. Zarankiewicz" (PDF), Colloquium Math., 3: 50–57, MR 0065617. This work concerns the number of edges in biclique-free bipartite graphs, but a standard application of the probabilistic method transfers the same bound to arbitrary graphs.
- ^ Erdős, P.; Hajnal, A.; Moon, J. W. (1964), "A problem in graph theory" (PDF), The American Mathematical Monthly, 71: 1107–1110, doi:10.2307/2311408, MR 0170339.
- ^ a b Telle, Jan Arne; Villanger, Yngve (2012), "FPT algorithms for domination in biclique-free graphs", in Epstein, Leah; Ferragina, Paolo (eds.), Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012, Proceedings, Lecture Notes in Computer Science, vol. 7501, Springer, pp. 802–812, doi:10.1007/978-3-642-33090-2_69.
- ^ Kaplan, Haim; Matoušek, Jiří; Sharir, Micha (2012), "Simple proofs of classical theorems in discrete geometry via the Guth–Katz polynomial partitioning technique", Discrete and Computational Geometry, 48 (3): 499–517, arXiv:1102.5391, doi:10.1007/s00454-012-9443-3, MR 2957631. See in particular Lemma 3.1 and the remarks following the lemma.
- ^ Lokshtanov, Daniel; Mouawad, Amer E.; Panolan, Fahad; Ramanujan, M. S.; Saurabh, Saket (2015), "Reconfiguration on sparse graphs", in Dehne, Frank; Sack, Jörg-Rüdiger; Stege, Ulrike (eds.), Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015, Proceedings (PDF), Lecture Notes in Computer Science, vol. 9214, Springer, pp. 506–517, arXiv:1502.04803, doi:10.1007/978-3-319-21840-3_42.