8 citations · 14 across the 18 of their papers we have counts for
30 papers
Strongly Polynomial Parallel Maximum Flow Revisited
Adam Karczmarz, Paweł Pilarski
We study the maximum flow problem in directed networks with real capacities in the parallel setting. For a network with vertices and arcs, we show that a randomized paralle…
VARSHAP: Addressing Global Dependency Problems in Explainable AI with Variance-Based Local Feature Attribution
Mateusz Gajewski, Mikołaj Morzy, Adam Karczmarz +1
Existing feature attribution methods like SHAP often suffer from global dependence, failing to capture true local model behavior. This paper introduces VARSHAP, a novel model-agnos…
Fully Dynamic Algorithms for Transitive Reduction
Gramoz Goranci, Adam Karczmarz, Ali Momeni +1
Given a directed graph , a transitive reduction of (first studied by Aho, Garey, Ullman [SICOMP `72]) is a minimal subgraph of that preserves the reachability rela…
On Incremental Approximate Shortest Paths in Directed Graphs
Adam Górkiewicz, Adam Karczmarz
In this paper, we show new data structures maintaining approximate shortest paths in sparse directed graphs with polynomially bounded non-negative edge weights under edge insertion…
Towards Scalable and Practical Batch-Dynamic Connectivity
Quinten De Man, Laxman Dhulipala, Adam Karczmarz +3
We study the problem of dynamically maintaining the connected components of an undirected graph subject to edge insertions and deletions. We give the first parallel algorithm for t…
Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
Vikrant Ashvinkumar, Aaron Bernstein, Adam Karczmarz
In the restricted shortest paths problem, we are given a graph whose edges are assigned two non-negative weights: lengths and delays, a source , and a delay threshold . T…
Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more
Adam Karczmarz, Da Wei Zheng
Le and Wulff-Nilsen [SODA '24] initiated a systematic study of VC set systems to unweighted -minor-free directed graphs. We extend their results in the following ways: $\bulle…
Fully Dynamic Shortest Paths in Sparse Digraphs
Adam Karczmarz, Piotr Sankowski
We study the exact fully dynamic shortest paths problem. For real-weighted directed graphs, we show a deterministic fully dynamic data structure with worst-ca…
Fully Dynamic Strongly Connected Components in Planar Digraphs
Adam Karczmarz, Marcin Smulewicz
In this paper, we consider maintaining strongly connected components (SCCs) of a directed planar graph subject to edge insertions and deletions. We show a data structure maintainin…
Accurate estimation of feature importance faithfulness for tree models
Mateusz Gajewski, Adam Karczmarz, Mateusz Rapicki +1
In this paper, we consider a perturbation-based metric of predictive faithfulness of feature rankings (or attributions) that we call PGI squared. When applied to decision tree-base…
Max -Flow Oracles and Negative Cycle Detection in Planar Digraphs
Adam Karczmarz
We study the maximum -flow oracle problem on planar directed graphs where the goal is to design a data structure answering max -flow value (or equivalently, min -cut…
Deterministic Fully Dynamic SSSP and More
Jan van den Brand, Adam Karczmarz
We present the first non-trivial fully dynamic algorithm maintaining exact single-source distances in unweighted graphs. This resolves an open problem stated by Sankowski [COCOON 2…
Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form
Adam Karczmarz, Piotr Sankowski
Algebraic techniques have had an important impact on graph algorithms so far. Porting them, e.g., the matrix inverse, into the dynamic regime improved best-known bounds for various…
Subquadratic Dynamic Path Reporting in Directed Graphs Against an Adaptive Adversary
Adam Karczmarz, Anish Mukherjee, Piotr Sankowski
We study reachability and shortest paths problems in dynamic directed graphs. Whereas algebraic dynamic data structures supporting edge updates and reachability/distance queries ha…
Optimal Decremental Connectivity in Non-Sparse Graphs
Anders Aaman, Adam Karczmarz, Jakub Łącki +3
We present a dynamic algorithm for maintaining the connected and 2-edge-connected components in an undirected graph subject to edge deletions. The algorithm is Monte-Carlo randomiz…
Improved Strongly Polynomial Algorithms for Deterministic MDPs, 2VPI Feasibility, and Discounted All-Pairs Shortest Paths
Adam Karczmarz
We revisit the problem of finding optimal strategies for deterministic Markov Decision Processes (DMDPs), and a closely related problem of testing feasibility of systems of lin…
Improved Feature Importance Computations for Tree Models: Shapley vs. Banzhaf
Adam Karczmarz, Anish Mukherjee, Piotr Sankowski +1
Shapley values are one of the main tools used to explain predictions of tree ensemble models. The main alternative to Shapley values are Banzhaf values that have not been understoo…
Fully Dynamic Algorithms for Minimum Weight Cycle and Related Problems
Adam Karczmarz
We consider the directed minimum weight cycle problem in the fully dynamic setting. To the best of our knowledge, so far no fully dynamic algorithms have been designed specifically…
Sublinear Average-Case Shortest Paths in Weighted Unit-Disk Graphs
Adam Karczmarz, Jakub Pawlewicz, Piotr Sankowski
We consider the problem of computing shortest paths in weighted unit-disk graphs in constant dimension . Although the single-source and all-pairs variants of this problem are we…
Decomposable Submodular Function Minimization via Maximum Flow
Kyriakos Axiotis, Adam Karczmarz, Anish Mukherjee +2
This paper bridges discrete and continuous optimization approaches for decomposable submodular function minimization, in both the standard and parametric settings. We provide impro…
Planar Reachability Under Single Vertex or Edge Failures
Giuseppe F. Italiano, Adam Karczmarz, Nikos Parotsidis
In this paper we present an efficient reachability oracle under single-edge or single-vertex failures for planar directed graphs. Specifically, we show that a planar digraph ca…
A Deterministic Parallel APSP Algorithm and its Applications
Adam Karczmarz, Piotr Sankowski
In this paper we show a deterministic parallel all-pairs shortest paths algorithm for real-weighted directed graphs. The algorithm has work and $\tilde{O}(d…
Min-Cost Flow in Unit-Capacity Planar Graphs
Adam Karczmarz, Piotr Sankowski
In this paper we give an time algorithm for computing min-cost flow (or min-cost circulation) in unit capacity planar multigraphs where edge costs…
Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
Adam Karczmarz, Jakub Łącki
We give new partially-dynamic algorithms for the all-pairs shortest paths problem in weighted directed graphs. Most importantly, we give a new deterministic incremental algorithm f…