{"id":"09888035-7ccc-4ba6-bbc2-4bdfd5608e8e","arxiv_id":"2607.17930","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"mCLP is NP-complete even on constant-size-tree forests with bounded levels or clusters, and FPT when parameterized by vertex cover number plus number of clusters.","lead":"mCLP stays NP-complete even when the graph is a forest of tiny trees with few clusters or levels, but becomes fixed-parameter tractable when parameterized by vertex cover plus cluster count. The paper introduces 'solution normalizations' and 'blueprints' to handle the problem's non-hereditary behavior, which blocks standard kernelization tricks.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"FPT proof depends on an unproven straight-line redrawing step (Lemma 13) that cites a theorem not supporting fixed-y-coordinate straightening; if the claim is false, Lemma 18 and Theorem 23 collapse.","rationale":"The reader's weakest_assumption correctly identifies the straight-line redrawing step in Lemma 13 as the most insecure point. My analysis of the proof confirms that Lemma 13's shortcut argument depends entirely on the ability to treat the region K as a straight-line polygon. The cited reference [18] (Pach and Tóth, monotone drawings) does not establish preservation of prescribed y-coordinates, and no other justification is provided. This is the single most load-bearing concern because it underpins Lemma 18, which is the bridge between solution normalizations and the bounded-size subinstance property that makes FPT enumeration possible. I do not see a clear alternative route in the paper that avoids this step for bounding pendant vertices. Therefore the central FPT theorem is not fully proven as written. However, the gap is potentially patchable: if the straight-line level-drawing statement is true (as I suspect it may be, given the level-planar drawing literature), then the proof can be fixed by replacing the citation and adding a short justification. The reader's verdict of CONDITIONAL is appropriate; my stress-test does not move it. I agree with the reader's identification, so agreement_with_reader is 'agree'.","tokens_in":28424,"tokens_out":23825,"duration_ms":212385,"concrete_test":"Check whether every level-planar drawing with y-monotone edges can be redrawn with straight-line edges without changing vertex y-coordinates. Concretely: (1) Locate a known theorem stating that every level-planar graph admits a straight-line level drawing preserving the leveling (or construct one); if such a theorem exists, the gap is a simple citation fix. (2) If no such theorem is found, attempt a counterexample search over small level-planar graphs (e.g., all graphs with up to 6 vertices and 3 levels) by formulating the straight-line level drawing problem as a linear feasibility system: assign x-coordinates to vertices with fixed y-levels such that every edge is a straight segment between its endpoints and no two edges cross. If any level-planar graph fails this system, Lemma 13's straightening assumption is false and the FPT proof collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central FPT result (Theorem 23) rests on Lemma 18, which guarantees a bounded-size subinstance with a tidy solution. Lemma 18 in turn relies on Lemma 13 (Solution Normalization 5) to bound pendant vertices on induced augmentation paths. The critical step in Lemma 13 is: 'By the work of Pach and Tóth [18], we can assume that all edges of (E,A) are drawn as straight line segments without changing the y-coordinates of the vertices.' This is not a consequence of [18] as cited. The paper [18] proves the existence of monotone straight-line drawings of planar graphs, but it does not prescribe vertex y-coordinates (levels). The proof of Lemma 13 requires the region K to be a straight-line polygon so that Proposition 2 can be applied to find a y-monotone chord. If edges may only be y-monotone curves, the boundary of K can be curved, Proposition 2's triangulation-based argument does not apply, and the shortcutting step fails. Without Lemma 13, the bound on pendant vertices in Lemma 18 is unsupported, so the bounded-size subinstance claim—and hence the FPT enumeration in Theorem 23—does not go through. This is not merely a missing citation: the paper supplies no proof of the fixed-y-coordinate straight-line redrawing claim, and it is not obviously true. A second instance of the same geometric gap appears in Lemma 18 when invoking [3, Lemma 5] for shortcutting non-peak/valley paths. The concern is load-bearing, but it is addressable if the straight-line claim can be justified by a correct theorem or a direct construction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the parameterized complexity of monotone Clustered Level Planarity (mCLP), a level-planar drawing problem with cluster connectivity constraints. It presents two main contributions. First, it strengthens the known NP-hardness of mCLP: the problem remains NP-complete even when the input is a forest in which every connected component has constant size, and either the number of levels or the number of clusters is a small constant (Theorems 4 and 5). Second, it gives an FPT algorithm for mCLP parameterized by the vertex cover number plus the number of clusters (Theorem 23). The FPT result is obtained by proving that every yes-instance has a bounded-size subinstance admitting a 'tidy' solution (Lemma 18), and then enumerating all 'blueprints' of bounded size and testing their realizability via dynamic programming (Lemma 21). The paper contains detailed proofs, several solution-normalization lemmas, and a discussion of why standard kernelization fails because mCLP is non-hereditary.","tokens_in":28850,"tokens_out":17946,"duration_ms":171258,"significance":"If correct, the paper essentially settles the parameterized complexity of mCLP for the most common graph-structural parameters, leaving only the vertex cover number without the cluster count as an open case. The proposed blueprint technique is an interesting way to handle non-hereditary planarity problems, and the explicit 'solution normalization' approach may be useful beyond this specific problem. The hardness results are strong and well motivated. The paper is well structured, provides many illustrative figures, and is transparent about the places where proofs are sketched. However, the FPT proof rests on a geometric redrawing assumption that is not supported by the cited reference, which makes the central algorithmic result currently not fully verified.","major_comments":[{"comment":"The proof of Lemma 13 contains the claim: 'By the work of Pach and Tóth [18], we can assume that all edges of (E,A) are drawn as straight line segments without changing the y-coordinates of the vertices.' This is not a consequence of the cited paper, which concerns monotone straight-line drawings of planar graphs and does not prescribe vertex y-coordinates. The straightening step is essential: it lets the region K be treated as a simple polygon so that Proposition 2 can be applied to shortcut the augmentation path P. Without a correct justification, the bound on pendant vertices in Lemma 18 is unsupported, and with it the bounded-size subinstance Lemma 18 and the FPT enumeration in Theorem 23. The authors should either prove the fixed-y-coordinate straight-line redrawing claim (for example by citing a level-planar straight-line drawing theorem) or replace this step with a different argum","section":"§4.1, Lemma 13 (Solution Normalization 5)"},{"comment":"The proof of Lemma 18 invokes '[3, Lemma 5]' to modify the drawing so that a shortcut edge can be inserted crossing-free and y-monotone. The cited lemma is about radial level planarity with fixed embedding and may not apply directly to the situation here, where augmentation edges and varying y-levels are involved. Since this step is used to bound the number of isolated vertices, it is also load-bearing for Lemma 18 and Theorem 23. The authors should either state the lemma from [3] and verify that its hypotheses hold, or give a self-contained proof of the shortcut property.","section":"§4.1, Lemma 18 (proof)"}],"minor_comments":[{"comment":"The proof of Theorem 3 is only sketched: 'We only sketch the correctness of the slightly modified construction here as it also follows analogously to the proof given by [11].' Since the new hardness theorems (Theorems 4 and 5) are built on this modified construction, the sketch should be expanded to state explicitly which modifications are made and why equivalence is preserved, or the theorem should be cited directly from [11] without proof.","section":"§3, Theorem 3"},{"comment":"In the dynamic-programming proof, the claim that Property (iii) of Claim 22 is independent of the choice of the mapping Phi_l' is only justified by a brief comment about counting ears in equivalence classes. This is plausible but should be formalized: the existence of an injective mapping between suitable vertices can be checked by a matching argument, and the cover assignment is itself a matching problem. The current proof does not give the precise complexity bound in terms of the input size, though the description suggests polynomial time.","section":"§4.2, Lemma 21"},{"comment":"Figure 2, which summarizes the parameter combinations for NP-hardness, is visually dense and the labels are small. A table with the exact parameters used in Theorems 3–5 might be easier to read. Minor typos and punctuation issues appear in the text, e.g., the missing space in 'we refer to the problem (y-)monotone Clustered Level Planarity (mCLP)' in the introduction.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The central algorithmic result (Theorem 23) hinges on a geometric claim in Lemma 13 that is not supported by the cited reference [18]. This is not a minor citation issue: if the straight-line redrawing with fixed y-coordinates is not possible, the bound on pendant vertices and hence the FPT theorem collapse. I believe the claim is likely true and can be proved using known level-planar straight-line drawing results, so I recommend major revision rather than rejection. The authors should also double-check the use of [3, Lemma 5] in Lemma 18. The hardness results and the overall approach are solid and will be valuable once the geometric gaps are closed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is worth reading. The paper largely settles the parameterized landscape for mCLP, and the FPT half introduces a solution-normalization/blueprint technique that is a real contribution. I would send it to review, but I would want the authors to fix one under-supported geometric step before I trust the FPT theorem.\n\nThe hardness part is the strongest. Theorems 4 and 5 show NP-completeness even when every component is a constant-size tree and either the number of levels or the number of clusters is small. That is a clean exclusion result, and it knocks out FPT for almost all structural parameters. The construction is elaborate, but the proof sketches are plausible and carry conviction.\n\nThe FPT result (Theorem 23) is the genuinely new thing. The idea of working with solution normalizations rather than kernelization, then encoding bounded-size subinstances as blueprints and matching them with DP, is clever and handles the non-hereditary behavior honestly. Lemma 7 is the right setup.\n\nThe soft spot is geometric. In Lemma 13, the proof says that by Pach and Toth [18] we may assume all edges are straight-line segments while keeping the vertex y-coordinates. That is not what [18] proves, and the paper gives no direct proof. If the claim is false, the bound on pendant vertices in Lemma 18 falls apart, and with it the bounded-subinstance argument. I suspect the claim is true -- I would be surprised if level-planar drawings cannot be straightened with levels fixed -- but as written it is a gap. The authors need to supply a correct citation or a lemma. There is a second spot in Lemma 18 where [3, Lemma 5] is invoked for shortcutting; it is probably fine, but check.\n\nAlso, Theorem 3's proof is only sketched, and the new hardness results inherit from it. Since it is the authors' own published result, that is less worrying, but a precise reference would make the paper stronger. Lemma 21's counting argument also deserves a bit more detail.\n\nIf these are addressed, I would be happy with the paper. As is, I would still send it to peer review -- the hardness results stand alone, and the FPT machinery is worth publishing even if the geometric lemma needs a patch.","headline":"The paper is largely sound and genuinely interesting; the FPT proof has a load-bearing geometric gap that should be fixed, but this is a solid contribution worth reviewing.","tokens_in":29260,"tokens_out":13899,"would_cite":true,"duration_ms":132290,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C85","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Clustered level planarity is FPT with vertex cover plus cluster count","keywords":["monotone clustered level planarity","level planarity","clustered planarity","cluster augmentation","parameterized complexity","fixed-parameter tractability","vertex cover","NP-completeness"],"falsifier":"Find a level graph that has a level-planar y-monotone embedding but for which no straight-line drawing exists that keeps all vertices on their assigned levels; such a counterexample would falsify the geometric assumption behind the pendant-vertex bound and would break the FPT proof.","tokens_in":28380,"feed_emoji":"📐","tokens_out":11325,"duration_ms":90154,"temperature":0.7,"pith_summary":"Monotone Clustered Level Planarity (mCLP) asks whether a graph with fixed vertex levels can be drawn without crossings so that each cluster can be made connected by adding y-monotone edges. This paper determines which parameters make the problem tractable. On the negative side, mCLP remains NP-complete even for forests of constant-size trees with no isolated vertices and only a constant number of clusters or levels, which rules out fixed-parameter algorithms for almost every structural graph parameter. On the positive side, the problem is fixed-parameter tractable when the parameter is the vertex cover number plus the number of clusters. The key is showing that every yes-instance has a bounded-size subinstance admitting a tidy solution, then enumerating abstract blueprints of such subinstances, because standard kernelization fails for this non-hereditary problem.","feed_headline":"Clustered level planarity is FPT with vertex cover plus cluster count","feed_subtitle":"NP-hardness holds even on constant-size trees, so vertex cover is the only useful parameter.","key_machinery":"The central object is the tidy solution: a solution of a subinstance in which every omitted degree-2 vertex (an ear) is covered by a special augmentation edge with triangular incident faces, so that omitted vertices can be spliced back in without crossings. Solution normalizations show that any solution can be compressed to a tidy solution on a bounded-size subinstance, controlling transversals, ears, pendant vertices, and isolated vertices. Blueprints then let the algorithm enumerate all candidate bounded subinstances in FPT time: a blueprint is an abstract mCLP instance whose core matches the input and whose non-core vertices are dummies carrying only level-order information, and a polynom","core_discovery":"The central claim is that a yes-instance of mCLP admits a tidy solution on a subinstance whose size is bounded by a polynomial in the size of a vertex cover and the number of clusters, and that any such tidy solution can be extended to the entire instance by reinserting all omitted vertices. This yields a fixed-parameter algorithm: enumerate all bounded-size blueprints (abstract instances that match the input on a core subgraph), test each blueprint for realizability by dynamic programming, and answer yes exactly when some blueprint is realizable. The paper also proves that mCLP is NP-complete even for acyclic instances whose components have constant size, with either at most three clusters","pith_inferences":["The blueprint and solution-normalization framework is not specific to mCLP and could plausibly transfer to other non-hereditary constrained drawing problems where kernelization is blocked.","A natural next step is to decide whether the number of clusters can be dropped from the parameter; the paper's dynamic program would then have to track cluster-to-cluster mappings, which seems to be the main obstacle.","The polynomial bound on isolated vertices is the tightest part of the proof; a more direct combinatorial argument for isolated vertices could lower the parameter dependence or yield a kernel."],"forward_implications":["mCLP is para-NP-hard for treewidth, pathwidth, feedback vertex set, maximum degree, and essentially every graph-structural parameter except vertex cover, even when combined with a constant number of clusters or levels.","mCLP is fixed-parameter tractable when parameterized by vertex cover number plus the number of clusters, so instances with small vertex cover and few clusters can be solved exactly in FPT time.","Every yes-instance contains a bounded-size subinstance with a tidy solution, which directly yields an XP algorithm and provides a polynomial-time verifiable structural certificate.","The hardness reductions hold for acyclic, proper instances with fixed rotation, so these restrictions alone do not make the problem tractable."],"fun_headline_variants":["Vertex cover plus cluster count makes mCLP fixed-parameter tractable","Hard on bounded trees, but FPT with vertex cover and clusters","Only vertex cover and clusters give tractability for mCLP","New FPT algorithm: vertex cover and cluster count tame mCLP"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The FPT proof assumes a cited geometric straightening result: every level-planar drawing with y-monotone edges can be redrawn with straight-line edges while keeping every vertex on its prescribed level; this is used to bound the number of pendant vertices, and if it fails, the polynomial bound on subinstance size collapses.","fun_headline_variants_meta":{"raw":{"variants":["Vertex cover plus cluster count makes mCLP fixed-parameter tractable","Hard on bounded trees, but FPT with vertex cover and clusters","Only vertex cover and clusters give tractability for mCLP","New FPT algorithm: vertex cover and cluster count tame mCLP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000734,"raw_usage":{"total_tokens":3171,"prompt_tokens":848,"completion_tokens":2323,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":592,"completion_tokens_details":{"reasoning_tokens":2247}},"tokens_in":592,"tokens_out":2323,"duration_ms":17143,"temperature":1.0,"reasoning_tokens":2247,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T16:34:46.387373+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a level graph that has a level-planar y-monotone embedding but for which no straight-line drawing exists that keeps all vertices on their assigned levels; such a counterexample would falsify the geometric assumption behind the pendant-vertex bound and would break the FPT proof.","supporting_citations":[],"review_version":1}