IC Colloquium: Finding patterns, short cycles and long shortest paths in graphs
Event details
| Date | 07.02.2022 |
| Hour | 15:00 › 16:00 |
| Location | Online |
| Category | Conferences - Seminars |
| Event Language | English |
By : Mina Dalirrooyfard - MIT
IC Faculty candidate
Abstract
This talk is about finding useful structures in a graph using fast algorithms, and/or showing that no such fast algorithms exist under popular hypotheses from the field of Fine-Grained Complexity. These graph structures can be a small fixed sized pattern subgraph, or more specific bigger structures such as the longest shortest path in the graph whose length is known as the diameter of a graph. Finding these structures has many applications, from protein-protein interactions in biology to anomaly detection in networks.
We first focus on the Graph Pattern Detection or Subgraph Isomorphism Problem that asks for detecting a fixed-sized subgraph pattern in a given graph. We give the first fine-grained lower bounds for this problem for arbitrary patterns. We also consider the "counting" version of this problem and show that it is hard "on average" when the input graph is drawn from the uniform distribution. Then we move on to patterns that are not necessarily fixed sized and are represented by graph parameters such as diameter, radius, eccentricity and girth. In this part we show that the folklore 2-approximation algorithm for computing the diameter of the graph is tight under SETH, a fine-grained complexity hypothesis. We will conclude with ideas for future work.
Bio
Mina Dalirrooyfard is a final year PhD student at MIT, advised by Virginia Vassilevska Williams. Her research area is graph algorithms and fine-grained complexity, with a particular focus on graph pattern detection, graph parameter estimation and fine-grained average-case complexity.
More information
IC Faculty candidate
Abstract
This talk is about finding useful structures in a graph using fast algorithms, and/or showing that no such fast algorithms exist under popular hypotheses from the field of Fine-Grained Complexity. These graph structures can be a small fixed sized pattern subgraph, or more specific bigger structures such as the longest shortest path in the graph whose length is known as the diameter of a graph. Finding these structures has many applications, from protein-protein interactions in biology to anomaly detection in networks.
We first focus on the Graph Pattern Detection or Subgraph Isomorphism Problem that asks for detecting a fixed-sized subgraph pattern in a given graph. We give the first fine-grained lower bounds for this problem for arbitrary patterns. We also consider the "counting" version of this problem and show that it is hard "on average" when the input graph is drawn from the uniform distribution. Then we move on to patterns that are not necessarily fixed sized and are represented by graph parameters such as diameter, radius, eccentricity and girth. In this part we show that the folklore 2-approximation algorithm for computing the diameter of the graph is tight under SETH, a fine-grained complexity hypothesis. We will conclude with ideas for future work.
Bio
Mina Dalirrooyfard is a final year PhD student at MIT, advised by Virginia Vassilevska Williams. Her research area is graph algorithms and fine-grained complexity, with a particular focus on graph pattern detection, graph parameter estimation and fine-grained average-case complexity.
More information
Practical information
- General public
- Free
Contact
- Host: Ola Svensson