Graphs are perhaps one of the most efficient tools to describe complex systems in many different contexts. The use of graphs has allowed researchers to identify patterns, optimize processes and analyze the dynamics of systems and entities. It is of no surprise the numerous advances on multiples fields that have been achieve by studying basic relationships between multiple nodes and edges. One of the major research areas studied by the members of GAMMA deals with solving challenging optimization problems on graphs.
Maximum Clique Problems on Sparse Graphs
The maximum clique problem is one of the most recognized graph theoretical problems. Indeed, it was listed as one of the famous Karp’s 21 NP-complete problems. Since its conception, several theoretical and practical developments in multiple areas have been found by studying solution approaches for this problem. Despite most efforts, maximum clique remains to this day a computationally challenging problem, having famous synthetic benchmark instances with 1,000 vertices yet to be solved. An interesting observation, though is that many real-life instances with millions of vertices are often solved in just a few seconds by apparently simple algorithms. In collaboration with researchers from other institutions, we have studied this problem in detail.
Graph partitioning is often utilized as a reduction technique in order to obtain representations of a graph which are more suitable for analysis. Several applications of graph partitioning include the load balancing for parallel processing, districting, complexity reduction for VLSI network design problems, and mitigating cascading failures in interdependent cyber-physical systems. Furthermore, graph partitioning has been utilized as a technique for detecting clusters within social, pathological and biological networks. There exists a wide range of partitioning problems which differ by the restrictions they impose on the resulting subgraphs of the partition. In GAMMA, we are interested in developing exact approaches for solving several variations of graph partitioning problems.
Random Events on Graphs
A wide variety of problems arising from different scientific domains involve the careful study of random events that occur on scattered locations of a given network. Among the many different examples, perhaps the studies that have permeated the literature the most, are the ones that involve the analysis of events that take place on infrastructure networks. One of the key components pertaining to the study of random events in networks is the statistical characterization of the distances between them. Given that the events take place on random locations across a given network, studying the random variables representing these distances can bring valuable information regarding the dynamics behind these complex systems. As part of our research, we are interested in identifying a characterization of several statistical properties of the distance between random events on a network.