Hola,
¿eres nuevo aquí?

Registrate y conecta tu empresa con financiación pública, partners y proyectos.

BUKA

Financiado

Limits of Structural Tractability

The combination of methods from logic and graph theory has been extremely successful in the design of algorithms, in complexity theory, and other areas of theoretical computer science. A success story exemplifying the power of thi... ver más

30/09/2029

UNIWARSAW

2M€

Presupuesto del proyecto: 2M€

Líder del proyecto

UNIWERSYTET WARSZAWSKI No se ha especificado una descripción o un objeto social para esta compañía.

TRL 4-5

Ver 1 Participantes

Financiación concedida El organismo HORIZON EUROPE notifico la concesión del proyecto el día 2023-12-13

Línea de financiación objetivo El proyecto se financió a través de la siguiente ayuda:

ERC-2023-COG: ERC CONSOLIDATOR GRANTS

I+D

Cerrada hace 1 año

0% 100%

1 Participantes

UNIWARSAW

1.94M€ | Lider

Proyectos interesantes

GRAPHCOSY GRAPH reconstruction, COspectrality and SYnchronisation thro... 188K€ Cerrado

CRACKNP Finding Cracks in the Wall of NP completeness 1M€ Cerrado

PGC2018-095322-B-C21 OPTIMIZACION INTELIGENTE EN GRAFOS 63K€ Cerrado

PGC2018-095322-B-C22 METAHEURISTICAS EFICIENTES PARA LA OPTIMIZACION EN GRAFOS 74K€ Cerrado

TIN2010-20967-C04-03 TEORIA, APLICACIONES Y SINERGIA EN SAT, CSP Y FDL 77K€ Cerrado

CONJEXITY Investigating the Conjectures of Fine-Grained Complexity 1M€ Cerrado

Últimas noticias

27-11-2024: Videojuegos y creaci... Se abre la línea de ayuda pública: Ayudas para la promoción del sector del videojuego, del pódcast y otras formas de creación digital

27-11-2024: DGIPYME En las últimas 48 horas el Organismo DGIPYME ha otorgado 1 concesiones

27-11-2024: FUNDACION-EOI En las últimas 48 horas el Organismo FUNDACION EOI ha otorgado 2 concesiones

Duración del proyecto: 69 meses Fecha Inicio: 2023-12-13
Fecha Fin: 2029-09-30

Líder del proyecto

UNIWERSYTET WARSZAWSKI

TRL 4-5

Presupuesto del proyecto 2M€

Descripción del proyecto The combination of methods from logic and graph theory has been extremely successful in the design of algorithms, in complexity theory, and other areas of theoretical computer science. A success story exemplifying the power of this approach is the recent development in the algorithmic structure theory of sparse graphs. In this line of research, structural results stemming from Robertson and Seymour’s graph minor theory, and the more recent sparsity theory of Nešetřil and Ossona de Mendez, were com- bined with logical methods in order to obtain a systematic understanding of tractability. An example result in this area states that every graph property definable in first order logic can be decided in linear time, for all planar graphs. Culminating a long line of research, Grohe, Kreutzer, and Siebertz gener- alized this result to all nowhere dense graph classes. Those are very general classes of sparse graphs, which include the class of planar graphs, classes of bounded maximum degree, or classes excluding a fixed minor. Moreover, this result completely delimits the tractability frontier for sparse graph classes. However, many classes are tractable, but not sparse. The recent twin-width theory, drawing on deep connections between logic and enumerative combinatorics, achieves an analogue of the result of Grohe et al. for all ordered graphs. Thus, algorithmic tractability is now understood in two contexts: of sparse graphs, and of ordered graphs. This project sets out to characterize all tractable graph classes. This requires developing a systematic understanding of the logical structure underlying algorithmic tractability. The tools I intend to apply and develop originate from graph structure theory, and from stability theory, one of the most successful areas in logic recently. The expected results will be of foundational nature, and of interest primarily to theoretical computer scientists, graph theorists, and logicians.

Conecta tu I+D

Entra hoy

Financiación

Empresas

CTIs/Universidades

Proyectos

Investigadores