Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Alberta

$10,000.00

Structure and randomness of NP-complete problems

FY 2008-09

Summary
NP-complete problems, such as Satisfiability(SAT), Constraint Satisfaction(CSP), Planning, Hamiltonian Cycle etc, have many practical applications, ranging from formal verification of hardware and software to finding the best route for mail delivery. The last decade witnessed impressive progress of the solvers of NP-complete problems in general, and Satisfiability in particular. This progress was the result of a permanent competition between finding new, challenging instances and designing efficient solvers able to tackle the challenges. We believe that producing new challenging instances/models is not enough for improving our ability to solve hard problems - characterizing and classifying the new instances is also necessary. This ensures that any progress made in solving some instances can be used (or adapted) to solve an entire class of instances. The first moves in this direction are to investigate the structural properties of these instances and to assess the influence of these properties on the instances difficulty. The main goal is to better understand, characterize, classify and compare instances. We intend to pursue this goal by investigating instances of two NP-complete problems: Subgraph Isomorphism and Satisfiability, their conversions, their structural properties and the relationship between these properties and instance hardness. This research is expected to make both empirical and theoretical contributions. Although this research work focuses on Subgraph Isomorphism and Satisfiability, its results may be applied or adapted to other NP-complete problems. We believe that the investigation of the structure and its influence on instances hardness has the potential of improving our ability to solve hard combinatorial problems by identifying some properties of the instances which can be used for designing more efficient solvers.
Program
Discovery Grants Program - Individual
Location
Alberta, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
327477-2006
Name nom
Anton, CalinDoru
Department département
Augustana, Faculty of
Organization id
9
Institution établissement
University of Alberta
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2008
Competition year année de concours
2006
Award amount
10000
Program id
RGPIN
Program nane 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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
802
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
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
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
3
Nb partie
3
Application title
Structure and randomness of NP-complete problems
Keyword
NA
Application summary
NP-complete problems, such as Satisfiability(SAT), Constraint Satisfaction(CSP), Planning, Hamiltonian Cycle etc, have many practical applications, ranging from formal verification of hardware and software to finding the best route for mail delivery. The last decade witnessed impressive progress of the solvers of NP-complete problems in general, and Satisfiability in particular. This progress was the result of a permanent competition between finding new, challenging instances and designing efficient solvers able to tackle the challenges. We believe that producing new challenging instances/models is not enough for improving our ability to solve hard problems - characterizing and classifying the new instances is also necessary. This ensures that any progress made in solving some instances can be used (or adapted) to solve an entire class of instances. The first moves in this direction are to investigate the structural properties of these instances and to assess the influence of these properties on the instances difficulty. The main goal is to better understand, characterize, classify and compare instances. We intend to pursue this goal by investigating instances of two NP-complete problems: Subgraph Isomorphism and Satisfiability, their conversions, their structural properties and the relationship between these properties and instance hardness. This research is expected to make both empirical and theoretical contributions. Although this research work focuses on Subgraph Isomorphism and Satisfiability, its results may be applied or adapted to other NP-complete problems. We believe that the investigation of the structure and its influence on instances hardness has the potential of improving our ability to solve hard combinatorial problems by identifying some properties of the instances which can be used for designing more efficient solvers.
University of Alberta - $10,000 Grant (2008-09) | Canada Spends