{"id":"0d84438d-345c-44a7-9efb-54a75ccc3c82","arxiv_id":"2506.05156","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Queue Layout Extension is NP-complete with all vertices present, W[1]-hard parameterized by missing elements, FPT when page count is added, and polynomial when only two vertices are missing.","lead":"This paper studies how hard it is to finish a partial queue layout, a linear ordering of a graph's vertices where edges on each page must not wrap around each other. It maps the difficulty of this extension problem under several parameters and shows queue layouts behave differently from stack layouts, which only forbid crossings.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 16's 2-SAT encoding omits totality clauses and its transitivity reduction fails for new vertices that are not endpoints of any new edge, leaving the proof of Theorem 5 incomplete.","rationale":"The reader's weakest assumption identifies the same location: the transitivity claim inside Lemma 16. My independent reading confirms the concern and adds a closely related, equally concrete gap: the formula φ1 as printed does not enforce totality, so the proof's step from a satisfying assignment to a total spine order is unjustified. Both problems are localized to Lemma 16, the polynomial check on which Theorem 5 depends. The central complexity map of the paper may still be correct, and the fixes (adding the 2-CNF totality clauses, and either guessing a total order on all new vertices or handling isolated new vertices separately) appear straightforward and would not change the stated theorem. Therefore the appropriate verdict remains CONDITIONAL: accept only after the proof of Lemma 16 is repaired and the transitivity/totality claims are verified. I do not see reason to escalate to rejection, since the identified issues are proof gaps rather than demonstrated counterexamples to the theorem itself.","tokens_in":26720,"tokens_out":18883,"duration_ms":221248,"concrete_test":"Run the construction of Lemma 16 on the instance with V(H)=∅, Vadd={a,b,c}, and E(G)=∅ (three isolated new vertices, no new edges). The printed φ1 admits the satisfying assignment x_{a,b}=x_{b,c}=x_{c,a}=1, x_{b,a}=x_{c,b}=x_{a,c}=0, which satisfies all four subformulas yet does not correspond to any linear order. This demonstrates that 'exactly one of these cases is true' is false without totality clauses (x_{u,v}∨x_{v,u}). Separately, check whether the authors intend ≺Eadd to be a total order on all of Vadd; if so, the branch bound in Theorem 5 and the definition of Lemma 16 must be updated to say so, and the instance above is then excluded by construction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Lemma 16, the formula φ1 is defined as ⋀_{u≠v} ((x_{u,v}⇒¬x_{v,u}) ∧ (x_{v,u}⇒¬x_{u,v})), which is equivalent to (¬x_{u,v}∨¬x_{v,u}). This enforces antisymmetry but not totality: the assignment x_{u,v}=x_{v,u}=0 satisfies φ1, so the proof's assertion that 'exactly one of these cases is true' when constructing ≺G from a satisfying assignment is false as written. Additionally, the reduction of transitivity clauses to 2-CNF relies on the claim that for every triple u,v,w the relative order of at least two vertices is fixed by ≺H or ≺Eadd. This fails for any new vertex that is not an endpoint of a new edge (e.g., an isolated vertex in Vadd): such vertices are not ordered by ≺Eadd as defined ('a total order in which the endpoints of new edges will appear'). Thus with two isolated new vertices and one old vertex, no pair order is fixed, and with three isolated new vertices the transitivity clause ¬x_{u,v}∨¬x_{v,w}∨x_{u,w} is genuinely 3-CNF. Because Lemma 16 provides the polynomial verification step inside Theorem 5, this gap means the FPT result lacks a proven correctness argument as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Queue Layout Extension (QLE), the problem of extending a partial ℓ-page queue layout of a subgraph H to a full layout of a supergraph G. The main contribution is a complexity map for QLE: NP-completeness when only edges are missing but all vertices are fixed (Theorem 1), fixed-parameter tractability in the number of missing edges in that setting (Theorem 2), membership in XP parameterized by the number κ of missing vertices and edges (Theorem 3), W[1]-hardness parameterized by κ (Theorem 4), fixed-parameter tractability parameterized by κ plus the number of pages ℓ (Theorem 5), and polynomial-time solvability when exactly two vertices are missing (Theorem 6). The paper stresses the contrasts with the analogous stack-layout extension problem, particularly the polynomial-time two-vertex case versus NP-hardness for stack layouts.","tokens_in":26940,"tokens_out":12116,"duration_ms":148406,"significance":"If all results are correct, the paper provides a essentially complete parameterized complexity classification of QLE and identifies several genuinely surprising distinctions between queue and stack layout extension. The W[1]-hardness reduction from Multicolored Clique is developed in considerable detail, and the appendix removing multi-edges addresses a real technical obstacle rather than leaving it as an assumption. The two-vertex polynomial-time result is a particularly clean and non-obvious contrast with the stack-layout setting. However, the proof of Theorem 5 rests on Lemma 16, and as written that lemma has correctness gaps in the 2-SAT encoding; since Theorem 5 is one of the three headline results, the classification is not yet fully supported.","major_comments":[{"comment":"The 2-SAT formula does not enforce totality. The subformula φ1 is ⋀_{u≠v} ((x_{u,v}⇒¬x_{v,u}) ∧ (x_{v,u}⇒¬x_{u,v})), which is equivalent to ⋀_{u≠v} (¬x_{u,v} ∨ ¬x_{v,u}); in particular, an assignment with x_{u,v}=x_{v,u}=0 satisfies φ1. The proof's (⇒)-direction nevertheless asserts that 'exactly one of these cases is true' when constructing ≺G from a satisfying assignment. Without totality, the assignment does not determine a spine order, so the claimed equivalence between satisfiability of φ and existence of a solution is not established. This is not a cosmetic omission: it is exactly the step that converts a satisfying assignment into a total order on V(G).","section":"Section 5, Lemma 16"},{"comment":"The proof does not include transitivity clauses in φ, and the argument that they are unnecessary is not valid. The claim that for every triple u,v,w the relative order of at least two of them is fixed by ≺H or ≺Eadd is asserted without a case analysis and is false as stated for new vertices that are not endpoints of any new edge and hence do not appear in ≺Eadd; with two such vertices and one old vertex, no pair order is fixed, and with three such vertices the clause ¬x_{u,v} ∨ ¬x_{v,w} ∨ x_{u,w} is an irreducible 3-CNF clause. Moreover, even when a pair's order is fixed, the reduced clause is not automatically among φ1–φ4 unless the transitivity clauses are explicitly added to the formula. Because transitivity is missing, a satisfying assignment may contain directed cycles such as x_{u,v}=x_{v,w}=x_{w,u}=1 while satisfying all φ1 clauses; the proof's instruction to 'take the transitive closure' is then not legitimate, since closing a cyclic relation destroys antisymmetry. Since Lemma 16 supplies the polynomial verification step inside Theorem 5, the proof of Theorem 5 is incomplete as written.","section":"Section 5, Lemma 16 (transitivity)"}],"minor_comments":[{"comment":"In the proof of Lemma 7, the final conclusion of the argument for F′ is stated as ac∉F′, but the argument actually shows as≺cs and ae≺ce, so the complement edge ac should lie in F′; the conclusion should be ac∈F′.","section":"Section 3, Lemma 7"},{"comment":"The instance notation in the statement of Lemma 21 contains a typo: 'I′=(ℓ,H,G′=G\\{e},⟨≺,σ⟩)' should be 'I′=(ℓ,G′,H,⟨≺H,σH⟩)'.","section":"Section 6, Lemma 21"},{"comment":"In the proof of Lemma 16, the sentence 'we conclude that ⟨≺H,σH⟩ is a solution of I' should refer to ⟨≺G,σG⟩, since the solution is the layout of G being constructed.","section":"Section 5, Lemma 16"},{"comment":"The sentence 'we replace for every two vertices u,v∈Eadd' should read 'for every two vertices u,v∈Vadd', since Eadd is a set of edges, not vertices.","section":"Section 5, Lemma 16"},{"comment":"The phrase 'O(nadd!·madd^{nadd}) potential orders among endpoints of new edges' is imprecise when nadd is larger than the number of vertices that are actually endpoints of new edges; the branching is over permutations of the new vertices, so the wording 'orders of the new vertices' would be clearer.","section":"Section 5, Theorem 5"}],"recommendation":"major_revision","confidential_remarks":"The main correctness gap is localized to Lemma 16, but it is load-bearing for Theorem 5, which is advertised as one of the three main results and appears in the abstract and Table 1. I do not think the paper should be rejected: the gap appears repairable by rewriting Lemma 16 with explicit totality clauses and explicit transitivity clauses reduced to 2-CNF under a total order on all new vertices, and the rest of the paper contains substantial correct material. However, the revised version must also state clearly what is assumed about new vertices that are not endpoints of any new edge (e.g., isolated vertices), since the current proof silently relies on such an assumption."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this. The paper is a genuine contribution: it gives a complete parameterized complexity map for Queue Layout Extension (QLE), with new algorithms and lower bounds, and identifies a real contrast with stack layout extension. The W[1]-hardness reduction (Theorem 4) is carefully built, the multi-edge removal appendix is thorough, and the two-vertex polynomial case (Theorem 6) is a substantial new result. The proof of Lemma 7 has a small typo (the conclusion should be ac∈F', not ac∉F'), but that's minor.\n\nThe soft spot is Lemma 16, which is the engine of the FPT theorem (Theorem 5). The stress-test is right on both counts. The formula φ1 only prevents both x_{u,v} and x_{v,u} from being true; it doesn't require one of them to be true, so \"exactly one of these cases is true\" doesn't follow. You can't build a total order from the satisfying assignment as stated. And the transitivity argument fails for new vertices that are not endpoints of any new edge: for three such isolated vertices, no pair's order is fixed, so the transitivity clause is genuinely 3-CNF. That means the polynomial-time 'check' in Lemma 16 isn't proven, and Theorem 5 lacks a correctness proof.\n\nThis gap is load-bearing but probably repairable. You could, for instance, handle new vertices with no incident edges by simply placing them at one end of the spine, since they impose no constraints. But as written, the proof of a central result is incomplete.\n\nMy verdict: this deserves a serious referee. Send it to review, and the referee should require a fixed Lemma 16. The rest of the paper looks solid, and if the gap is closed, it's a strong paper.","headline":"New complexity map for queue layout extension, but the FPT theorem's 2-SAT lemma has a real gap that needs fixing.","tokens_in":27516,"tokens_out":5095,"would_cite":false,"duration_ms":56439,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q27","68R10","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes a complete parameterized complexity map for the Queue Layout Extension problem, showing it is NP-complete with all vertices fixed, W[1]-hard in the number of missing elements, fixed-parameter tractable when page…","keywords":["Queue layouts","Parameterized complexity","Extension problems","Linear layouts","Permutation graphs","2-SAT","Fixed-parameter tractability","Queue number"],"falsifier":"Enumerate all spine orders for a small instance with three new vertices, none incident to a missing edge, and compare the answer of Lemma 16's 2-SAT formula with brute-force extendability; a mismatch in either direction would refute the lemma. A more direct test is to exhibit a triple in which no two elements are ordered by ≺H or ≺Eadd, forcing a three-literal transitivity clause and breaking the claimed 2-CNF encoding.","tokens_in":26479,"feed_emoji":"🧩","tokens_out":7947,"duration_ms":86566,"temperature":0.7,"pith_summary":"The paper asks how hard it is to finish a partially drawn queue layout: some vertices and edges already sit on a spine and are assigned to pages, and the task is to insert the missing vertices and edges so that no page contains two nested edges. It claims a full complexity map for this problem. With the spine fixed, deciding extendability is already NP-complete, but fixing only the missing edges makes it fixed-parameter tractable in their number. Counting both missing vertices and missing edges gives W[1]-hardness, so no fixed-parameter algorithm is expected; adding the number of pages to the parameter restores fixed-parameter tractability. Notably, when exactly two vertices are missing the problem becomes polynomial-time solvable, in direct contrast to the analogous stack-layout extension problem, which is NP-hard in that setting.","feed_headline":"Extending queue layouts: NP-hard, W[1]-hard, FPT, and easy","feed_subtitle":"With all vertices fixed it is NP-complete; with two vertices missing it runs in polynomial time, unlike stack layouts.","key_machinery":"The argument runs through several constructions. First, the conflict graph C(G,≺) — vertices are edges of G, adjacency means the two edges nest in the spine order — is shown to be a permutation graph, so assigning edges to pages with a fixed spine order is exactly coloring that permutation graph, and extending a layout is precoloring extension. For the hardness lower bound, two gadgets on the spine, an edge gadget and a fixation gadget, force each new vertex to land in the interval corresponding to a vertex of the right color and force adjacency to match the input graph's edges. For the FPT result, Observation 15 turns the non-nesting condition into biconditional clauses, and Lemma 16 packages the whole spine-placement problem as a 2-SAT instance whose clauses stay binary because old and guessed orders fix at least two positions in every triple. For the two-vertex case, Lemmas 18–21 supply reduction rules using visibility sets P(e) to delete edges with at least two admissible pages without changing solvability.","core_discovery":"The paper's central claim is that Queue Layout Extension (QLE) — linear arrangement of vertices plus page assignment avoiding nested edges, given a partial such layout to extend — has the following exact complexity classification: NP-complete when all vertices are present but edges may be missing; in XP but W[1]-hard when parameterized by the total number of missing elements; fixed-parameter tractable when the parameter is the number of pages plus the number of missing elements; and polynomial-time solvable when the partial layout is missing exactly two vertices. The two-vertex result is the paper's headline contrast with stack layouts, where the corresponding restriction is NP-hard.","pith_inferences":["If Lemma 16's structural assertion is made fully explicit, a likely consequence is that the same 2-SAT framework handles partial page assignments where only some edges' colors are prescribed, not just full subgraph layouts.","The contrast with stacks suggests that extension complexity is not a single property of linear layouts; each layout style's local forbidden configuration (nesting versus crossing) creates its own algorithmic boundary, so results for queue and stack layouts should not be assumed to transfer to track layouts or other linear drawing styles.","A natural testable extension is whether the two-vertex polynomial algorithm generalizes to a constant number of missing vertices; if the visibility reduction rules survive, QLE may be in XP parameterized by the number of missing vertices alone, without the page count.","The permutation-graph equivalence means any future improvement in coloring or list-coloring permutation graphs would immediately improve algorithms for queue-layout extension with fixed spine order; the paper already imports NP-completeness and XP membership from that direction."],"forward_implications":["For graphs whose vertex order is already fixed, extending a queue layout by missing edges is NP-complete but fixed-parameter tractable in the number of missing edges.","When both vertices and edges may be missing, the problem is W[1]-hard in the number of missing elements, ruling out an FPT algorithm for that parameter under the standard complexity hypothesis.","Including the number of pages in the parameter makes the problem fixed-parameter tractable, so the combined parameter gives the first positive algorithmic handle on general missing vertices and edges.","With exactly two missing vertices, extendability is decidable in polynomial time even though the number of missing edges is unbounded, giving the first concrete separation from stack-layout extension in the same setting."],"supporting_citations":[{"why":"Supplies the NP-hardness of computing 1-page queue layouts from scratch, which makes QLE NP-hard already when all vertices are missing and ℓ = 1.","marker":"[24]"},{"why":"Establishes that assigning edges to queues in a fixed spine order is equivalent to coloring a permutation graph, the basis for Theorem 1.","marker":"[17,18]"},{"why":"Shows precoloring extension is NP-complete on permutation graphs, giving the NP-completeness direction of Theorem 1.","marker":"[25]"},{"why":"Shows list coloring of permutation graphs with up to k colors is in XP parameterized by k, giving the XP part of Theorem 1.","marker":"[21]"},{"why":"The stack-layout extension paper whose algorithms, hardness gadgets, and two-vertex NP-hardness result QLE adapts and contrasts.","marker":"[12]"},{"why":"Linear-time algorithm for 2-SAT, used as the polynomial verification step inside Lemma 16 and Theorem 5.","marker":"[2]"},{"why":"Standard reference for parameterized complexity and the W[1]-hardness of Multi-colored Clique, the starting problem of the reduction in Theorem 4.","marker":"[11]"}],"fun_headline_variants":["Queue layout extension: NP-hard, W[1]-hard, and easy with two gaps","Extending queue layouts: simple when two vertices are missing","Two missing vertices flip queue layout extension from hard to easy","Contrast with stacks: queue extension gets easy with two missing vertices","Queue layouts: NP-complete, W[1]-hard, FPT, and trivial for two missing vertices"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The FPT algorithm in Theorem 5 rests on Lemma 16's claim that for every triple of vertices, the relative order of at least two is already pinned down by the old spine order or the guessed order of new-edge endpoints, so transitivity constraints never require a clause with three literals; the paper does not give a full case analysis, especially for vertices that are not endpoints of any new edge.","fun_headline_variants_meta":{"raw":{"variants":["Queue layout extension: NP-hard, W[1]-hard, and easy with two gaps","Extending queue layouts: simple when two vertices are missing","Two missing vertices flip queue layout extension from hard to easy","Contrast with stacks: queue extension gets easy with two missing vertices","Queue layouts: NP-complete, W[1]-hard, FPT, and trivial for two missing vertices"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000958,"raw_usage":{"total_tokens":4000,"prompt_tokens":779,"completion_tokens":3221,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":395,"completion_tokens_details":{"reasoning_tokens":3120}},"tokens_in":395,"tokens_out":3221,"duration_ms":29103,"temperature":1.0,"reasoning_tokens":3120,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T10:25:25.890212+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all spine orders for a small instance with three new vertices, none incident to a missing edge, and compare the answer of Lemma 16's 2-SAT formula with brute-force extendability; a mismatch in either direction would refute the lemma. A more direct test is to exhibit a triple in which no two elements are ordered by ≺H or ≺Eadd, forcing a three-literal transitivity clause and breaking the claimed 2-CNF encoding.","supporting_citations":[{"cited_title":"The O ptimum C ost C hromatic P artition P roblem","cited_arxiv_id":null,"evidence_quote":"Shows precoloring extension is NP-complete on permutation graphs, giving the NP-completeness direction of Theorem 1."},{"cited_title":"On L ist C oloring and L ist H omomorphism of P ermutation and I nterval G raphs","cited_arxiv_id":null,"evidence_quote":"Shows list coloring of permutation graphs with up to k colors is in XP parameterized by k, giving the XP part of Theorem 1."}],"review_version":1}