{"id":"265acf6a-34c1-40e3-a457-5278f3853dde","arxiv_id":"1908.08938","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A new NP-completeness result for 2-stack 1-queue layouts, plus a conflict-minimizing heuristic that beats adapted eLen and ceilFloor on most benchmark graph classes.","lead":"This paper proves that deciding whether a graph can be drawn with two stack pages and one queue page is NP-complete, and it introduces a new heuristic for minimizing crossing and nesting conflicts in mixed linear layouts. The practical result is that the new heuristic often beats existing book-drawing heuristics on random and planar graph classes, though not on all tested instances.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's converse induction is unsupported: Lemma 2 only constrains the unique gadget vertex u, and the proof asserts the same for every neighbor of u without a lemma.","rationale":"The central contribution is the NP-completeness reduction in Theorem 1. The proof is short and leans entirely on Lemma 2. After constructing G', the converse must show that every vertex of G is placed between w1 and w2 and that every edge of G is therefore forced into S1∪S2. The only tool supplied is Lemma 2, which applies to the unique vertex u that carries the gadget edges w1u and w2u. The sentence 'As for u in Lemma 2' attempts to transfer the lemma to each neighbor v of u, but v does not satisfy the lemma's hypotheses. Without a propagation lemma of the form 'if xy is an edge and x lies between w1 and w2, then y also lies between w1 and w2', the induction cannot start. No such lemma is stated or proved in the appendix. This is distinct from the connectivity issue: even for connected G, the first step from u to N(u) is missing. If G is disconnected, other components are never reached. Thus the proof as written does not establish the claimed NP-completeness. The issue is not necessarily about the truth of the theorem; it could well be true and the proof repairable with a new lemma. But a reader cannot verify the central claim from the text. The computer-verified Observations 1-3 are a second dependency; they are less alarming because source code is available, but they do not repair the inductive gap. The experimental contribution is separate and is reasonably reported, with the Delaunay exception discussed in Section 4, although the abstract overstates the heuristic's advantage. Overall, the reader's CONDITIONAL verdict remains appropriate: the paper should be accepted only if the induction step is either proved or the theorem is re-proved with a correct argument.","tokens_in":9033,"tokens_out":15827,"duration_ms":144573,"concrete_test":"Use the authors' exhaustive-search code or an independent SAT/ILP model to test the local propagation claim: take the graph of Lemma 2 and add one extra vertex v plus edge uv; ask whether a conflict-free 2-stack 1-queue layout exists with v placed left of w1 or right of w2. If yes, the claim that every neighbor of u lies between w1 and w2 is false and the reduction's converse fails. If no, the claim is at least empirically true, but the paper should still supply a lemma proving the propagation before the theorem is accepted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The NP-completeness proof of Theorem 1 rests on an unjustified inductive step. In the reduction, the two double-K8 gadgets are attached to a chosen vertex u of G by edges w1u and w2u; Lemma 2 proves only that this distinguished vertex u lies between w1 and w2. The proof then states: 'As for u in Lemma 2, we find that w1≺v≺w2 for every neighbor v∈V of u. By induction we find for all v′∈V that w1≺v′≺w2.' But Lemma 2 cannot be applied to a neighbor v: v is not incident to w1 or w2, and the only new edge is uv. No lemma in the appendix shows that a neighbor of a vertex already known to lie between w1 and w2 must itself lie between them. This is not only a connectivity issue: even for connected G, the step from u to its neighbors is a non sequitur. For disconnected G, the induction obviously does not reach other components, so the converse of the reduction as stated is false unless the reduction is restricted to connected instances. Because this is the exact step that forces all edges of G into the two stacks, the NP-completeness result is not established by the written proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies mixed linear layouts with s stack pages and q queue pages. It claims two complexity results: (1) deciding whether a graph admits a 2-stack 1-queue layout is NP-complete, and (2) a fixed-vertex-order mixed layout recognition problem remains NP-complete under addition of one stack or one queue page. The paper also proposes a new O(m^2) page-assignment heuristic for minimizing crossings and nestings in 1-stack 1-queue layouts, and evaluates it against two adapted book-drawing heuristics on random graphs, Delaunay triangulations, planar bipartite graphs, 2-trees, and 3-trees.","tokens_in":9261,"tokens_out":4559,"duration_ms":44157,"significance":"If the NP-completeness theorem is correctly established, it is a meaningful contribution to the sparse literature on mixed linear layout complexity. The heuristic is, to the authors' knowledge, the first targeted at conflict minimization in mixed 1-stack 1-queue layouts, and the experimental study is careful, with code provided, multiple vertex-order heuristics considered, and six benchmark classes. The reported improvements over adapted book-drawing heuristics on most classes (with Delaunay triangulations as an exception) are plausible and useful. However, the central NP-completeness proof contains a serious unsupported step, and the structural observations used in the reduction are verified only by an undescribed exhaustive search, so the complexity claim is not established as written.","major_comments":[{"comment":"The converse direction contains an unsupported inductive step. Lemma 2 establishes only that the distinguished vertex u lies between w1 and w2 in the constructed gadget. The proof then asserts 'As for u in Lemma 2, we find that w1≺v≺w2 for every neighbor v∈V of u' and proceeds by induction over V. Lemma 2, however, applies only to the special vertex u, which is incident to both w1 and w2; an arbitrary neighbor v of u is not incident to w1 or w2, so the lemma cannot be invoked for v. No lemma in Appendix A supplies a propagation argument showing that a neighbor of a vertex known to lie between w1 and w2 must itself lie between them. Consequently, even for connected G the step from u to its neighbors is a non sequitur, and for disconnected G the induction cannot reach vertices outside the component of u. Because this step is what forces all edges of G into the two stack pages, the NP-completeness proof as written does not establish the result. The authors should either prove a suitable stronger gadget lemma or restrict the reduction to connected graphs and justify the propagation.","section":"Section 2, proof of Theorem 1"},{"comment":"The rigidity properties of K8 and double-K8 layouts that underpin Lemma 2 and hence Theorem 1 are asserted to follow from exhaustive search, with only a link to source code provided. The manuscript does not describe the search space (e.g., whether all vertex orders or all page assignments are enumerated), the pruning rules, or the verification procedure. Since these observations are load-bearing for the NP-completeness reduction, the paper should include a detailed description of the exhaustive search parameters and the exact statements verified, or replace them with human-checkable proofs.","section":"Appendix A, Observations 1-3"}],"minor_comments":[{"comment":"The abstract states experiments 'for the cases, q = 1', which appears to be a typo; it should read 'for the case s, q = 1'.","section":"Abstract and Section 3"},{"comment":"The description of the stack and queue data structures does not specify how the notions 'edges on top of e in S' and 'edges in front of e in Q' are defined when e is removed from an interior position rather than from the top/front. The authors should clarify whether these counts refer to the current state of the data structure after all insertions up to the right endpoint of e, and how removals from interior positions are implemented.","section":"Section 3, algorithm description"},{"comment":"In the second reduction, the claim that 'no edge between vertices of M can be on a queue page' is not justified in the text; the argument should state explicitly that every queue page already contains an edge from some Mi that nests each M-edge.","section":"Section 2, proof of Theorem 2(ii)"},{"comment":"The captions of Figures 4 and 5 do not mention that the vertical axis is 'conflicts per edge'; adding this would improve readability.","section":"Appendix B, Figures 4 and 5"}],"recommendation":"major_revision","confidential_remarks":"The main issue is the induction gap in Theorem 1; this is not a mere presentation issue. If the authors cannot provide a lemma replacing the unsupported step, the paper's central complexity claim collapses. The experimental section is solid and could stand alone, but the complexity result as written is not established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper has two distinct parts that should not be graded together. The heuristic and experimental study are useful and honest; the complexity section has a serious gap that, as written, leaves Theorem 1 unproven.\n\nWhat's new and good: the stack-queue page assignment heuristic is, to my knowledge, the first targeted at mixed 1-stack 1-queue layouts. The idea of keeping crossing and nesting counters while processing vertices in order, and using a look-ahead term (0.5 per active edge) to decide page assignment, is sensible and runs in O(m^2). The experiments compare fairly against adapted eLen and ceilFloor across random graphs, Delaunay triangulations, planar bipartite graphs, and 2/3-trees, and report winners per instance plus error bands. They also report the Delaunay exception honestly, though the abstract overstates the case by omitting it. Theorem 2, the page-addition monotonicity result, is a clean structural observation with a plausible proof.\n\nThe soft spot is Theorem 1. Lemma 2 only establishes that the designated vertex u lies between the two outer vertices w1 and w2, using edges w1u and w2u. The converse direction then asserts, \"As for u in Lemma 2, we find that w1≺v≺w2 for every neighbor v of u,\" and inducts over all of G. But a neighbor v is not incident to w1 or w2, so Lemma 2 cannot be applied to v. No lemma in the appendix supplies that step. This is not merely a connectivity issue; even for connected G, the induction does not follow. Without forcing every vertex of G into the w1–w2 interval, the argument that all edges of G are nested by the two queue edges collapses, and the reduction from 2-stack layout is not established. The result may be true and fixable—perhaps with a stronger gadget or a case analysis—but the written proof does not prove it.\n\nThe exhaustive-search observations for K8 and double-K8 in Appendix A are a lesser worry: code is provided, but the search space and completeness criteria are not documented in the paper. That's a minor fix. The heuristic's 0.5 weight is a free parameter, though the paper does not tune it to make claims, so that is fine.\n\nIf I were editor, I would send it to review: the heuristic work deserves publication, and the complexity result is worth an expert look. But the referee must force a rewrite of Theorem 1's proof. This is a revise-and-resubmit, not a reject.","headline":"The heuristic and experiments are solid and honest, but the main NP-completeness proof has a gap in the induction step that leaves Theorem 1 unproven as written.","tokens_in":9805,"tokens_out":8595,"would_cite":true,"duration_ms":78744,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that recognizing 2-stack 1-queue layouts is NP-complete, settling a mixed linear layout complexity question, and presents a heuristic that reduces conflicts.","keywords":["mixed linear layouts","stack layouts","queue layouts","2-stack 1-queue","NP-completeness","graph drawing","conflict minimization","heuristics"],"falsifier":"Run an independent exhaustive search over all 8! vertex orders and all page assignments of K8 to check Observation 1's claims that v1v3 and v6v8 are always in the queue page and that the longest edges are in the stacks; any counterexample would invalidate Theorem 1's gadget.","tokens_in":8809,"feed_emoji":"📐","tokens_out":6827,"duration_ms":57740,"temperature":0.7,"pith_summary":"The paper proves that deciding whether a graph admits a layout with two stack pages and one queue page is NP-complete, closing the complexity question for a natural mixed layout model. It also shows that NP-completeness is preserved when an extra stack or queue page is added to a fixed-order layout problem. On the algorithmic side, the paper introduces the first heuristic aimed directly at minimizing crossings and nestings in 1-stack 1-queue layouts, using counters to estimate future conflicts. Experiments on random graphs, planar bipartite graphs, and tree-like graphs show the new heuristic matches or outperforms two established book-embedding heuristics adapted to mixed layouts, with Delaunay triangulations as the main exception.","feed_headline":"Recognition of 2-stack 1-queue layouts is NP-complete","feed_subtitle":"A new stack-queue heuristic beats adapted book-embedding methods on most benchmark graphs.","key_machinery":"The argument for NP-completeness rests on a rigid gadget: the double-K8, formed by identifying two vertices of two K8 cliques and adding an edge between two outer vertices. Exhaustive search over all vertex orders establishes three structural observations about 2-stack 1-queue layouts of K8 and double-K8, namely that certain longest edges must lie in the stack pages, certain edges must lie in the queue page, and only the first and last vertices of two copies can interleave. These observations force the input graph's vertices to be placed between the outer vertices of the two gadgets, turning the question of a 2-stack 1-queue layout into the NP-complete question of a 2-stack layout. The heuristic uses a different mechanism: while scanning vertices left to right it inserts edges into tentative stack and queue data structures, keeps a crossing counter and a nesting counter for each edge, and assigns each edge to the page with the lower estimated future conflict cost.","core_discovery":"The central claim is that recognizing 2-stack 1-queue layouts is NP-complete. The proof reduces from the NP-complete 2-stack layout problem by attaching a specially constructed graph to an arbitrary input graph; a gadget built from two copies of K8 (a double-K8) forces any valid layout to confine the input graph's vertices between two outer vertices, so that the input edges must all lie in the stack pages. A second result shows that if a fixed-order s-stack q-queue recognition problem is NP-complete, then adding one more stack or queue page keeps it NP-complete. The paper also claims that its stack-queue page assignment heuristic, which processes vertices left to right and assigns each edge by comparing estimated future crossing and nesting counts, produces fewer or comparable conflicts per edge than the adapted eLen and ceilFloor heuristics on most benchmark graph classes, the exception being larger Delaunay triangulations where ceilFloor is better.","pith_inferences":["Because the exhaustive-search observations are the load-bearing part of the NP-completeness proof, a natural next step is to independently re-verify them with a different search implementation; if any observation is false, Theorem 1 would need a different gadget.","The heuristic's future-conflict estimation could be combined with vertex-order heuristics that specifically reduce nestings, since the authors note that specialized queue-oriented order heuristics are missing.","The exception of Delaunay triangulations suggests that a hybrid algorithm could select between stack-queue and ceilFloor based on graph properties such as average degree or number of triangles.","The fixed-order NP-completeness preservation result means that SAT-based layout tools cannot rely on adding pages to make the page-assignment subproblem tractable."],"forward_implications":["Unless P = NP, there is no polynomial-time algorithm that decides whether a given graph admits a 2-stack 1-queue layout.","The reduction's gadget may generalize to s-stack 1-queue layouts for s > 2 if larger rigid cliques are found, as the authors suggest.","The stack-queue heuristic runs in O(m^2) time, matching eLen and ceilFloor, so it can be used in practice without extra cost.","For random graphs, planar bipartite graphs, and 3-trees, the new heuristic wins on most instances; for Delaunay triangulations, ceilFloor wins on larger instances.","The heuristic can be generalized to arbitrary numbers of stack and queue pages."],"supporting_citations":[{"why":"Supplies the NP-complete 2-stack layout problem used as the reduction source for Theorem 1.","marker":"[1]"},{"why":"Reinforces the reduction source by showing 2-stack layouts are equivalent to subhamiltonian graphs.","marker":"[2]"},{"why":"Provides the stack/queue validation strategy (inserting and removing edges) that the heuristic builds upon.","marker":"[8]"},{"why":"Defines queue layouts and gives the 2n-3 conflict-free edge bound that motivates the benchmark densities.","marker":"[9]"},{"why":"Supplies the book drawing heuristics and vertex order algorithms that are adapted and compared in the experiments.","marker":"[10]"},{"why":"Supplies the eLen page-assignment heuristic baseline.","marker":"[3]"},{"why":"Supplies the ceilFloor page-assignment heuristic baseline.","marker":"[13]"},{"why":"Motivates the 1-stack 1-queue case and the planar bipartite graph conjecture that guides the benchmark selection.","marker":"[12]"}],"fun_headline_variants":["2-stack 1-queue layout recognition is NP-complete","Mixed stack-queue layout recognition is NP-complete","New heuristic reduces conflicts in mixed stack-queue layouts","Stack-queue heuristic beats book-embedding on most graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The NP-completeness proof depends on exhaustive computer search over all vertex orders of K8 and double-K8; if that search is incomplete or incorrectly implemented, the structural observations and the reduction built on them could fail.","fun_headline_variants_meta":{"raw":{"variants":["2-stack 1-queue layout recognition is NP-complete","Mixed stack-queue layout recognition is NP-complete","New heuristic reduces conflicts in mixed stack-queue layouts","Stack-queue heuristic beats book-embedding on most graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001056,"raw_usage":{"total_tokens":4427,"prompt_tokens":938,"completion_tokens":3489,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":554,"completion_tokens_details":{"reasoning_tokens":3421}},"tokens_in":554,"tokens_out":3489,"duration_ms":24428,"temperature":1.0,"reasoning_tokens":3421,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:25:26.638330+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an independent exhaustive search over all 8! vertex orders and all page assignments of K8 to check Observation 1's claims that v1v3 and v6v8 are always in the queue page and that the longest edges are in the stacks; any counterexample would invalidate Theorem 1's gadget.","supporting_citations":[{"cited_title":"Discrete Applied Mathematics 122(1-3), 93–115 (2002)","cited_arxiv_id":null,"evidence_quote":"Supplies the eLen page-assignment heuristic baseline."},{"cited_title":"Memetic Computing 5(4), 255–274 (2013)","cited_arxiv_id":null,"evidence_quote":"Supplies the ceilFloor page-assignment heuristic baseline."},{"cited_title":"In: Frati, F., Ma, K.L","cited_arxiv_id":null,"evidence_quote":"Motivates the 1-stack 1-queue case and the planar bipartite graph conjecture that guides the benchmark selection."}],"review_version":1}