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

  • Precision Forestry The use of remote sensing data in obtaining information about forests has a long, almost 100-year history.
    Krzysztof Stereńczak
  • AI for Security Amongst other things, we develop multi-level management systems to protect critical infrastructure as well as systems for securing key state services against both kinetic and cyber threats.
    Tomasz Michalak
  • Sustainable Machine Learning For Autonomous Machines Our solutions could potentially be used in drones as a tool supporting the protection of national parks, including animals against poaching. They allow for fast and efficient monitoring of large land areas in remote locations...
    Bartosz Zieliński