Structural graph theory and parameterized complexity
Project goals
Many real-world algorithmic problems turn out to be intractable in their full generality. Theory of parameterized complexity, however, provides a useful framework for a refined analysis of such hard problems, and for designing conceptually new algorithmsthat can solve hard problems for the real-world instances efficiently. In contrast to heuristics, this approach provides guarantied runtime bounds.Graphs are combinatorial structures suitable for modeling many discrete and optimization problems. Structural graph theory has already proved very useful in parameterized algorithmics. For instance, most of traditional hard problems are efficiently solvable on graphs of bounded tree-width. We plan to exploit other structural properties of graphs like branch-width, DAG-width, rank-width, or their topological properties. Our goal is to find new application areas of structural graph theory in parameterized algorithm design, by collaboration of our research groups from both areas.
Keywords
fixed parameter tractabilityexponential algorithmtree-widthgraph minortopological graph
Public support
Provider
Czech Science Foundation
Programme
International projects
Call for proposals
Mezinárodní projekty 3 (SGA02009GA1GC)
Main participants
—
Contest type
VS - Public tender
Contract ID
201/09/J021
Alternative language
Project name in Czech
Strukturální teorie grafů a parametrizovaná složitost
Annotation in Czech
Mnoho algoritmických problémů z reálného světa se ukazují jako nezvladatelné v plné obecnosti. Teorie parametrizované složitosti nám však dává užitečný rámec nástrojů pro jemnější analýzu obtížnosti těchto těžkých problémů a pro návrh koncepčně nových algoritmů, které dokáží řešit reálné instance těžkých problémů efektivněji. Na rozdíl od heuristických přístupů tak získáme i garantované ohraničení času. Grafy jako kombinatorické struktury jsou vhodné pro modelování diskrétních a optimalizačních problémů. Přitom strukturální teorie grafů se ukazuje jako velmi užitečná v parametrizovaných algoritmech. Například většina tradičně těžkých problémů je rychle řešitelná na grafech omezené stromové šířky.Naším plánem je využít i další strukturální vlastnosti grafů jako větvená šířka, DAG šířka, ranková šířka, či jejich topologické vlastnosti. Cílem je nalézt nové oblasti aplikací strukturální teorie grafů v navrhování parametrizovaných algoritmů, čehož bude dosaženo spoluprácí našich výzkumných
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
IN - Informatics
CEP - secondary branch
BA - General mathematics
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
First we gave a thorough overview of parameterized complexity of known problems on directed graphs with respect to known directed ?width? measures. Moreover, we showed that most of these problems remain NP-complete even for very restricted classes of directed graphs (using two new measures DAG-depth and K-width). Some of the complexity bounds were taken from literature, however the rest was prove
Solution timeline
Realization period - beginning
Jan 1, 2009
Realization period - end
Dec 31, 2010
Project status
U - Finished project
Latest support payment
Apr 16, 2010
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
CEP11-GA0-GC-U/03:3
Data delivery date
Feb 9, 2015
Finance
Total approved costs
1,014 thou. CZK
Public financial support
1,014 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
1 014 CZK thou.
Public support
1 014 CZK thou.
0%
Provider
Czech Science Foundation
CEP
IN - Informatics
Solution period
01. 01. 2009 - 31. 12. 2010