New and traditional structural graph measures for logic and algorithms
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202600001
Main participants
Masarykova univerzita / Fakulta informatiky
Contest type
VS - Public tender
Contract ID
26-21334S
Alternative language
Project name in Czech
New and traditional structural graph measures for logic and algorithms
Annotation in Czech
One of the approaches to designing algorithms for generally intractable problems relies on investigation of suitable structural measures of the inputs. Studying such measures leads to a better understanding of combinatorial and structural dividing lines between tractable and intractable instances. Our proposal focuses on structural measures and parameters related to first-order logic of graphs. We plan to explore this live direction by combining existing methods and new tools from structural combinatorics and graph logic, taking advantage of the combinatorial/logical duality of many such parameters. Namely we plan to study; (a) combinatorial properties and efficient parameterized computation and approximation of some of the computationally hard new parameters, with applications in algorithmic metatheorems; (b) in particular, fine properties of the hereditary product structure measure which we have just recently introduced; and (c) the questions of FO definability, interpretability and non-interpretability of certain graph classes in other classes, based on the parameters studied.
Scientific branches
R&D category
ZV - Basic research
OECD FORD - main branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - secondary branch
—
OECD FORD - another secondary branch
—
CEP - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
AF - Documentation, librarianship, work with information<br>BC - Theory and management systems<br>BD - Information theory<br>IN - Informatics
Solution timeline
Realization period - beginning
Jan 1, 2026
Realization period - end
Dec 31, 2028
Project status
Z - Beginning multi-year project
Latest support payment
—
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
CEP26-GA0-GA-R
Data delivery date
May 4, 2026
Finance
Total approved costs
10,258 thou. CZK
Public financial support
9,226 thou. CZK
Other public sources
1,032 thou. CZK
Non public and foreign sources
0 thou. CZK