{"id":"1ce1ade3-ccd5-4cc4-b209-0272a08ad470","arxiv_id":"2607.07627","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper disproves a prior FPT algorithm for PNE in graphical games of bounded treewidth, proves W[1]-hardness, and gives improved algorithms with matching pw-SETH lower bounds for pathwidth and cutwidth.","lead":"This paper corrects a flawed algorithm for finding pure Nash equilibria in graphical games, proves the problem is W[1]-hard parameterized by treewidth, and gives improved algorithms with tight lower bounds for pathwidth and cutwidth. It matters because it resolves a decade-old error and pinpoints the exact fine-grained complexity of a fundamental game-theoretic problem.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified. The paper's three contributions (W[1]-hardness correction, improved combinatorial bounds, conditional lower bounds) are well-supported with detailed proofs. The reader's pw-SETH concern is standard practice, not a correctness risk.","rationale":"The paper makes three distinct, well-supported contributions. The W[1]-hardness reduction is correct and directly refutes [35]. The combinatorial bounds on G_co width are the main technical contribution — the pathwidth proof is fully detailed in Appendix B, and the treewidth proof's switching-leaf mechanism is sound: the key observation that at a join node, an unswitched heavy vertex must have its switching leaf in the other child's subtree (thus bounding its present neighbors from that child to Δ−λ) is correct. The tightness constructions and bramble argument (Theorem 18) are clean. The conditional lower bounds follow standard reduction patterns with correct parameter bookkeeping.\n\nThe reader's concern about pw-SETH is not a load-bearing issue — it is the standard framing for conditional lower bounds in fine-grained complexity, and the paper is explicit about it. The gap between the treewidth upper bound (⌊2Δ/3+1⌋) and the treewidth lower bound (only ⌊Δ/2+1⌋ via pathwidth) is acknowledged as an open question, which is honest rather than a flaw.\n\nI agree with the reader's ACCEPT verdict and HIGH confidence. The paper corrects a flawed result in the literature, provides improved algorithms with matching (conditional) lower bounds, and contributes independently useful combinatorial bounds on graph square width. No verdict adjustment needed.","tokens_in":23650,"tokens_out":3707,"duration_ms":165744,"concrete_test":"Independently verify the join-node width analysis in Theorem 11 by constructing a small explicit example: take Δ=6 (so λ=2), a tree decomposition with a join bag containing tw+1=3 vertices, each heavy in exactly one child with 4 present neighbors from that child and 2 future neighbors from the other (the switching leaf being in the other subtree). Confirm that |B_{i,2}| ≤ ⌊2·6/3+1⌋·(3) = 15 and that the decomposition remains valid (each vertex forgotten exactly once). If the bound fails for this concrete case, the treewidth construction has a gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I examined the paper's central claims carefully and do not find a significant load-bearing concern.\n\n1. W[1]-hardness (Theorem 8): The reduction from Multicolored Clique is sound. The vertex cover of size 3k² is correct — the u-players are the only vertices with edges to the v-players, and the v-players form independent sets with constant payoff matrices. The construction time 2^k · n^{O(1)} is FPT in k. This correctly contradicts [35]'s claim of α^{tw} · |G|^{O(1)}, since with α=2 this would be an FPT algorithm parameterized by treewidth for a W[1]-hard problem.\n\n2. Combinatorial bounds (Theorems 10–13): The pathwidth bound (Theorem 10) has a full validity proof in Appendix B showing each vertex is forgotten exactly once, with a clean contradiction argument. The treewidth bound (Theorem 11) uses the switching-leaf mechanism: at a join node, for an unswitched vertex v heavy in one child, the switching leaf must be in the other child's subtree, bounding |N^⪯_i(v)| ≤ Δ−λ; if not heavy in either child, |N^⪯_i(v)| ≤ 2λ−2. With λ=⌈Δ/3⌉, this gives max(⌊2Δ/3⌋, 2⌈Δ/3⌉−2) = ⌊2Δ/3⌋, matching the claimed bound. The tightness examples (Theorems 16–17) use grid-like constructions with bramble-based lower bounds (Theorem 18, Propositions 21–22), which are correct.\n\n3. Lower bounds (Theorems 23–24): The reductions from CSP to PNE achieve the required pathwidth compression (pw/k + 7) and cutwidth bound (pw + 4), with matching out-degree 2k−1 so that ⌊Δ/2+1⌋ = k. The equivalence in Theorem 2 follows from both directions: pw-SETH false → faster CSP → faster PNE (via Theorem 14), and faster PNE → faster CSP (via Theorems 23–24).\n\nThe reader's weakest_assumption about pw-SETH being unproven is not a correctness concern — conditional lower bounds under standard hypotheses are expected practice in fine-grained complexity, and the paper is transparent about this throughout.","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","summary":"This paper revisits the parameterized complexity of deciding whether a graphical game admits a pure Nash equilibrium (PNE). It makes three contributions: (1) showing that a prior algorithm by Thomas and van Leeuwen [Algorithmica 2015] claiming α^{O(tw)} dependence is flawed, by proving W[1]-hardness parameterized by vertex cover (Theorem 8); (2) improving the natural DP algorithm's parameter dependence from α^{(Δ+1)·tw} to α^{⌊2Δ/3+1⌋·tw}, α^{⌊Δ/2+1⌋·pw}, and α^{ctw} (Theorem 1), via tightened combinatorial bounds on the width of the co-neighbor graph G_co (Theorems 10–13); and (3) showing that the pathwidth and cutwidth algorithms are optimal under the pw-SETH, in the sense that improving them is equivalent to falsifying that hypothesis (Theorem 2, Theorems 23–24).","tokens_in":24019,"tokens_out":2718,"duration_ms":167851,"significance":"The paper makes a valuable contribution on multiple fronts. The correction of the Thomas–van Leeuwen result is important for the field, as the flawed algorithm appears to have been accepted as state of the art. The tightened bounds on tw(G²) and pw(G²) in terms of Δ and the original graph's width (Corollary 4) are of independent combinatorial interest and could find further applications. The conditional lower bounds are notably tight: the paper establishes equivalence (not just implication) with the pw-SETH, which is a clean and strong result. The tightness examples (Theorems 16–17) with the bramble-based lower bound on H_n (Theorem 18, Propositions 21–22) provide concrete evidence that the combinatorial bounds cannot be improved further. The gap between the treewidth and pathwidth constants (2/3 vs. 1/2) is an intriguing open question that the paper honestly flags.","major_comments":[],"minor_comments":[{"comment":"§4.1, Theorem 10: The notation N^⪯_i(v) and N^≻_i(v) is introduced inline but could benefit from a formal definition box or a clearer initial statement, as these objects are used heavily in both Theorems 10 and 11.","section":null},{"comment":"§4.1, Theorem 11: The concept of 'switching leaf' is central to the treewidth construction but is defined somewhat tersely. A brief paragraph explaining the intuition for why a unique leaf of T[v|heavy] can always be selected, and how the switching path interacts with the join node construction, would improve readability.","section":null},{"comment":"Appendix A: The counterexample to [35] is clear and convincing. It might be worth cross-referencing this example in Section 3 (where Theorem 8 is stated) so readers are aware that a concrete counterexample exists in the appendix.","section":null},{"comment":"§5, Theorem 23: The reduction achieves Δ = 2k−1 (odd). The paper notes in §6 that tightening the lower bound for even Δ is open. It would be helpful to briefly state in Theorem 23 itself that the result applies only to odd Δ, for precision.","section":null},{"comment":"§4.3, Theorem 16: The pathwidth lower bound argument relies on G²_{k,p} containing an n×n grid as a subgraph. The justification is given in two sentences; a slightly more detailed explanation of why the pivot vertex connections guarantee the grid minor/subgraph would strengthen the proof.","section":null},{"comment":"References: [27] (Lampis, SODA 2025) and [28] (Lampis, SODA 2026) are both by one of the authors. This is appropriately disclosed through standard citation, but the authors may wish to explicitly note that the pw-SETH was introduced by one of them in §1 (Other related work) for full transparency.","section":null}],"recommendation":"accept","confidential_remarks":"The pw-SETH was introduced by Lampis (one of the authors) in [27], which underpins the lower bounds. This is standard practice in fine-grained complexity, and the paper shows equivalence rather than one-directional implication, which mitigates any circularity concern. The hypothesis has been adopted by multiple independent groups. I do not consider this a conflict of interest or a correctness risk. The paper fits well within the scope of a algorithms/complexity journal."},"author_rebuttal":{"model":"glm-5.2","summary":"We thank the referee for the careful reading and the positive assessment. The referee's summary accurately captures the three main contributions of the paper: (1) the identification of the flaw in the Thomas–van Leeuwen algorithm and the W[1]-hardness result, (2) the improved combinatorial bounds on the width of the co-neighbor graph yielding improved algorithms, and (3) the tight conditional lower bounds under the pw-SETH. The referee raised no major comments requiring revision. We are grateful for the referee's acknowledgment of the independent interest of the combinatorial bounds (Corollary 4), the strength of the equivalence results (Theorem 2), and the tightness examples (Theorems 16–18). We note the referee's interest in the gap between the treewidth and pathwidth constants (2/3 vs. 1/2), which we have flagged as an open question in Section 6. We remain open to any minor editorial suggestions the referee may have.","responses":[],"tokens_in":23233,"tokens_out":217,"duration_ms":19177,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","letter":"Here's the short version: this paper does three things, all of them solid. It shows that a published algorithm of Thomas and van Leeuwen (Algorithmica 2015) is flawed — more strongly, that the problem is W[1]-hard parameterized by treewidth (even vertex cover), so their claimed FPT algorithm would collapse FPT to W[1]. It gives improved algorithms for PNE in graphical games, tightening the parameter dependence from α^{(Δ+1)·tw} to α^{⌊2Δ/3+1⌋·tw}, α^{⌊Δ/2+1⌋·pw}, and α^{ctw}. And it proves matching lower bounds for the pathwidth and cutwidth cases under the pw-SETH, showing the improvements are equivalent to falsifying that hypothesis. The combinatorial bound on tw(G²) and pw(G²) (Theorem 3, Corollary 4) is independently useful and, by the authors' account, the first improvement over the standard (Δ+1)·tw bound that has been used across many papers. The W[1]-hardness reduction from Multicolored Clique is standard and explicit. The vertex cover of size 3k² is correct, and with α=2 the contradiction with [35] is immediate. The combinatorial proofs (Theorems 10–13) are constructive with detailed validity and width arguments. The tightness examples use grid-like constructions with bramble-based lower bounds (Theorem 18, Propositions 21–22), which check out. The switching-leaf mechanism for the treewidth bound is the most intricate part; the argument that each vertex is forgotten exactly once via the contradiction in Claim 12 is sound. The pw-SETH lower bounds (Theorems 23–24) achieve the required pathwidth compression and cutwidth bounds with matching out-degree, and the equivalence in Theorem 2 goes both directions. The reader's concern about pw-SETH being unproven is not a correctness issue — conditional lower bounds under standard hypotheses are expected practice, and the paper is transparent throughout. The one genuine gap is the treewidth lower bound not matching the algorithmic upper bound, which the authors acknowledge as open. This is not a flaw; it is an honest open question. The gap between the 1/2 and 2/3 constants for pathwidth vs. treewidth is genuinely intriguing given how rarely these parameters differ. I agree with the reader's assessment and the stress-test note: no significant load-bearing concern. This paper is for researchers in parameterized complexity and algorithmic game theory. The graph square width bounds alone justify attention from the graph algorithms community. It deserves a serious referee.","headline":"Corrects a standing error in the literature, gives improved algorithms with matching lower bounds, and proves a tight combinatorial bound on graph square widths. The W[1]-hardness result disproving Thomas-van Leeuwen is clean and important.","tokens_in":24925,"tokens_out":659,"would_cite":true,"duration_ms":94090,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"PNE in Graphical Games: Better Algorithms, Corrected Hardness","keywords":[],"falsifier":"If the pw-SETH is false (i.e., SAT parameterized by pathwidth can be solved in (2−ε)^pw time), then the optimality of the pathwidth and cutwidth PNE algorithms collapses, and the equivalence in Theorem 2 becomes vacuous.","tokens_in":23900,"feed_emoji":"🎮","tokens_out":1017,"duration_ms":115111,"temperature":0.7,"pith_summary":"This paper revisits the complexity of deciding whether a graphical game admits a pure Nash equilibrium (PNE), parameterized by graph width measures (treewidth, pathwidth, cutwidth) and maximum degree Δ. The authors make three main contributions. First, they identify a flaw in a prior algorithm that claimed to remove the exponential dependence on Δ from the treewidth-based running time; they prove the problem is W[1]-hard parameterized by treewidth, so no such algorithm can exist unless FPT = W[1]. Second, they improve the natural dynamic programming dependence from α^((Δ+1)·tw) to α^(⌊2Δ/3+1⌋·tw), α^(⌊Δ/2+1⌋·pw), and α^(ctw), by tightening a combinatorial bound relating the width of a graph G, its maximum degree, and the width of its square G² (or co-neighbor graph G_co). Third, they show the pathwidth and cutwidth algorithms are likely optimal: improving them is equivalent to falsifying the pw-SETH, a standard fine-grained complexity hypothesis. The central technical object is the co-neighbor graph G_co of the game graph, whose width controls the CSP encoding's complexity; the key mechanism is a refined decomposition that avoids adding all out-neighbors of every vertex to every bag, instead tracking only a minority subset and inserting bags at transition points.","feed_headline":"Graph square bound sharpens Nash equilibrium search","feed_subtitle":"Correcting a decade-old flawed algorithm, the work cuts the exponent by a constant factor and proves the result is likely optimal.","key_machinery":"The co-neighbor graph G_co of the game digraph, whose width determines CSP-solving cost; a refined tree/path decomposition of G_co that tracks 'present' vs 'future' out-neighbors of each vertex and inserts bags at the transition ('switching leaf' for treewidth, 'becoming heavy' for pathwidth), saving a constant fraction of neighbors per bag.","core_discovery":"The standard bound tw(G²) ≤ (Δ+1)·tw(G) is not tight. By carefully splitting each vertex's out-neighborhood into present and future portions and inserting bags at the transition point where a vertex becomes 'heavy', one can achieve tw(G_co) ≤ ⌊2Δ/3+1⌋·tw(G) and pw(G_co) ≤ ⌊Δ/2+1⌋·pw(G), yielding constant-factor improvements in the exponent of PNE algorithms. These bounds are shown to be tight for both pathwidth and treewidth via explicit graph families, and the resulting algorithms for pathwidth and cutwidth are optimal under the pw-SETH. Simultaneously, the problem is W[1]-hard parameterized by treewidth (even vertex cover) when α = 2, refuting a prior claimed FPT algorithm.","pith_inferences":[],"forward_implications":["Any algorithm for PNE in graphical games parameterized by treewidth with running time α^(f(Δ)·tw) must have f(Δ) = Ω(Δ) unless W[1] = FPT, settling the parameterized complexity landscape for this problem.","The tightened width bounds on graph squares (Corollary 4) apply to any problem whose complexity depends on tw(G²) or pw(G²), potentially improving algorithms for graph coloring, distance labeling, and related problems beyond game theory.","The gap between the treewidth constant (2Δ/3) and pathwidth constant (Δ/2) is unusual—most graph problems have identical complexity for these two parameters—suggesting PNE computation may be a natural problem that genuinely distinguishes treewidth from pathwidth.","The equivalence between improving the PNE algorithms and falsifying the pw-SETH means this problem serves as a complete problem for the pw-SETH at these parameter regimes, making it a useful reduction target for future lower bounds."],"fun_headline_variants":["Prior PNE algorithm proven flawed; new tighter width bounds found","New graph square bounds improve pure Nash equilibrium search","Optimal pathwidth and cutwidth bounds for Nash equilibrium search","Fine-grained complexity of Nash equilibria refutes prior FPT claims","Tighter graph width bounds for pure Nash equilibrium search"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The optimality claims for the pathwidth and cutwidth algorithms rely on the pw-SETH, which asserts that the standard dynamic programming algorithm for SAT parameterized by pathwidth cannot be improved from 2^pw to (2−ε)^pw. This is an unproven complexity hypothesis stronger than P ≠ NP; if it fails, the claimed lower bounds collapse.","fun_headline_variants_meta":{"raw":{"variants":["Prior PNE algorithm proven flawed; new tighter width bounds found","New graph square bounds improve pure Nash equilibrium search","Optimal pathwidth and cutwidth bounds for Nash equilibrium search","Fine-grained complexity of Nash equilibria refutes prior FPT claims","Tighter graph width bounds for pure Nash equilibrium search","W[1]-hardness restricts PNE algorithms; new optimal bounds established"]},"model":"glm-5.2","effort":"high","cost_usd":0.0,"raw_usage":{"total_tokens":1776,"prompt_tokens":698,"completion_tokens":1078,"prompt_tokens_details":null},"tokens_in":698,"tokens_out":1078,"duration_ms":66430,"temperature":1.0,"reasoning_tokens":941,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-09T04:30:25.839212+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"If the pw-SETH is false (i.e., SAT parameterized by pathwidth can be solved in (2−ε)^pw time), then the optimality of the pathwidth and cutwidth PNE algorithms collapses, and the equivalence in Theorem 2 becomes vacuous.","supporting_citations":[],"review_version":1}