Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Triangle-free graph
Summary
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 independent graphs.
By Turán's theorem, the n-vertex triangle-free graph with the maximum number of edges is a complete bipartite graph in which the numbers of vertices on each side of the bipartition are as equal as possible.
The triangle finding or triangle detection problem is the problem of determining whether a graph is triangle-free or not. When the graph does contain a triangle, algorithms are often required to output three vertices which form a triangle in the graph.
It is possible to test whether a graph with edges is triangle-free in time where the hides sub-polynomial factors and is the exponent of fast matrix multiplication. it is known that from which it follows that triangle detection can be solved in time . Another approach is to find the trace of A^3, where A is the adjacency matrix of the graph. The trace is zero if and only if the graph is triangle-free. For dense graphs, it is more efficient to use this simple algorithm which again relies on matrix multiplication, since it gets the time complexity down to , where is the number of vertices.
Even if matrix multiplication algorithms with time were discovered, the best time bounds that could be hoped for from these approaches are or . In fine-grained complexity, the sparse triangle hypothesis is an unproven computational hardness assumption asserting that no time bound of the form is possible, for any , regardness of what algorithmic techniques are used. It, and the corresponding dense triangle hypothesis that no time bound of the form is possible, imply lower bounds for several other computational problems in combinatorial optimization and computational geometry.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.