Skip to content Search

The characteristics of today’s real-world networks make even the most basic graph processing tasks (such as computing connected components or shortest paths) challenging.

These networks are often very large and their size can easily exceed the capacity of the main memory of a single commodity machine. Even if a network can fit in a computer’s main memory, it might happen that using well-established optimal algorithms (such as breadth-first search) does not guarantee the computation is carried out fast enough. Whereas the consumer processors’ clock speeds have not been increasing lately, a typical processor’s core count is growing steadily. This motivates looking for efficient parallel algorithms in either the classical shared memory models (PRAM) or more recent massively parallel computation models (such as MapReduce) with input data distributed among multiple machines.

Another challenge that we face is that the networks evolve in time. In a typical scenario, a network can undergo small updates very frequently. The updates are so small that it appears unreasonable to recompute the required information from scratch after each update. This motivation has given rise to a very rich area of dynamic graph algorithms that seeks efficient data structures maintaining properties of dynamic graphs. Most of the work in this area so far has been theoretical. Practical evaluation of dynamic graph algorithms is still in its infancy.

The goal of our team’s research is to design and evaluate new parallel and dynamic algorithms for fundamental graph processing problems. First, we conduct theoretical investigation of what parallel work-depth tradeoffs can be achieved and to what extent these solutions can be robust in dynamic environments. Second, we engineer implementations and perform experimental evaluation of dynamic and parallel graph algorithms for problems of practitioners’ interest.

The team’s research is partially aligned with the goals of the NCN grant 2022/47/D/ST6/02184 “Parallel and exact algorithms for path problems in directed graphs” hosted by IDEAS NCBR.

Research Team Leader


Adam Karczmarz

Adam Karczmarz is a postdoctoral researcher at IDEAS NCBR, also affiliated with the University of Warsaw, from where he obtained a Ph.D. degree in 2019. He is broadly interested in the theoretical and practical aspects of algorithm and data structures design. His research so far has concentrated mainly on classical graph processing problems such as reachability and shortest paths computation, especially in dynamic, fault-tolerant, and parallel settings that address some of the most significant challenges of today’s large networks. Lately, he has also been exploring connections between classical algorithm design and machine learning.

Ministry of Education and Science scholarship for outstanding young scientists (2022)

FNP START scholarship (2020)

NCN Etiuda scholarship (2017)

NCN Sonata Grant (2023)

NCN Preludium Grant (2019)

Other research groups and teams

  • Sequential Decision Making We believe that the development of techniques for effective analysis and decision-making in sequences will lead to the creation of intelligent and autonomous systems. This will translate into many practical solutions, ranging from controlling robots or autonomous vehicles to multi-step decision or deductive procedures, such as mathematical proofs.
    Piotr Miłoś
  • Systems Security and Data Privacy Several machine learning applications involve issues where privacy plays a special role.
    Stefan Dziembowski
  • Parallel and Dynamic Graph Algorithms The characteristics of today’s real-world networks make even the most basic graph processing tasks (such as computing connected components or shortest paths) challenging.
    Adam Karczmarz