New and traditional structural graph measures for logic and algorithms

Poskytovatel

Grantová agentura České republiky

Program

Standardní projekty

Veřejná soutěž

SGA0202600001

Hlavní účastníci

Masarykova univerzita / Fakulta informatiky

Druh soutěže

VS - Veřejná soutěž

Číslo smlouvy

26-21334S

Název projektu anglicky

New and traditional structural graph measures for logic and algorithms

Anotace anglicky

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.

Kategorie VaV

ZV - Základní výzkum

OECD FORD - hlavní obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

OECD FORD - vedlejší obor

—

OECD FORD - další vedlejší obor

—

CEP - odpovídající obory <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)

AF - Dokumentace, knihovnictví, práce s informacemi<br>BC - Teorie a systémy řízení<br>BD - Teorie informace<br>IN - Informatika

Zahájení řešení

1. 1. 2026

Ukončení řešení

31. 12. 2028

Poslední stav řešení

Z - Začínající víceletý projekt

Poslední uvolnění podpory

—

Důvěrnost údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Systémové označení dodávky dat

CEP26-GA0-GA-R

Datum dodání záznamu

4. 5. 2026

Celkové uznané náklady

10 258 tis. Kč

Výše podpory ze státního rozpočtu

9 226 tis. Kč

Ostatní veřejné zdroje financování

1 032 tis. Kč

Neveřejné tuz. a zahr. zdroje finan.

0 tis. Kč