Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$34,000.00

Structure and algorithms for graphs with forbidden induced subgraphs

FY 2022-23

Summary
Graphs consist of a finite set (vertices) and connections between them (edges). Many real-world data structures fit into this framework, from airports (two of which are connected if there is non-stop flight between them) to social media accounts (two of which are connected if they are friends on the social media network). Algorithms for graphs shape our everyday experiences. Many airlines use a simple heuristic to increase the variety of in-flight movies by having a different selection for eastbound and westbound flights, since most passengers travel once in each direction. Other problems might require (close to) optimum solutions, making the use of heuristics less feasible. As an example, a company might wish to optimize the variety of advertisements that passengers see at airports. Creating an ad is expensive, and thus the company would like to know how they can use as few different ads as possible to ensure that when no passenger sees the same ad at two airports connected by a non-stop flight. This can be stated in terms of graphs: Given a graph, the goal is to assign a natural number to every vertex such that for every edge, its two vertices have different numbers, and the highest number used is as small as possible. This is known as the Graph Colouring Problem, which is computationally intractable. More generally, graph problems arise often in the context of finding an efficient solution for a system described by connections, but they tend to be intractable when no assumptions are made about the input graph. A central question of the proposed research is the following: Which structural assumptions about input graphs make classic graph problems (such as colouring, maximum stable set, and maximum clique) efficiently solvable? Usually, structural assumptions are formulated as forbidden local patterns (induced subgraphs), and the goal is to deduce a sufficient amount of global information about graphs that avoid these patterns to process them quickly. This gives rise to further questions: Can we give a construction for all graphs in a graph class? Can we show that certain graph parameters depend on each other in this graph class, but not in general? Can we show that there is a common pattern that occurs in all very large graphs in the class? Answers to these questions fit into the larger context of describing what a large structure looks like if it does not contain a specified smaller structure. Seminal results related to this question have been obtained or announced in other areas, such as graph minors and matroid minors. This programme benefits HQP by providing a background that is suitable both for industry and academic careers. While the primary impact of this proposal will be felt in the advancement of knowledge in the fields of graph theory, and theoretical computer science in general, it also has the potential to supply tools for practical uses including transportation networks, social media, and resource allocation and distribution.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2020-03912
Name nom
Spirkl, Sophie
Department département
Combinatorics and Optimization - Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2020
Award amount
34000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:3
Partie
1
Nb partie
5
Application title
Structure and algorithms for graphs with forbidden induced subgraphs
Application summary
Graphs consist of a finite set (vertices) and connections between them (edges). Many real-world data structures fit into this framework, from airports (two of which are connected if there is non-stop flight between them) to social media accounts (two of which are connected if they are friends on the social media network). Algorithms for graphs shape our everyday experiences. Many airlines use a simple heuristic to increase the variety of in-flight movies by having a different selection for eastbound and westbound flights, since most passengers travel once in each direction. Other problems might require (close to) optimum solutions, making the use of heuristics less feasible. As an example, a company might wish to optimize the variety of advertisements that passengers see at airports. Creating an ad is expensive, and thus the company would like to know how they can use as few different ads as possible to ensure that when no passenger sees the same ad at two airports connected by a non-stop flight. This can be stated in terms of graphs: Given a graph, the goal is to assign a natural number to every vertex such that for every edge, its two vertices have different numbers, and the highest number used is as small as possible. This is known as the Graph Colouring Problem, which is computationally intractable. More generally, graph problems arise often in the context of finding an efficient solution for a system described by connections, but they tend to be intractable when no assumptions are made about the input graph. A central question of the proposed research is the following: Which structural assumptions about input graphs make classic graph problems (such as colouring, maximum stable set, and maximum clique) efficiently solvable? Usually, structural assumptions are formulated as forbidden local patterns (induced subgraphs), and the goal is to deduce a sufficient amount of global information about graphs that avoid these patterns to process them quickly. This gives rise to further questions: Can we give a construction for all graphs in a graph class? Can we show that certain graph parameters depend on each other in this graph class, but not in general? Can we show that there is a common pattern that occurs in all very large graphs in the class? Answers to these questions fit into the larger context of describing what a large structure looks like if it does not contain a specified smaller structure. Seminal results related to this question have been obtained or announced in other areas, such as graph minors and matroid minors. This programme benefits HQP by providing a background that is suitable both for industry and academic careers. While the primary impact of this proposal will be felt in the advancement of knowledge in the fields of graph theory, and theoretical computer science in general, it also has the potential to supply tools for practical uses including transportation networks, social media, and resource allocation and distribution.