Structural Property Testing in Large Graphs

The main focus of my research is finding structural properties of large graphs and networks, with approaches using combinatorial analysis and algorithmic theory. The general setting is for a given large graph or a network G, to study whether G satisfies some structural properties, for example, whether G is planar, is an expander, or contains a copy of another smaller subgraph H. This question can be naturally generalized to various quantitative questions, for example, how far (according to some prescribed measure, such as number or proportion of edges) is G from any planar graph, or how many copies of H does G contain. Various questions of this nature appear in many areas, including algorithms, graph theory, property testing, combinatorics, in statistical analysis (including learning) of networks, complexity sciences, and so on.

Specific areas of research in this area include study in graph property testing in several contexts, including standard offline algorithms, but also distributed algorithms (such as the LOCAL, CONGEST, and CONGESTED CLIQUE models) and parallel algorithms (for example, the new and popular model of Massive Parallel Computations). The underlying problem is to check properties of the input graph G, such as whether or not a graph contains a copy of a small subgraph (for example, a complete graph of a certain size), checking for being E-far from satisfying a certain property, and counting or listing all copies of a particular graph which appear within it as subgraphs. These questions can also be considered in particular classes of graphs, such as planar graphs, expander graphs, graphs with high girth, and random graphs of various densities and constructions. Additional questions that can be asked in the context of local models of graphs include optimization problems such as maximal and maximum matchings, independent sets, vertex covers, and graph colourings.

A related area of research is that of graph streaming problems - in which data concerning the problem arrives online and problems such as determining connectedness, checking the presence of subgraphs or minors, and colourability, are solved while the algorithm only has a limited memory and cannot choose which edges to access, with potential industrial applications in banking and big data.

A second related area is the study of large graphs and their structural properties, for example analysing the structure of graphs that are triangle-free, or H-free, or H-minor-free. This area of study is closely related to the famous triangle removal lemma and to the Szemeredi Regularity lemma. Approaches to problems in this domain may include some solely graph-theoretical components, but may also be aided by implementation in some cases.