Papers for

software engineers working on graph algorithms

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Combinatorial algorithms face limits in dynamic max flow updates

A Note on the Hardness of Partially Dynamic Max Flow

Abstract: We study the fine-grained complexity of partially dynamic max flow in capacitated graphs. Assuming the combinatorial 4-clique hypothesis, combinatorial algorithms require $Ω(n^{2-o(1)})$ amortized update time. Thus, recomputing max flow after each update is optimal up to subpolynomial factors for combinatorial algorithms in dense graphs. The previous conditional lower bound was $Ω(n^{1-o(1)})$ amortized update time under SETH or the OMv hypothesis and applies to all algorithms [Dah16].

Fri 6 NovData Structures and Algorithms
The gist
Finding the maximum flow in a network is important for things like traffic or data routing. The authors studied how quickly algorithms can update these max flow values when the network changes a bit over time. They found a mathematical reason that certain types of algorithms can’t do this updating much faster than just recalculating from scratch in dense networks. This means efforts to speed up these updates for these algorithms likely won’t improve beyond a certain point.
Open → 2611.10181v1

Safe hypergraph shrinking methods keep best solutions intact

Safe Hypergraph Contraction via Capacity-Aware Repair Certificates

Abstract: Multilevel partitioners shrink circuit hypergraphs through vertex contractions, yet a contraction that satisfies block capacity can still eliminate every optimal balanced bipartition. We develop certified safe coarsening (CSC) to identify contractions that preserve an optimum without computing that optimum. CSC certifies a repair for any feasible partition that splits a candidate group: the repair must respect the fixed block capacities and must not increase the cut-net objective. Its bounds exclude hyperedges that capacity constraints force to be cut. A pair certificate checks individual merges, while a directed minimum-cut test certifies groups whose savings emerge only when vertices move together. We prove that certified disjoint batches and successive rounds with recertification retain at least one globally optimal feasible partition for hypergraphs with positive integer vertex and net weights. Experiments on exactly solvable instances confirm optimum preservation for every tested configuration; integration with KaHyPar lowers the sum of per-instance best cuts on circuit benchmarks, with additional runtime.

Thu 1 OctData Structures and Algorithms
The gist
Finding the best way to split complex circuits into parts is tricky, especially when trying to simplify the problem by grouping parts together. The authors developed a way to safely combine parts without accidentally losing the best possible split. Their method checks if the merging keeps the optimal solution feasible by verifying certain safety conditions. Tests show this approach works well on circuits and helps find better splits overall.
Open → 2610.01678v1

Compact constraints improve graph search efficiency without huge size increase

Compact Partial Symmetry Breaking for Graph Search Problems

Abstract: Symmetry breaking in graph search problems remains challenging: complete symmetry breaking constraints are typically exponential in size, while partial approaches trade precision for scalability. We introduce a strength-driven, redundancy-aware methodology for constructing compact partial symmetry breaking constraints based on graph patterns. Each pattern corresponds to a Boolean clause over equality literals and can be integrated directly into CP or SAT models. Our approach incrementally selects strong, non-redundant graph patterns, yielding partial symmetry breaks that achieve substantial pruning of non-canonical graphs while remaining compact in size. This provides a principled framework for deriving lightweight partial symmetry breaking constraints which are significantly more precise than all published state-of-the-art alternatives. We evaluate the proposed constraints on graph instances with up to 25 vertices using a redundancy ratio metric. The resulting partial symmetry breaks constitute only a small fraction of the size of complete symmetry breaking constraints, while delivering significant performance improvements across several graph search benchmarks compared to previously defined partial symmetry breaking methods.

Fri 18 SeptLogic in Computer Science
The gist
Graph search problems become very slow when many symmetrical solutions exist, and fully removing these symmetries is often too large to handle. The authors introduced a method that picks important patterns to break symmetries partially but effectively, keeping the problem size small. Their approach finds a good balance between cutting down redundant solutions and keeping the constraints manageable. Tests showed their method works better than previous partial symmetry breaking techniques on graphs up to 25 nodes.
Open → 2609.21555v1