Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Simon Fraser University

$55,000.00

Complexity of Partition Problems

EF 2021-22

Résumé
This proposal concerns several problem areas within the common theme of algorithmic graph theory. While many standard algorithmic and optimization problems are intractable (that is, NP-complete) in general, efficient algorithms become possible if the inputs are restricted to certain natural and well-structured networks (that is, graphs and digraphs). This is in particular true for many graph colouring problems and their generalizations and variants studied in this research. One of the objectives will be to illuminate the kind of structure that is helpful for such problems, and identify such situations. Sometimes this involves proving intractability (NP-completeness) of the problems investigated, at other times it involves designing algorithms that take advantage of the special structure these networks posses. This may take various forms, from using a geometric representation of the input, to using its recursive description, or other characterization. While this has been well explored in the case of undirected graphs, the novelty of our approach will be to systematically widen the focus to directed graphs. Surprisingly, it appears that with small exceptions the analogies are not sufficiently well explored, and we have already observed in recent investigations that interesting novel phenomena can and do arise. The focus on general digraphs is a significant extension of the current theory and applications of undirected graph classes (and their corresponding specialized algorithms), which is quite established and very successful. Our main focus will be on partition problems, typified (in the undirected case) by such classical concepts as graph colouring, graph homomorphisms, and matrix partitions. The structures investigated will be defined by the existence of special ordering, or the existence of special orientations, or the existence of novel geometric representations. In addition, we will examine the power of such descriptions, and study which digraph classes can be described by such characterizations.
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-2019-04221
Name nom
Hell, Pavol
Department département
Computing Science, School of - Computing Science, School of
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2021
Competition year année de concours
2019
Award amount
55000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Installment
inst:3
Partie
1
Nb partie
5
Application title
Complexity of Partition Problems
Keyword
NSERC
Application summary
This proposal concerns several problem areas within the common theme of algorithmic graph theory. While many standard algorithmic and optimization problems are intractable (that is, NP-complete) in general, efficient algorithms become possible if the inputs are restricted to certain natural and well-structured networks (that is, graphs and digraphs). This is in particular true for many graph colouring problems and their generalizations and variants studied in this research. One of the objectives will be to illuminate the kind of structure that is helpful for such problems, and identify such situations. Sometimes this involves proving intractability (NP-completeness) of the problems investigated, at other times it involves designing algorithms that take advantage of the special structure these networks posses. This may take various forms, from using a geometric representation of the input, to using its recursive description, or other characterization. While this has been well explored in the case of undirected graphs, the novelty of our approach will be to systematically widen the focus to directed graphs. Surprisingly, it appears that with small exceptions the analogies are not sufficiently well explored, and we have already observed in recent investigations that interesting novel phenomena can and do arise. The focus on general digraphs is a significant extension of the current theory and applications of undirected graph classes (and their corresponding specialized algorithms), which is quite established and very successful. Our main focus will be on partition problems, typified (in the undirected case) by such classical concepts as graph colouring, graph homomorphisms, and matrix partitions. The structures investigated will be defined by the existence of special ordering, or the existence of special orientations, or the existence of novel geometric representations. In addition, we will examine the power of such descriptions, and study which digraph classes can be described by such characterizations.