Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Victoria

$31,000.00

Graph structure and algorithms

EF 2024-25

Résumé
Efficient computational solutions to combinatorial problems can often be derived from an understanding of the structure of graphs. My long-term goals are to discover graph structural properties which are of algorithmic importance, and to develop useful tools for solving combinatorial problems. Graph structures can be described in terms of orderings of vertices, orientations of edges, forbidden subgraphs, or forbidden substructures. Analyzing various structural properties of graphs gives rise to a wealth of exciting mathematical problems. The challenge of solving these problems lies in an understanding of specified structural properties. The short-term goals of my program involve the study of specified vertex orderings (e.g., min-orderings) of graphs and digraphs, orientation completion problems for various classes of oriented graphs, and partitions of graphs with forbidden induced subgraphs. Many optimization problems (e.g., graph colouring), which are NP-hard in general, can be solved efficiently for graphs that have good vertex ordering properties. The dichotomy theorem that we obtained for list homomorphism problems for graphs asserts that the polynomial cases are exactly the graphs which have min-orderings. Our result has impact on the study of constraint satisfaction problems which are the subject of research in artificial intelligence, and motivated the investigation of several other problems. Min-orderings again play an important role in classification of the complexity of those problems. The concept of min-orderings also has implications in matrix theory. Despite the importance of this concept, no polynomial time recognition algorithm for min-orderable digraphs is known. I am keen to study the structure of this digraph class and develop tools for solving related combinatorial problems. Graph structures are sometimes inherent in having certain orientations. For example, graphs which have local tournament orientations correspond to proper circular-arc graphs, and graphs which have quasi-transitive orientations are exactly the comparability graphs. Polynomial time algorithms for solving orientation completion problems have been devised for several classes of oriented graphs, including local tournaments and quasi-transitive oriented graphs. Recently, the complete list of obstructions for local tournament orientation completions has been found. It is an open problem to find the complete list of obstructions for quasi-transitive orientation completions. The study of structural properties of graphs and digraphs will be carried out with the view of obtaining computational solutions to combinatorial problems such as graph colouring, homomorphism, and orientation completion. My research projects will involve diversity researchers, including undergraduates, graduates, postdoc and other collaborators. My approach involves blending combinatorial arguments with methods from the theory of structured graphs and their geometric representations.
Programme
Discovery Grants Program - Individual
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2024-04701
Name nom
Huang, Jing
Department département
Mathematics and Statistics
Organization id
7
Institution établissement
University of Victoria
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
31000
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
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
803
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer communications
Area of application fr
Téléinformatique
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Graph structure and algorithms
Keywords
graph class; forbidden subgraph characterization; vertex ordering characterization; orientation; list homomorphism; graph partition and decomposition; recognition; algorithm; complexity; matrix ordering
Application summary
Efficient computational solutions to combinatorial problems can often be derived from an understanding of the structure of graphs. My long-term goals are to discover graph structural properties which are of algorithmic importance, and to develop useful tools for solving combinatorial problems. Graph structures can be described in terms of orderings of vertices, orientations of edges, forbidden subgraphs, or forbidden substructures. Analyzing various structural properties of graphs gives rise to a wealth of exciting mathematical problems. The challenge of solving these problems lies in an understanding of specified structural properties. The short-term goals of my program involve the study of specified vertex orderings (e.g., min-orderings) of graphs and digraphs, orientation completion problems for various classes of oriented graphs, and partitions of graphs with forbidden induced subgraphs. Many optimization problems (e.g., graph colouring), which are NP-hard in general, can be solved efficiently for graphs that have good vertex ordering properties. The dichotomy theorem that we obtained for list homomorphism problems for graphs asserts that the polynomial cases are exactly the graphs which have min-orderings. Our result has impact on the study of constraint satisfaction problems which are the subject of research in artificial intelligence, and motivated the investigation of several other problems. Min-orderings again play an important role in classification of the complexity of those problems. The concept of min-orderings also has implications in matrix theory. Despite the importance of this concept, no polynomial time recognition algorithm for min-orderable digraphs is known. I am keen to study the structure of this digraph class and develop tools for solving related combinatorial problems. Graph structures are sometimes inherent in having certain orientations. For example, graphs which have local tournament orientations correspond to proper circular-arc graphs, and graphs which have quasi-transitive orientations are exactly the comparability graphs. Polynomial time algorithms for solving orientation completion problems have been devised for several classes of oriented graphs, including local tournaments and quasi-transitive oriented graphs. Recently, the complete list of obstructions for local tournament orientation completions has been found. It is an open problem to find the complete list of obstructions for quasi-transitive orientation completions. The study of structural properties of graphs and digraphs will be carried out with the view of obtaining computational solutions to combinatorial problems such as graph colouring, homomorphism, and orientation completion. My research projects will involve diversity researchers, including undergraduates, graduates, postdoc and other collaborators. My approach involves blending combinatorial arguments with methods from the theory of structured graphs and their geometric representations.