Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Simon Fraser University

$62,000.00

Complexity of Partition Problems

EF 2015-16

Résumé
Graph colouring is a basic graph optimization problem whose study dominates graph theory and algorithms, from the celebrated four-colour theorem to its applications in scheduling and operations research. This proposal addresses fundamental computational questions connected with the problem of k-colouring, as well as two of its important generalizations, namely the H-colouring, and the M-partition problems. These are mainly of interest because of their connection with the constraint satisfaction problem, and with the study of graph perfection, respectively. It is well known that each k-colouring problem is NP-complete or polynomial time solvable. In the more general context of constraint satisfaction problems, such dichotomy has been conjectured by Feder and Vardi. In the most general form of M-partitions, the existence of dichotomy is also open. The Feder-Vardi conjecture has been driving theoretical research in constraint satisfaction for the past two decades. While there is now a natural conjecture for a classification of which H lead to polynomial time solvable problems (one version of such a conjecture is formulated in terms of existence of certain ""polymorphisms""), the Feder-Vardi conjecture still seems beyond reach. On the other hand, there are many natural combinatorial problems arising from the conjecture that need to considered, and might impact the search for an answer. These include problems of classifying digraphs possessing particular polymorphisms, their relation to existing and well studied graph classes such as interval and chordal graphs, and the recognition and characterization problems for such digraphs. At the same time, the dichotomy conjecture and classification, as well as the basic k-colouring problem and the more general M-partition problems, appear to be more accessible, and worthy of study, for restricted classes of digraphs. In fact, the restriction of the Feder-Vardi conjecture to undirected graphs is a well-known result of Nesetril and the proposer, that was one of two main motivations for the Feder-Vardi conjecture. This work has potential impact on the understanding of the difficulties in solving constraint satisfaction problems. Constraint satisfaction problems model many problems in scheduling, logistics, databases, and artificial intelligence.
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-2014-05508
Name nom
Hell, Pavol
Department département
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
2015
Competition year année de concours
2014
Award amount
62000
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
Partie
2
Nb partie
5
Application title
Complexity of Partition Problems
Keyword
NSERC
Application summary
Graph colouring is a basic graph optimization problem whose study dominates graph theory and algorithms, from the celebrated four-colour theorem to its applications in scheduling and operations research. This proposal addresses fundamental computational questions connected with the problem of k-colouring, as well as two of its important generalizations, namely the H-colouring, and the M-partition problems. These are mainly of interest because of their connection with the constraint satisfaction problem, and with the study of graph perfection, respectively. It is well known that each k-colouring problem is NP-complete or polynomial time solvable. In the more general context of constraint satisfaction problems, such dichotomy has been conjectured by Feder and Vardi. In the most general form of M-partitions, the existence of dichotomy is also open. The Feder-Vardi conjecture has been driving theoretical research in constraint satisfaction for the past two decades. While there is now a natural conjecture for a classification of which H lead to polynomial time solvable problems (one version of such a conjecture is formulated in terms of existence of certain ""polymorphisms""), the Feder-Vardi conjecture still seems beyond reach. On the other hand, there are many natural combinatorial problems arising from the conjecture that need to considered, and might impact the search for an answer. These include problems of classifying digraphs possessing particular polymorphisms, their relation to existing and well studied graph classes such as interval and chordal graphs, and the recognition and characterization problems for such digraphs. At the same time, the dichotomy conjecture and classification, as well as the basic k-colouring problem and the more general M-partition problems, appear to be more accessible, and worthy of study, for restricted classes of digraphs. In fact, the restriction of the Feder-Vardi conjecture to undirected graphs is a well-known result of Nesetril and the proposer, that was one of two main motivations for the Feder-Vardi conjecture. This work has potential impact on the understanding of the difficulties in solving constraint satisfaction problems. Constraint satisfaction problems model many problems in scheduling, logistics, databases, and artificial intelligence.