Structural properties and algorithmic complexity of discrete problems
Project goals
Many practical algorithmic problems have a core based on the structures of discrete mathematics, like on graphs or matroids. It turns out that majority of the basic discrete problems are "almost unsolvable" (NP-hard) in their general formulation. Still,one has to look for, at least, approximate solutions to hard problems, or at solutions working under additional assumptions. The key to finding suitable assumptions allowing for effective solutions of hard problems lies in understanding their structure.As an example of a great success of structural approaches, we mention the deep and revolutionary Graph Minor Theory of Robertson and Seymour. Moreover, there is the new theory of parametrized complexity of algorithms by Downey and Fellows. The topic of our project is development of structural approaches to hard discrete problems, especially with emphasis on tree- or branch-width of graphs and matroids. Those include new applications of the structural methods in design of fixed parameter tractable
Keywords
graphmatroidtree-widthclique-widthgraph minorscrossing numberparametrized complexity
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 8 (SGA02005GA-ST)
Main participants
—
Contest type
VS - Public tender
Contract ID
201/05/0050
Alternative language
Project name in Czech
Strukturální vlastnosti a algoritmická složitost diskrétních problémů
Annotation in Czech
V pozadí mnoha praktických algoritmických problémů stojí struktury diskrétní matematiky, jako je graf nebo obecněji matroid. Jak se však ukazuje, většina již základních diskrétních problémů je "téměř neřešitelná" (NP-těžká) ve své obecné formulaci. Přesto je žádoucí hledat alespoň přibližná řešení takových těžkých problémů, nebo řešení fungující za dodatečných předpokladů. Klíčem k nalezení vhodných předpokladů umožňujících efektivní řešení těžkých problémů přitom je pochopení jejich vnitřní struktury.Jako příklad úspěchu tohoto strukturálního přístupu bychom zmínili hlubokou a převratnou teorii grafových minorů Robertsona a Seymoura. Mimo to je zde nová teorie parametrizované složitosti algoritmů Downeyho a Fellowse. Náplní našeho projektuje rozvíjení strukturálních přístupů k těžkým diskrétním problémům, zvláště s důrazem na stromovou či větvenou šířku grafů a matroidů. To zahrnuje nové aplikace strukturálních metod při vývoji parametrizovaně efektivních algoritmů na grafech, například
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
BA - General mathematics
CEP - secondary branch
IN - Informatics
CEP - another secondary branch
—
10101 - Pure mathematics
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
During research on our grant project we have found out many new theoretical results in the areas of structural and topological properties of combinatorial structures (mainly of graphs and matroids), and of their algorithmic applications. These new statem
Solution timeline
Realization period - beginning
Jan 1, 2005
Realization period - end
Dec 31, 2007
Project status
U - Finished project
Latest support payment
May 2, 2007
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP08-GA0-GA-U/04:3
Data delivery date
Dec 16, 2008
Finance
Total approved costs
472 thou. CZK
Public financial support
453 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
28 thou. CZK
Basic information
Recognised costs
472 CZK thou.
Public support
453 CZK thou.
95%
Provider
Czech Science Foundation
CEP
BA - General mathematics
Solution period
01. 01. 2005 - 31. 12. 2007