{"id":"7afae2cc-ce3e-4f4e-bf40-7079358973b4","arxiv_id":"1908.08911","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Fixed-Order Book Thickness is fixed-parameter tractable by vertex cover number and by pathwidth of the vertex order, and Book Thickness is fixed-parameter tractable by vertex cover number.","lead":"This paper gives fixed-parameter algorithms for deciding whether a graph can be drawn in a k-page book, both when the vertex order is fixed and when it is not. The algorithms are fast when the graph has a small vertex cover, and for fixed order when the order has small pathwidth.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the DP interchangeability lemmas hold under scrutiny; a small-instance brute-force cross-check would still be worthwhile.","rationale":"The reader correctly identifies the interchangeability of partial assignments with the same visibility record as the key fragile step in both fixed-order algorithms. I agree that this is the assumption that would break the FPT claims if false. However, my detailed check of Lemma 1 and Lemma 4 found the step sound: the transition from one record set to the next is deterministic when given the stored representative, and the proof of Lemma 1 can be completed for the case i∉X by noting that then u_{i−1} and u_i are consecutive with no cover vertex between, so the old visibility of u_i equals the old visibility of u_{i−1}, which is stored; if a cover vertex does lie between, then i∈X and its old visibility matrix is in the record. The pathwidth DP's guard-insertion step is also valid because newly inserted guards are not in the old guard set, so Lemma 3 applies to them directly, and copying from the immediate successor in the queue is justified even when the successor is another new guard. The only notable imprecision is the kernel-size statement O(kτ) in Theorem 3's proof, since the number of vertex types is 2^τ; the true kernel size is O(2^τ kτ). This is a minor presentational error, not a correctness issue, because the brute-force bound τ^{τ^{O(τ)}} is loose enough to absorb the exponential dependency on τ. Overall, the central claims of fixed-parameter tractability appear correct, and I recommend keeping the reader's ACCEPT verdict.","tokens_in":13740,"tokens_out":56535,"duration_ms":526441,"concrete_test":"Implement both fixed-order DP algorithms (Theorem 1 and Theorem 2) exactly as described, and cross-check against brute-force enumeration of all page assignments (and, for Theorem 2, all relevant vertex orders) for all graphs on n≤8 with vertex cover number τ≤3, and for Theorem 2 also orders with pathwidth κ≤2, over many random edge sets. Compare the YES/NO answers and the minimum page count returned; any mismatch would pinpoint a failure of Lemma 1 or Lemma 4.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After full scrutiny, I cannot identify a load-bearing flaw. The central risk is indeed Lemma 1 and Lemma 4's interchangeability of partial assignments with identical visibility records. I traced the transition maps: validity of a new β depends only on M_{i−1}(i−1), and new visibility matrices depend only on the old matrices; the current-vertex case i∉X reduces to M_{i−1}(i−1) because then u_{i−1} and u_i are consecutive with no C vertex between, and if a C vertex does lie between, i∈X so its matrix is already stored. For the pathwidth DP, new guards are not in P*_i, so Lemma 3 legitimately applies to them, and copying from the immediate successor is valid even when that successor is also new. The only imprecision is the kernel-size statement 'O(kτ)': the number of types is 2^τ, so the kernel is actually O(2^τ kτ), but this is absorbed by the stated τ^{τ^{O(τ)}} brute-force bound and does not affect the FPT claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the parameterized complexity of two NP-complete book embedding problems. For Fixed-Order Book Thickness, Theorem 1 provides an algorithm running in 2^{O(τ^3)}·n when parameterized by the vertex cover number τ, and Theorem 2 provides an algorithm running in n·κ^{O(κ^2)} when parameterized by the pathwidth κ of the fixed vertex order. For Book Thickness, Theorem 3 gives a kernelization parameterized by τ, with total running time τ^{τ^{O(τ)}} + 2^τ·n. All three algorithms output a witness embedding if one exists. The proofs are based on dynamic programming over visibility matrices and visibility vectors, with interchangeability lemmas showing that partial page assignments with identical visibility records are equivalent for all future extensions, and a kernelization using page-equivalence classes of vertices outside a vertex cover.","tokens_in":13960,"tokens_out":30840,"duration_ms":288136,"significance":"The results are significant and timely. They provide the first FPT algorithms for Fixed-Order Book Thickness and the first FPT algorithm for Book Thickness for general values of k, making progress on a question of Dujmović and Wood about bounded-treewidth graphs. The visibility-based DP abstraction is elegant and the interchangeability lemmas are the right technical tool; the algorithms are also constructive and output witnesses. The kernelization is simple and uses a clean K_{2,3} obstruction argument. On close reading, the central DP correctness arguments are sound. The caveats are local: a pigeonhole bound in the kernelization proof is misstated, one geometric insertion step is informal, and some notation is sloppy. None of these issues affects the main FPT claims, and all are easily repairable.","major_comments":[{"comment":"The pigeonhole step is incorrect as written. With |V_U\\{v}| ≥ 2kτ+1 vertices partitioned into at most k^τ page-equivalence classes, one cannot conclude that three vertices are page-equivalent; for example, k=τ=10 gives 41 vertices and up to 10^10 classes. The argument requires |V_U\\{v}| > 2k^τ, so the threshold should be |V_U| ≥ 2k^τ+2. Consequently the kernel size is O(2^τ k^τ), not O(kτ) as stated. The FPT bound in Theorem 3 remains valid after this correction, but the proof and the stated kernel size need to be fixed.","section":"Section 4, Theorem 3 Claim"},{"comment":"The extension of a k-page book embedding by inserting v next to u1 and routing each new edge vw 'arbitrarily close' to u1w is informal. A rigorous justification is needed: because u1 has at most one edge on each page, each page contains at most one new edge incident to v, and that edge can be drawn in the same face of the existing page as u1w; since v and u1 are consecutive on the spine, the small connecting segment crosses no edge. Please spell this out and state explicitly whether v is inserted to the left or right of u1.","section":"Section 4, Theorem 3 Claim (embedding extension)"}],"minor_comments":[{"comment":"Superscripts are missing in several bounds: 'ττ^2' should be τ^{τ^2}, '2τ^3+τ^2' should be 2^{τ^3+τ^2}, and 'ττ' in the runtime should be τ^τ.","section":"Section 3.1"},{"comment":"The proof is too compressed. It should state explicitly that the transition from Q_i to Q_{i-1} is a deterministic function of the visibility vectors in a record and the assignment β of F_{i-1}, so that two partial assignments with the same record are interchangeable for validity and for the updated record. This is the key safety property of the representative Λ_i and deserves a direct statement.","section":"Section 3.2, Lemma 4"},{"comment":"When computing Q_0 from Q_1, the rule 'if v_{i-1}∈P^*_i then ω'=(ω_2,...,ω_m)' yields an empty tuple when P^*_1={v_0}; the paper should clarify that v_0's visibility vector is vacuously all-⋄ and that an empty record for Q_0 is intended, or add a special-case initialization for Q_0.","section":"Section 3.2, base case"},{"comment":"The brute-force expression O(kτ!·k^{kτ}) is unclear. Since the kernel has N = O(2^τ k^τ) vertices, the enumeration should be stated as O(N!·k^{O(N^2)}), which evaluates to τ^{τ^{O(τ)}}.","section":"Section 4, Theorem 3"}],"recommendation":"minor_revision","confidential_remarks":"The paper is a solid contribution and, after the local fixes above, suitable for publication. The reader's positive assessment matches mine; the kernelization threshold and the geometric step are the only points requiring attention. I recommend minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a genuinely useful paper. It gives the first fixed-parameter algorithms for book thickness with general page count k, parameterized by vertex cover, and for fixed-order book thickness by vertex cover and by the pathwidth of the order. The Bannister–Eppstein result only handled k=2 under treewidth, so this is real new ground.\n\nThe visibility-based DP is a neat idea. The interchangeability lemmas (Lemma 1 and Lemma 4) are load-bearing and they check out; I traced the transition maps and the induction goes through. The kernelization in Theorem 3 is straightforward but correct, and the type-counting argument is clean. The algorithms output witnesses, which is often missing in this literature. Credit where due: the paper is carefully written, the proofs are mostly complete, and the techniques are honestly assembled from known parameterized-toolbox components.\n\nTwo soft spots, both minor. First, the kernel-size bound says O(kτ), but the number of types is 2^τ, so the kernel is actually O(2^τ kτ). This does not affect the FPT claim because the brute-force bound τ^{τ^{O(τ)}} is already enormous, but it is a sloppy statement. Second, the proof of the claim in Theorem 3 says a copied edge runs 'arbitrarily close' to an existing edge; this is the only informal geometric step I can find. It is intuitively right and I do not think it hides a counterexample, but it deserves a rigorous sentence or a figure. Also, given the DPs are intricate, a brute-force cross-check on small instances would be cheap insurance, but that is a suggestion, not a flaw.\n\nThe central argument holds up. The treewidth question remains open, and the authors say so; that is honest.\n\nWho is this for? People in graph drawing and parameterized complexity. It deserves serious peer review. I would accept it and send to a good conference or journal; the minor issues are fixable in revision.","headline":"First real FPT results for book thickness beyond k=2; proofs hold up, with only minor kernel-size imprecision and a casual geometric step.","tokens_in":14467,"tokens_out":1521,"would_cite":true,"duration_ms":14216,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Book thickness is fixed-parameter tractable under vertex cover","keywords":["book embedding","fixed-parameter tractability","vertex cover number","pathwidth","kernelization","visibility","graph drawing"],"falsifier":"Search for a graph, a vertex order, and two distinct partial page assignments that yield identical visibility records (identical matrices for every snapshot position in Section 3.1, or identical vectors for every guard in Section 3.2) but for which one assignment admits a crossing-free completion to $k$ pages and the other does not; such a pair would refute Lemma 1 or Lemma 4 and invalidate the FPT bounds.","tokens_in":13579,"feed_emoji":"📖","tokens_out":11660,"duration_ms":100778,"temperature":0.7,"pith_summary":"The paper establishes that two NP-complete book embedding problems become tractable when the input graph is structurally simple. For graphs with a vertex cover of size $\\tau$, both Fixed-Order Book Thickness and Book Thickness admit fixed-parameter algorithms, meaning they run in time linear in the graph size times a factor that depends only on $\\tau$; the fixed-order problem is also fixed-parameter tractable when the pathwidth of the given vertex order is the parameter. In ordinary terms, once a small set of vertices touches every edge, or a narrow memory window along the spine suffices, the number of pages can be decided efficiently rather than by brute force. The algorithms are constructive: they return a book embedding that uses the minimum number of pages under the given order whenever one exists. These are the first fixed-parameter algorithms for the fixed-order problem and the first for general Book Thickness with more than two pages.","feed_headline":"Book thickness is fixed-parameter tractable under vertex cover","feed_subtitle":"Both NP-complete problems become tractable on graphs with a small vertex cover; fixed-order also via pathwidth.","key_machinery":"The mechanism carrying the argument is record-based dynamic programming with interchangeability: the state is not the full page assignment but a bounded-size visibility record, and the interchangeability lemmas (Lemma 1 for visibility matrices, Lemma 4 for visibility vectors) guarantee that storing one arbitrarily chosen assignment per record is safe. This bounds the state space by $2^{O(\\tau^3)}$ for the vertex-cover parameterization and by $(\\kappa+2)^{O(\\kappa^2)}$ for the pathwidth parameterization, yielding the FPT running times. For the unfixed-order variant, the load-bearing mechanism is kernelization by type counting: vertices outside the cover are classified by their neighbor set, and classes with more than $2k\\tau+2$ vertices are reduced without changing whether a $k$-page embedding exists.","core_discovery":"The central discovery is that exponentially many partial page assignments can be compressed into a bounded number of equivalence classes without losing future options. In the vertex-cover algorithm, each record is a visibility matrix—a table recording which cover vertices are reachable from a given vertex on each page without crossing an already assigned edge—together with snapshots at the positions immediately after each cover vertex; Lemma 1 proves that any two assignments with identical records behave identically in all future extension steps. In the pathwidth algorithm, each record is a visibility vector whose $p$-th entry is the important guard for page $p$, the nearest guard whose edge on that page blocks the view; Observation 3 shows this single guard fully determines which vertices remain visible, and Lemma 4 proves the same interchangeability. For Book Thickness without a fixed order, the paper kernelizes: keeping only $2k\\tau+2$ vertices of each type (same neighbor set inside the cover) preserves the answer, and an embedding of the reduced graph extends to the original.","pith_inferences":["If the important-guard characterization survives a bounded crossing budget, the same right-to-left dynamic program could likely run in $n \\cdot (\\kappa+c)^{O(\\kappa^2)}$ time for embeddings with at most $c$ crossings per page, extending the paper's own suggested future direction.","The interchangeability principle suggests a route to a bounded-treewidth algorithm, provided one can replace the spine's guards with a treewidth analogue of the important-guard observation, since a vertex can then be shielded by edges spanning several bags.","The kernel's dependence on neighbor sets suggests that other parameters bounding the number of distinct adjacency types, such as bounded neighborhood diversity, may also yield FPT algorithms for Book Thickness by the same type-counting argument."],"forward_implications":["A minimum-page book embedding of an $n$-vertex graph of vertex cover number $\\tau$ can be computed in $2^{O(\\tau^3)} \\cdot n$ time.","Fixed-Order Book Thickness with an order of pathwidth $\\kappa$ can be solved in $n \\cdot \\kappa^{O(\\kappa^2)}$ time, even when $\\kappa$ is much smaller than the vertex cover number.","Book Thickness is fixed-parameter tractable in the vertex cover number, via a kernel of $O(k\\tau)$ vertices that preserves embeddability.","All three algorithms return a valid $k$-page book embedding whenever one exists, so they solve the search and optimization versions, not just the decision problem.","These are the first fixed-parameter algorithms for the fixed-order problem, and the first for Book Thickness that allow more than two pages."],"supporting_citations":[{"why":"Supplies the $O(2^\\tau + \\tau n)$ minimum vertex cover algorithm used to compute the cover parameter in Theorems 1 and 3.","marker":"[6]"},{"why":"Proves Book Thickness is NP-complete and gives the complete-bipartite lower-bound graphs showing the page bounds of Observation 1 and Lemma 2 are tight.","marker":"[4]"},{"why":"Poses the bounded-treewidth open question that motivates the paper, with the new FPT results as partial progress.","marker":"[13]"},{"why":"Establishes that the fixed-order problem is NP-complete for four pages, providing the hardness baseline for the fixed-order parameterizations.","marker":"[28]"}],"fun_headline_variants":["Book embedding FPT under vertex cover","Fixed-order book thickness FPT via pathwidth","Kernel for book thickness under vertex cover","Vertex cover makes book embedding FPT"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that two partial page assignments producing identical visibility records are interchangeable for every future extension; if the concrete edge-to-page mapping ever influenced future possibilities beyond the record, the compression would lose soundness.","fun_headline_variants_meta":{"raw":{"variants":["Book embedding FPT under vertex cover","Fixed-order book thickness FPT via pathwidth","Kernel for book thickness under vertex cover","Vertex cover makes book embedding FPT"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001684,"raw_usage":{"total_tokens":6637,"prompt_tokens":868,"completion_tokens":5769,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":484,"completion_tokens_details":{"reasoning_tokens":5715}},"tokens_in":484,"tokens_out":5769,"duration_ms":38063,"temperature":1.0,"reasoning_tokens":5715,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:27:14.851269+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search for a graph, a vertex order, and two distinct partial page assignments that yield identical visibility records (identical matrices for every snapshot position in Section 3.1, or identical vectors for every guard in Section 3.2) but for which one assignment admits a crossing-free completion to $k$ pages and the other does not; such a pair would refute Lemma 1 or Lemma 4 and invalidate the FPT bounds.","supporting_citations":[{"cited_title":"Discrete Math","cited_arxiv_id":null,"evidence_quote":"Poses the bounded-treewidth open question that motivates the paper, with the new FPT results as partial progress."}],"review_version":1}