Can We Break Fine-Grained and NP-Hardness Barriers if We've Seen the Graph Before? The Isomorphic-Priors Model

1 Introduction

• Preprocessing receives prior graphs and their exact optimal values; each query must return the exact value for an isomorphic prior or report that none is isomorphic.Isomorphisms must preserve graph attributes such as weights, and the model also allows an algorithm to return the correct value for a query that matches no prior.Source: §1 · pp. 4–5

1.1 Our Results

• For NP-hard path problems, deterministic algorithms use eO(km) preprocessing and eO(m) query time; spanning-tree variants use randomized eO(kn^ω) preprocessing and eO(n^ω) query time.The results cover Constrained Shortest Path, ℓp-Shortest Path, Constrained Spanning Tree, and ℓp-Spanning Tree; the randomized algorithms are correct with high probability.Source: §1.1 · p. 5
• Replacement Path has deterministic eO(km) preprocessing and eO(m) query time, while Negative Triangle has randomized eO(kn^ω) preprocessing and eO(n^ω) query time.The paper also reports near-linear preprocessing and query times for Maximum Flow.Source: §1.1 · p. 6
• Parity, Mean Payoff, Energy, and Simple Stochastic Games have deterministic eO(km) preprocessing and eO(m) query time; the result extends to value-determined games.These games remain an open question for polynomial-time algorithms in the standard setting.Source: §1.1 · p. 6
• Unless GI is in P, polynomial preprocessing and query times are impossible for the listed NP-hard problems, even with one prior; the list includes almost all of Karp’s 21 problems and (2 − ϵ)-approximate k-Center.Unless GI is in coMA, the lower bounds also hold with unbounded preprocessing when queries use a polynomial-size data structure.Source: §1.1 · pp. 6–7
• The paper’s lower-bound method requires isomorphism-preserving reductions, and adapting classical reductions that lack this property remains an open research direction.The paper notes that some standard reductions preserve isomorphism, while others, including SAT-to-3-SAT, do not.Source: §1.1 · p. 7

1.2 Organization

• The paper introduces the model and notation, develops algorithms using randomized polynomial evaluation and Weisfeiler-Leman techniques, presents lower bounds, and concludes with proofs and further hypotheses.Additional WL-based algorithmic results and lower bounds appear in appendices A and B.Source: §1.2 · p. 8

2.1 Algorithms via Randomized Polynomial Evaluation (Details in Section 6)

• Randomized polynomial evaluation gives Negative Triangle an O~(n^ω) query and supports Constrained Spanning Tree through determinant evaluation and witness reconstruction.For Negative Triangle, evaluating the triangle polynomial at a shared random point gives an invariant for matching prior graphs, with high-probability correctness. For CST, the spanning-tree polynomial is evaluated via the Matrix Tree Theorem; an optimal tree can be reconstructed by matroid intersection in O~(m√n) time.Source: §2.1 · p. 9

2.2 Algorithms via Weisfeiler-Leman (WL) Coloring (Details in Sections 7 and 8)

• WL-equivalent graphs have the same exact optimum for Constrained Shortest Path, enabling near-linear queries; related methods cover other path problems, games, and CST.A WL-equivalent graph has the same color counts, which lets the algorithm transfer walks step by step and reconstruct an optimal path. CST also admits deterministic O(n^3 log n) query time via 2-WL.Source: §2.2 · p. 10

2.3 Lower Bounds (Details in Section 9)

• Isomorphism-preserving reductions transfer conditional lower bounds: a polynomial-time single-prior algorithm for Maximum Independent Set would imply GI is in P.The reduction encodes candidate vertex correspondences as vertices of a graph whose maximum independent set has size |V(G)| exactly when G and H are isomorphic.Source: §2.3 · p. 12
• The overview addresses the non-isomorphism-preserving SAT-to-3-SAT reduction by routing through graph coloring to obtain an isomorphism-preserving chain.The chain uses Karp’s SAT-to-Coloring reduction, Lovász’s Coloring-to-3-Coloring reduction, and a standard mapping from 3-Coloring to 3-SAT.Source: §2.3 · pp. 12–13

Fine-Grained Complexity

• Can Negative Triangle’s randomized bounds be made deterministic or near-linear, and do classical fine-grained equivalences and lower bounds extend to isomorphic priors?The current algorithm uses randomness for eO(kn^ω) preprocessing and eO(n^ω) query time; the standard weighted APSP-equivalent problems may require isomorphism-preserving reductions, as may barriers based on OV, Hitting Set, and combinatorial Triangle Detection.Source: §3 · p. 13

Isomorphic-Priors k-Clique Hypothesis

• The Isomorphic-Priors k-Clique Hypothesis posits no O(n^(ωk/3−ϵ))-time preprocessing and query algorithm with O(1) priors, implying GI ∉ P.An important open direction is to refute the hypothesis or establish it under more standard complexity assumptions.Source: §3 · p. 13

Approximability

• Can isomorphic priors achieve approximation guarantees such as 0.876 for Max 3-SAT, 0.879 for MaxCut, 1.99 for Vertex Cover, or 4/3 for metric TSP?The open questions also include 1.385 for Steiner Tree and n^0.99 for Max Clique, and whether PCP constructions and gap-preserving reductions can establish classical inapproximability bounds while preserving required isomorphisms.Source: §3 · pp. 13–14

Beyond Exact Isomorphism

• Can answers transfer approximately between graphs with similar representations, or exactly through structural relations beyond isomorphism?Possible directions include distances between Weisfeiler–Leman histograms for perturbed graphs, and weight-preserving homomorphisms for Negative Triangle, whose direction transfers positive versus negative answers; useful guarantees may require instance restrictions or controlled relaxations.Source: §3 · p. 14

Isomorphism-Preserving Algorithms

• Can basic constructions such as spanning-tree selection be made efficiently consistent across isomorphic inputs, and how does that complexity relate to graph canonization?The same question applies to shortest paths, minimum cuts, maximal and maximum matchings, and Δ+1 coloring.Source: §3 · p. 14

Beyond NP; More Concrete Problems

• Which problems beyond NP, including exact counting and games, admit polynomial preprocessing and query times with isomorphic priors?Examples raised include PSPACE- and NEXPTIME-complete NFA universality variants, makespan scheduling, Rabin games [MST24], global minimum vertex cuts [CMT26], and generalized Büchi games.Source: §3 · pp. 15–16

The Power of Invariant Representations; Characterizing Tractability

• Do invariant representations characterize tractability with priors, and which graph attributes or structural properties explain when classically hard problems become tractable?The section asks whether joint use of priors can exceed graph-only representations, whether unweighted NP-hard problems or all pseudopolynomial-time problems admit polynomial preprocessing and queries, and whether weakly NP-hard problems can remain conditionally hard.Source: §3 · p. 15

From Values to Solutions

• Can efficient value-retrieval algorithms generally be turned into solution-reconstruction algorithms when optimal witnesses accompany the priors?Decision-to-search reductions may generate instances not isomorphic to any prior, so the section asks which witness or representation properties enable reconstruction and whether value retrieval and solution reconstruction can differ in complexity.Source: §3 · p. 15

A Possible Connection to Graph Machine Learning

• If an isomorphism-invariant function is hard in this model, no invariant learner can jointly guarantee polynomial efficiency, exact training fit, and sound correct-or-abstain predictions for every training set.For TSP, assuming GI is not in P, this rules out such a learner; the guarantees must be relaxed, for example by allowing errors or requiring guarantees only with high probability on sampled training sets.Source: §4 · pp. 16–17
• Invariant-representation algorithms for CSP and Energy Game meet the abstract predictor requirements and transfer answers to non-isomorphic graphs with matching representations.These constructions do not establish that a particular neural architecture can represent or learn the predictors.Source: §4 · p. 17

Beyond Worst-Case Analysis

• Unlike average-case, smoothed, instance-optimal, or prediction-guided frameworks, isomorphic priors preprocess prior data without distributional assumptions or prediction oracles.The model asks whether existing lower bounds can be bypassed for graphs structurally equivalent to previously seen graphs.Source: §4 · p. 17

Graph Isomorphism (GI)

• GI testing yields O(k · T(n, m)) query time, while canonization reduces query time to O(T(n, m)) with O(k · T(n, m)) preprocessing; general-graph polynomial-time GI remains open.Babai’s algorithm gives quasipolynomial time, and polynomial-time GI algorithms are known for several restricted graph classes; beating O(n^3) for Negative Triangle via canonization would require O(n^(3−ε)) time.Source: §4 · pp. 17–18

Weisfeiler-Leman (WL) Color Refinement

• Weisfeiler-Leman invariants can be refined for near-linear algorithms in this model, extending their use beyond existing LP-based links to efficient problems.The paper presents this as a way to leverage a well-known technique to bypass traditional worst-case computational barriers.Source: §4 · p. 18
• Prior WL work establishes inexpressibility and inapproximability limits [AD19] [GGR24], while 2-WL subsumes adjacency-matrix spectral information used for the paper’s deterministic spanning-tree algorithms.The paper also situates its discussion alongside work connecting WL to homomorphism and subgraph counts and to GNN expressiveness [GRS22] [LB24] [CN25].Source: §4 · pp. 18–19

5.1 Preliminary: Attributed Graphs and Isomorphism

• Graph instances may carry vertex and edge attributes, and isomorphisms preserve adjacency and attributes; the problems considered preserve decision answers or optimal values under isomorphism.Source: §5.1 · p. 19

5.2 The Isomorphic-Priors Model

• Preprocessing stores exact solutions for prior graphs; a query returns the solution for an isomorphic prior, or solves H exactly or reports that no prior is isomorphic to it.Prior graphs share fixed vertex and edge counts and global parameters; if an explicit optimal solution is stored, the algorithm can reconstruct and output it for the query graph.Source: §5.2 · p. 20

5.3 Our Focused Approach: Invariant Representations

• An efficiently computable signature invariant under isomorphism and solution-preserving yields O(k·T(n)) preprocessing and O(T(n)) query time.The signature is stored with each prior graph’s optimal value; a trie supports matching query signatures.Source: §5.3 · pp. 20–21
• The applications’ signatures can reconstruct optimal solutions, while randomized signatures may preserve solutions only with high probability.Source: §5.3 · p. 21

6.1 Negative Triangle

• Negative Triangle takes eO(k · n^ω) preprocessing and eO(n^ω) query time with high probability in this model.If each prior containing a negative triangle supplies its three edge weights, the algorithm can also find such a triangle in the query graph in eO(n^ω) time with high probability.Source: §6 · p. 21, §6.1 · p. 24

6.2 Constrained Spanning Tree

• For NP-complete Constrained Spanning Tree, the model gives eO(k · n^ω) preprocessing and eO(n^ω) query time with high probability.If each prior supplies its multiset of cost-distance pairs, the algorithm can also output the corresponding spanning tree in the query graph in eO(n^ω) time with high probability.Source: §6 · pp. 21–22, §6.2 · p. 24
• The stated success probability is at least 1 − k^-1 n^-log(n), which the passage describes as high probability with respect to query size n.The supplied passage begins mid-bound; the expression is rendered from its text as provided.Source: §6.2 · p. 26
• An optimal spanning tree in H is reconstructed by matroid intersection between a graphic matroid and a partition matroid enforcing the prior tree’s cost-distance-pair multiplicities.Classical algorithms give polynomial time, with a stated eO(m√n) running time from recent algorithms.Source: §6.2 · p. 26

7.1 Constrained Shortest Path and Energy Game

• CSP is solvable with O(k(n + m) log n) preprocessing and O((n + m) log n) query time.If each prior also includes an optimal path, the query algorithm can return an optimal path within the same query time.Source: §7.1 · p. 27
• Energy Game is solvable with O(k(n + m) log n) preprocessing and O((n + m) log n) query time.If each winning prior has a memoryless winning strategy from every starting vertex, the algorithm also returns a memoryless optimal strategy for the query in the same time.Source: §7.1 · p. 28

7.2 Preliminaries: The Weisfeiler–Leman Algorithm

• 1-WL iteratively refines vertex colors using neighboring colors and edge attributes, and matching stable colors preserves neighborhoods and lifts walks between equivalent graphs.The lifted walk preserves the stable colors of corresponding vertices and the attributes of corresponding edges.Source: §7.2 · p. 29
• With canonical integer color identifiers, 1-WL runs in O((|V(G)| + |E(G)|) log |V(G)|) time.These identifiers avoid the exponentially growing string representations that arise from directly nesting multisets as colors.Source: §7.2 · p. 30

Appendix A), this gives a Invariant and Solution-Preserving Signature.

• A complete 1-WL invariant can be computed in O((|V| + |E|) log |V|) time and is equal exactly for 1-WL-equivalent graphs.The signature encodes each color class’s size and vertex attribute, plus nonzero edge counts by endpoint colors and edge attribute.Source: Appendix A · p. 30

7.3 1-WL Equivalence Implies Equal Optimality

• 1-WL-equivalent Constrained Shortest Path instances have equal optimal values, while equivalent Energy Game instances preserve Player 1’s winning status at the same initial energy.For Energy Games, the theorem applies to instances with corresponding designated initial vertices.Source: §7.3 · p. 31

7.4 Proof of Theorems 7.2 and 7.4

• For Constrained Shortest Path, preprocessing and query lookup take O((n + m) log n) time, and a stored optimal path can be reconstructed for the query graph.The algorithm stores each prior graph’s signature and optimal value; matching signatures return that value, while a missing signature certifies the query is not isomorphic to a prior. Path reconstruction follows matching edge attributes and stable colors, then removes cycles.Source: §7.4 · p. 32
• For Energy Game strategy reconstruction, a stored optimal memoryless strategy can be made color-consistent in O(n + m), enabling an optimal query strategy in O((n + m) log n).The reconstructed strategy uses matching stable colors and edge weights, with neighborhood preservation supplying corresponding moves.Source: §7.4 · p. 33

8 More on Weisfeiler-Leman (Advanced Arguments)

• The section presents ℓ-WL as a general strategy for fast isomorphic-priors algorithms and shows its limits: some problems in P are not ℓ-WL invariant for any constant ℓ.CSP and CST illustrate the strategy through 1-WL and 2-WL invariance, respectively.Source: §8 · p. 34

8.1 The Weisfeiler-Leman Algorithm

• ℓ-WL provides complete graph-equivalence signatures computable in O(n^(ℓ+1) log n) time, with higher dimensions more expressive and computationally more expensive.The algorithm colors ℓ-tuples of vertices; its complete invariant has matching equivalence exactly when two graphs receive the same signature.Source: §8 · p. 34, §8.1 · p. 35

8.2 ℓ-WL Invariant Functions are in the Isomorphic-Priors Model

• If an optimization problem is ℓ-WL invariant, it admits an isomorphic-priors algorithm with O(kn^(ℓ+1) log n) preprocessing and O(n^(ℓ+1) log n) query time.For 1-WL-invariant problems, the bounds are O(k(n + m) log n) preprocessing and O((n + m) log n) query time. A witness function whose feasibility check is ℓ-WL invariant suffices to prove optimum-value invariance; general theorems do not guarantee reconstructing an optimal solution.Source: §8.2 · pp. 35–36

8.3 CSP is 1-WL Invariant

• CSP is 1-WL invariant and admits isomorphic-priors algorithms with O(k(n + m) log n) preprocessing and O((n + m) log n) query time.The proof uses a witness based on counts of homomorphisms from colored paths; the input graphs must have the same length constraint B to be 1-WL equivalent.Source: §8.3 · pp. 36, 38

8.4 CST is 2-WL Invariant

• CST is 2-WL invariant, yielding a deterministic isomorphic-priors algorithm with O(kn^3 log n) preprocessing and O(n^3 log n) query time.The equivalence condition requires the two input graphs to have the same budget B.Source: §8.2 · p. 35, §8.4 · p. 38
• CST admits O(kn^3 log n) preprocessing and O(n^3 log n) query time for k prior instances of size at most n.The result follows from a witness function whose check function is 2-WL invariant.Source: §8.4 · pp. 39–40

8.5 Examples when Weisfeiler-Leman Fails

• A polynomial-time, isomorphism-invariant CFI decision problem is not ℓ-WL invariant for any ℓ, with Θ(ℓ)-size graphs that ℓ-WL cannot distinguish but the problem separates.This shows the Weisfeiler-Leman approach can fail even for problems solvable in polynomial time within the Isomorphic-Priors model.Source: §8.5 · pp. 41–42
• The CFI parity encoding also implies that solving linear equations over F2 is not ℓ-WL invariant for any ℓ [DGH+13].The passage identifies this as another polynomial-time problem that Weisfeiler-Leman cannot capture.Source: §8.5 · p. 42

9 Conditional Lower Bounds

• Unless GI is in P, every problem in H lacks polynomial preprocessing and query time in the model, even with one prior instance.H includes the decision problems listed in the section; the theorem measures polynomial time in n with k fixed.Source: §9 · p. 43
• Unless GI is in coMA, every problem in H lacks a polynomial-size data structure with polynomial query time, even with one prior instance.The same conditional lower bound applies to the problems listed in H.Source: §9 · p. 43
• Assuming some ε > 0 makes Gap-Max-3-SAT1, 1−ε unsolvable in the model, Max-k-Coverage cannot reach 1−1/e+ε′ and k-Median cannot reach 1+2/e−ε′′.Both approximation lower bounds hold with polynomial preprocessing and query time, even with one prior instance.Source: §9 · p. 43
• Under the analogous Gap-Max-3-SAT assumption for polynomial query time, polynomial-size data structures also cannot achieve those Max-k-Coverage or k-Median approximation thresholds.These bounds apply even with one prior instance.Source: §9 · p. 44

9.1 Hardness Results for GI

• Unless GI is in coMA, GI itself has no polynomial-size data structure with polynomial query time in this model, even for one prior instance.The result also holds for randomized data structures whose query is correct with probability 5/6.Source: §9.1 · p. 44

9.2 Iso-Problems and GI-Completeness

• Iso-Π is a promise problem distinguishing an isomorphic copy of a YES-instance from a NO-instance; Iso-GI is GI-complete, and every Iso-Π lies in GI.The input is promised to be in one of the two cases.Source: §9.2 · pp. 45–46

9.3 Isomorphism-Preserving Reductions

• Isomorphism-preserving reductions transfer GI-hardness between Iso-Π problems, and Iso-Π is GI-complete for every Π in H.Such reductions are polynomial-time, preserve YES/NO answers, and map isomorphic instances to isomorphic outputs.Source: §9.3 · pp. 46–47
• The section gives isomorphism-preserving reductions GI→IS and GI→SAT, plus IS→MaxCut using a standard gadget.The MaxCut threshold is chosen so an independent set of size at least k exists exactly when the constructed graph has a cut of at least that size.Source: §9.3 · pp. 48–50

9.4 The Hardness of 3-SAT

• Because Karp’s reduction is not isomorphism-preserving, the paper establishes 3-SAT hardness through Coloring→3-Coloring→3-SAT.Source: §9.4 · p. 50

9.4.1 Lovász’s Reduction for Colorability

• For odd k≥3, Lovász’s L(G,k) is isomorphism-preserving, has size and construction time O(k·(|V(G)|+|E(G)|)), and is 3-colorable exactly when G is k-colorable.Source: §9.4.1 · pp. 51, 53
• Coloring reduces to 3-Coloring via an isomorphism-preserving polynomial-time reduction that handles even k by first adding a universal vertex.Adding the vertex preserves graph isomorphism and makes A(G) (k + 1)-colorable exactly when G is k-colorable.Source: §9.4.1 · p. 54

9.4.2 Reduction from 3-Coloring to 3-SAT

• 3-Coloring reduces to 3-SAT by a polynomial-time isomorphism-preserving many-one reduction.The construction encodes vertex colors and edge constraints in a 3-CNF formula.Source: §9.4.2 · pp. 54–55

9.5 Hardness in the Isomorphism-Priors Model

• If Iso-Π is GI-hard, Π has no polynomial-preprocessing and polynomial-query algorithm with even one prior unless GI ∈ P.The result assumes prior instances have size at most n.Source: §9.5 · p. 56
• Unless GI ∈ coMA, IS, SAT, and MaxCut have no polynomial-size-data-structure algorithms with polynomial query time, even with one prior.The argument applies when GI is isomorphism-preservingly reducible to the problem; the reductions are established for all three problems.Source: §9.5 · pp. 56–57

9.6 Proof of Hardness for Gap-Max-k-Coverage

• For every ε, ε′ ∈ (0, 1/3), the construction gives an isomorphism-preserving reduction from 3CNF to Gap-Max-k-Coverage with gap 1 versus 1 − 1/e + ε′.It uses Feige’s k-prover system for general 3CNF; bounded-occurrence regularization is avoided because it may not preserve isomorphism.Source: §9.6 · pp. 57, 59
• A polynomial-time isomorphism-preserving reduction maps Gap-Max-3-SAT with gap (1, 1−ε) to Gap-Max-k-Coverage with gap (1, 1−1/e+ε′).YES instances map to instances with OPT = 1, while NO instances have OPT at most 1−1/e+ε′.Source: §9.6 · p. 60
• If Gap-Max-k-Coverage with gap (1, 1−1/e+ε) has polynomial preprocessing and query time with one prior, then Gap-Max-3-SAT with gap (1, 1−ε′) does too for every ε′ > 0.The transfer applies the reduction to prior and query formulas before using the assumed coverage algorithm.Source: §9.6 · pp. 60–61
• The same argument applies to polynomial-size data structures and yields the corresponding result for Gap-k-Median.The cited reduction also connects Gap-Max-k-Coverage and Gap-k-Median.Source: §9.6 · p. 61

10.1 Proof of the Main Theorems

• CSP admits eO(km) preprocessing and eO(m) query time, while CST admits randomized eO(kn^ω) preprocessing and eO(n^ω) query time.Source: §10.1 · p. 61
• The extensions to ℓp-Shortest Path and ℓp-Spanning Tree are straightforward generalizations, using walk lifting, which also works in these settings.Source: §10.1 · p. 61
• Replacement Path admits eO(km) preprocessing and eO(m) query time, while Negative Triangle admits randomized eO(kn^ω) preprocessing and eO(n^ω) query time.Source: §10.1 · p. 61
• Energy Game admits eO(km) preprocessing and eO(m) query time; the same result extends to Parity Game, Mean Payoff Game, Simple Stochastic Game, and value-determined games.Source: §10.1 · p. 61
• Theorem 1.4 follows directly from Theorems 9.3 and 9.4, with approximation results following from the corresponding gap results.Source: §10.1 · p. 61

10.2 k-Clique Hypothesis and Consequence

• Under the Isomorphic-Priors k-Clique Hypothesis, Graph Isomorphism is not polynomial-time solvable; this implication holds under weaker variants too.The proof sketch shows that a polynomial-time GI algorithm would yield an isomorphic-priors k-Clique algorithm contradicting the hypothesis; refuting it would be an intermediate step toward polynomial-time GI.Source: §10.2 · pp. 61–62

• The section gives the deferred proof of Lemma 7.14 concerning color-consistent strategies for Energy Game.Source: A Further Problems that are Invariant… · p. 70
• Further examples of problems invariant under 1-WL can be solved in near-linear time in the Isomorphic-Priors model.Source: A Further Problems that are Invariant… · p. 70

A.1 Color-Consistent Strategies for Energy Game

• Vertices in the same stable 1-WL color class have the same minimum initial energy required to win, so that energy defines a value for each class.The proof establishes this using the shadow-play argument and Neighborhood Preservation, then assigns each class the value of a representative vertex.Source: §A.1 · p. 70
• For each edge consistent with the original strategy, the proof finds a corresponding edge from a color-class representative with the same weight, yielding an energy-potential inequality that telescopes along plays.The corresponding edge leads to a class D from a representative of class C, with w(u, v) ≥ H(D) − H(C).Source: §A.1 · pp. 70–71
• The constructed strategy bσ is optimal from every starting vertex, has the required consistency property, and is computed in linear time.Source: §A.1 · p. 71

Value-determined games

• With k priors of at most n vertices and m edges, Value-determined Game has O(k(n + m) log n) preprocessing and O((n + m) log n) query time.The algorithm uses 1-WL equivalence to transfer winning strategies from a prior graph to an isomorphic query graph.Source: §A.2 · pp. 72–73
• For a shared Borel objective, 1-WL-equivalent value-determined games have the same winner, enabling the strategy transfer used by the algorithm.Instance-specific information, including the threshold, is encoded in graph attributes; the Borel objective is fixed globally.Source: §A.2 · pp. 71–73

Generalized Büchi games

• Generalized Büchi games with fixed set identifiers fit the value-determined-game framework, but preservation under arbitrary permutations of Büchi sets is not established.The current shadow-play argument does not provide a single globally consistent matching between the sets.Source: §A.2 · p. 73

Rabin games

• Rabin games with fixed pair identifiers also fit the framework, while preservation when pairs may be permuted is not established by the current argument.The obstacle is the lack of a globally consistent correspondence between Rabin pairs that preserves their pairing and component roles.Source: §A.2 · p. 74

Open questions

• Open questions are whether generalized Büchi games with arbitrarily permuted sets admit O(n^2.99) query time and whether similarly permuted Rabin games admit O(poly(n)) query time.Both questions concern the natural notions of isomorphism that allow sets or pairs to be permuted.Source: §A.2 · p. 74

A.3 The Replacement Path Problem

• The output is a vector of shortest-path costs, one for each designated path edge removed from the graph.The instance represents edge costs as edge attributes and assigns each designated path vertex its path index as an attribute, with other vertices assigned 0.Source: §A.3 · pp. 74–75
• For k prior instances with at most n vertices and m edges each, preprocessing takes O(k(n + m) log n) time and queries take O((n + m) log n) time.If each prior includes a set of replacement paths, the algorithm can also compute a set of replacement paths for the query graph within the same query time.Source: §A.3 · pp. 74–75
• Replacement Path has the same optimal replacement-path vector on any two instances that are 1-WL equivalent.The theorem underlies the isomorphic-priors algorithm's ability to transfer the prior solution to an equivalent query instance.Source: §A.3 · p. 75

A.4 Maximum Flow

• O(k(n+m) log n) preprocessing and O((n+m) log n) query time solve Maximum Flow; with a prior maximum flow, the query flow is recovered in the same query time.The near-linear query bound slightly improves on existing worst-case algorithms [CKL+22, vdBCP+23, vdBLL+21, vdBLN+20].Source: §A.4 · pp. 75, 76, 78
• The proof establishes equality between a graph’s maximum-flow value and that of its 1-WL color quotient by transferring flows in both directions.The two transfer lemmas show that a flow in either instance yields one in the other with at least as much value.Source: §A.4 · p. 76
• Graphs equivalent under 1-WL have the same maximum-flow value, since their color-quotient instances coincide.This improves on the result in, which establishes the same value preservation for 2-WL.Source: §A.4 · pp. 75, 78

B.1 Additional Problem Definitions

• 0/1-Integer Linear Programming asks whether Cx = d has a 0/1 solution, with instance isomorphism defined by row and column permutations.The problem is closed under this isomorphism: a solution x corresponds to Q^-1x in the permuted instance.Source: §B.1 · p. 78
• Graph problems include Clique, Clique Cover, Coloring, k-Coloring, Independent Set, and MaxCut, with graph isomorphism preserving k when it is part of the instance.The definitions ask about cliques, edge-clique covers, colorability, independent sets, or cuts meeting a specified size.Source: §B.1 · pp. 78–79
• Set-system problems include 3D-Matching, Exact Cover, and Hitting Set, with isomorphisms given by bijections of the underlying elements and set indices.3D-Matching seeks n pairwise coordinate-disjoint triples; Exact Cover seeks disjoint sets whose union is the universe; Hitting Set seeks a set intersecting each listed set exactly once.Source: §B.1 · p. 79
• Other graph problems include Feedback Arc Set, Feedback Vertex Set, Directed Hamiltonian Cycle, Undirected Hamiltonian Cycle, Vertex-Cover, and k-Center.Their isomorphisms preserve graph structure and, where specified, the threshold k; k-Center also preserves c and the weighted graph.Source: §B.1 · p. 79
• k-Median and Steiner Tree incorporate metric or weighted-graph structure, with isomorphisms preserving distances or edge weights, terminals, and relevant thresholds.k-Median uses facility-client distances satisfying the triangle inequality; Steiner Tree seeks a low-cost subtree containing the specified terminal vertices.Source: §B.1 · pp. 80–81
• SAT, 3-SAT, and Max k-SAT use CNF formulas, with formula isomorphism defined by variable renaming consistent with negation.3-SAT requires exactly three literals per clause, while Max k-SAT returns the maximum number of satisfied clauses.Source: §B.1 · p. 80
• Set Cover and Set Packing are also defined on families of subsets: the former asks for at most k sets covering the universe, and the latter for k mutually disjoint sets.Their instance isomorphisms use bijections on the elements and sets while preserving the stated parameters.Source: §B.1 · pp. 80–81
• TSP and Metric TSP ask for a minimum-length tour in a weighted clique, with Metric TSP additionally requiring edge weights to satisfy the triangle inequality.The definitions specify isomorphism through isomorphism of the underlying graphs.Source: §B.1 · p. 81

B.2 Additional Isomorphism-Preserving Reductions

• The section notes that many reductions are simple modifications of known reductions, and that reductions from can be checked for isomorphism preservation.The cited proof says all reductions in its preceding list follow by this approach.Source: §B.2 · p. 81
• Directed Hamiltonian Cycle reduces isomorphism-preservingly to Undirected Hamiltonian Cycle.The proof says the reductions in the preceding list follow from the corresponding reductions in after checking isomorphism preservation.Source: §B.2 · p. 81
• An independent set of size k corresponds to a vertex cover of size |V(G)| − k, yielding an isomorphism-preserving reduction from IS to VC.Source: §B.2 · p. 82
• A MaxCut instance with threshold k maps to a 2-SAT formula with threshold |E| + k, preserving the cut threshold and isomorphism under variable renaming.A cut of at least k edges satisfies both clauses for each cut edge and one for every other edge; conversely, meeting the formula threshold implies at least k cut edges.Source: §B.2 · p. 82
• Set Cover reduces isomorphism-preservingly to k-Median, using the same bijections on elements and sets to establish output isomorphism.The underlying reduction preserves YES-instances, as shown in.Source: §B.2 · pp. 82–83
• Undirected Hamiltonian Cycle reduces isomorphism-preservingly to Gap-TSP with any fixed c > 1, separating YES costs at most 1 from NO costs at least c.The reduction preserves isomorphism between input graphs and their outputs.Source: §B.2 · p. 83