{"id":"36ecedf3-6759-4133-a0b8-c6d1c94d1d37","arxiv_id":"2505.18885","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Deciding whether a graph has linear vertex arboricity 2 is NP-hard for maximum degree 5, NP-hard for planar graphs of maximum degree 6, and fixed-parameter tractable by treewidth.","lead":"The authors study the linear vertex arboricity of graphs, the smallest number of parts in a vertex partition where each part induces a collection of paths. They prove that deciding whether this number is 2 is NP-hard even for graphs of maximum degree 5, and they give a fixed-parameter-tractable algorithm for graphs of bounded treewidth.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 3's variable-gadget description is self-contradictory: attaching the a-vertices to 1 and 2 as written makes vertices 1 and 2 have degree 7, so the max-degree-5 bound in Theorem 2 is not established by the text; Lemma 4 assumes different adjacency.","rationale":"The reader's weakest-assumption analysis focused on the uniqueness of legal colorings of the gadgets, and that is indeed a verification gap. But the more immediate and load-bearing problem is that the variable gadget in Section 3 is not even well-defined from the text: the construction paragraph and Lemma 4 imply different edge sets, and the literal construction violates the maximum-degree-5 bound because vertices 1 and 2 acquire degree 7. This is a concrete, locatable inconsistency in the proof of the central theorem, not merely a missing case analysis. The K4/K5 typo in the abstract and the planarity sentence in Theorem 2's proof are also real but less central: the first concerns a known result, and the second, if true, would only strengthen the result. My proposed check—extracting the actual adjacency from Fig. 7 and then brute-force enumerating legal 2-colorings of the corrected gadget—would settle whether Theorem 2 holds as intended. The central claim is probably salvageable with a localized correction, so the existing CONDITIONAL verdict remains appropriate.","tokens_in":11184,"tokens_out":28512,"duration_ms":172840,"concrete_test":"Extract the adjacency list of V'_a from Fig. 7 or the authors' source and compute the degrees of vertices 1 and 2. If the a-labeled vertices are adjacent to 1 and 2 as the text states, both vertices have degree 7, directly falsifying the maximum-degree-5 claim. If the figure instead matches Lemma 4, with a-vertices adjacent to 6 and 7 rather than to 1 and 2, then correct the textual construction and exhaustively enumerate all 2-colorings of the corrected gadget to verify Lemma 4's uniqueness claim; any legal coloring with one a-vertex white but the two a-vertices differently colored, or with the complement vertex not opposite, would break the reduction in Theorem 2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 2 rests on the variable gadget V'_a, but the text and Lemma 4 describe incompatible graphs. The construction in Section 3 says: 'add two nonadjacent vertices labeled a and connect both of them to both vertices 1 and 2. Next we connect the top a-labeled vertex to vertex 3 and the bottom one to vertex 5.' Under that literal reading, each of vertices 1 and 2 has degree 7: three neighbours 3,4,5 inside K5^-, plus 6,7, plus the two a-vertices. This contradicts the claimed maximum degree 5. Lemma 4's proof, however, treats the upper a-vertex as having neighbours 3,6,7 and the lower one as forming a triangle with 6 and 7, which is only consistent with attaching the a-vertices to 6 and 7, not to 1 and 2. Thus either the construction sentence is wrong, or the lemma's case analysis is not about the graph being constructed. Since Theorem 2 is the paper's headline tight-hardness result, the reduction cannot be checked and the degree bound is not established until the intended adjacency list is specified. This is more concrete than the reader's general concern about spurious colorings: even the graph to which the uniqueness lemmas apply is ambiguous.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the linear vertex arboricity (lva) of a graph, focusing on the parameterized complexity of the decision problem k-LVA. It claims three main results: (i) 2-LVA is NP-hard for planar graphs of maximum degree 6; (ii) 2-LVA is NP-hard for general graphs of maximum degree 5, which would be tight because all graphs of maximum degree 4 except K5 have lva at most 2; and (iii) for any k, k-LVA is fixed-parameter tractable with respect to the treewidth of the input graph, proved via an MSO2 formulation and Courcelle's theorem. The paper also gives ILP and SAT formulations for k-LVA and leaves open the planar maximum-degree-5 case.","tokens_in":11398,"tokens_out":21481,"duration_ms":175234,"significance":"The maximum-degree-5 hardness result is the headline contribution: it would pin down the exact degree threshold at which 2-LVA becomes NP-hard and would complement the known polynomial behavior for maximum degree 4. The treewidth FPT result is a straightforward but solid application of Courcelle's theorem, and the ILP/SAT encodings are compact and potentially useful in practice. However, the degree-5 result is currently not verifiable because the variable-gadget construction in Section 3 is internally inconsistent and the gadget uniqueness proofs are not sufficiently rigorous. The planar degree-6 hardness and the FPT result appear sound, but the central tight-hardness claim needs substantial repair before the paper can be accepted.","major_comments":[{"comment":"The construction text and the proof of Lemma 4 describe incompatible graphs. The text says: 'add two nonadjacent vertices labeled a and connect both of them to both vertices 1 and 2. Next we connect the top a-labeled vertex to vertex 3 and the bottom one to vertex 5.' Under this literal reading, each of vertices 1 and 2 has degree at least 7 (three neighbors inside K5^-, plus 6 and 7, plus the two a-vertices), contradicting the claimed maximum degree 5 of H'. Lemma 4's proof, however, treats the upper a-vertex as adjacent to vertices 3, 6, and 7, and the lower a-vertex as forming a triangle with 6 and 7, which corresponds to attaching the a-vertices to 6 and 7, not to 1 and 2. Since Lemma 4 supplies the uniqueness and color-forcing properties used in the correctness proof of Theorem 2, the reduction cannot be checked as written and the degree bound is not established until the intended adjacency is specified and Lemma 4 is re-proved for that graph.","section":"Section 3, variable gadget description and Lemma 4"},{"comment":"Even setting aside the construction mismatch, the uniqueness proof is incomplete. The step 'the neighbors of that vertex (i.e., vertices 3, 6, and 7) must all be gray' does not follow from the two stated rules alone: a vertex with three same-colored neighbors is forbidden only if the vertex itself has that color, and here the upper a-vertex is assumed white; additional structural arguments are needed to rule out each neighbor being white. Similarly, the assertion 'this forces vertex 5 to be gray' is not justified by the stated rules, since if vertex 5 were white the lower a-vertex would have a bichromatic neighborhood (white neighbor 5, gray neighbors 6 and 7). The proof must give a complete case analysis with explicit adjacencies, or state and prove the automorphisms used in 'the other case is symmetric.' The same figure-dependent style appears in Lemmas 1, 2, 3, 5, and 6, so these proofs need to be made rigorous throughout.","section":"Section 3, Lemma 4 proof"},{"comment":"The proof begins by saying 'we again construct a planar graph H' using the planar embedding of H_phi as a pattern,' but the abstract and Section 6 explicitly leave the planar maximum-degree-5 case open, and the section's own opening says planarity is not needed. Taken literally, the sentence would assert a stronger result that contradicts the paper's stated open problem. The word 'planar' should be removed or replaced with a correct description of the constructed graph.","section":"Section 3, proof of Theorem 2"},{"comment":"The proof asserts that the resulting graph H' 'has maximum vertex degree 5' without any per-vertex degree count. In particular, the description of the linking pattern between clause gadgets is ambiguous: the text says each of the three linking vertices is connected to three 0-labeled vertices and that vertex 2 has two such neighbors on the left and one on the right, with vertices 1 and 3 'opposite,' but this does not specify how many linking vertices are incident to each individual 0-labeled vertex. A 0-labeled vertex in an internal clause gadget is already degree 2 inside its 5- or 6-cycle and may receive connections from both the left and right links; without an explicit adjacency specification one cannot verify that its degree never exceeds 5. The degree bound is a central claim of Theorem 2 and must be established by an explicit count.","section":"Section 3, degree bound in Theorem 2"}],"minor_comments":[{"comment":"The sentence 'All graphs of maximum degree 4 (except for K4) have linear vertex arboricity at most 2' should say 'except for K5,' since K4 has maximum degree 3 and the introduction correctly identifies K5 as the only no-instance among graphs of maximum degree 4.","section":"Abstract"},{"comment":"The formula named 'k-LVA(U)' is a sentence with no free variable U; this notation is confusing and should be changed. In addition, the proof of Theorem 4 should state explicitly that if the input value k is greater than tau+1, the answer is trivially yes, so the formula length can be bounded as a function of the treewidth tau; otherwise the formula length appears to depend on k as an input parameter.","section":"Section 4, MSO2 formulation"},{"comment":"Equation (4) is not symmetric in u and w but is written as a constraint 'for all {u,w} in E(G).' Since {u,w} is an unordered edge, the expression x_{u,v} + x_{v,w} checks only the orientation u < v < w and not w < v < u. Please state explicitly that the constraint is generated for both orientations (or for each ordered pair of adjacent vertices), otherwise the reverse ordering is not excluded.","section":"Section 5, Equation (4)"}],"recommendation":"major_revision","confidential_remarks":"The main issue is likely a typo in the variable-gadget adjacency, but it is load-bearing because Theorem 2 is the paper's headline tight-hardness result. If the corrected construction is supplied and the gadget lemma proofs are made rigorous, the paper could be a good fit. The abstract's 'K4' for 'K5' and the 'planar graph H'' slip in Theorem 2 suggest that the manuscript needs careful proofreading of the degree-5 section."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline result—NP-hardness of 2-Lva at maximum degree 5, tight via Matsumoto—is a real contribution, and the planar degree-6 hardness and treewidth FPT are also new. The FPT via MSO2 is a routine but valid application of Courcelle; the ILP/SAT section is a sensible add-on. I believe the core theorems are probably true, and the gadget design follows the expected template.\n\nBut there is a concrete problem in Section 3 that goes beyond a minor typo. The variable gadget is described as connecting the two a-labeled vertices to both vertices 1 and 2. Under that literal reading, vertices 1 and 2 would have degree 7, destroying the claimed maximum-degree-5 bound and invalidating Theorem 2. Lemma 4's proof, however, treats the upper a-vertex as adjacent to 3, 6, and 7, and the lower a-vertex as forming a triangle with 6 and 7. Those two descriptions are incompatible. The most likely fix is to attach the a-vertices to 6 and 7 instead of 1 and 2, which restores max degree 5 and matches Lemma 4, but as submitted the reduction graph is ambiguous and the degree bound is not established. This is a load-bearing flaw in the write-up, not a cosmetic issue.\n\nThere are also two smaller inconsistencies. The abstract excludes K4 where the introduction and Matsumoto's bound clearly require K5. And Theorem 2's proof says it constructs a planar graph H', which would solve the planar max-degree-5 case that the abstract and Section 6 explicitly leave open. Both look like copy-paste slips, but they should be fixed.\n\nThe gadget lemmas are proved by case analysis with some appeals to symmetry; they seem plausible, but the reliance on figures and informal 'similarly' arguments means the reductions are not fully machine-checkable. That is a minor weakness for a theory paper, not a fatal one.\n\nWho should read this? People working on graph drawing complexity or vertex partition problems will want the degree-5 threshold; the FPT result is standard but useful as a reference. The paper deserves a serious referee—the results are interesting and the errors appear fixable—but it should not be accepted in its current form. I would send it back for major revision, asking the authors to correct the variable gadget description, resolve the K4/K5 and planarity slips, and ideally make the gadget uniqueness proofs more explicit.","headline":"Tight degree-5 hardness for linear vertex arboricity is likely correct, but a load-bearing typo in the variable gadget makes the main construction unverifiable as written.","tokens_in":11981,"tokens_out":5369,"would_cite":true,"duration_ms":42355,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68Q17","68Q27"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that deciding whether a graph's vertices can be split into two path-forests is NP-hard even for graphs of maximum degree 5, that this threshold is tight, and that the problem parameterized by treewidth is fixed-parameter…","keywords":["linear vertex arboricity","weak line cover number","parameterized complexity","NP-hardness","maximum degree","treewidth","fixed-parameter tractability","planar graphs"],"falsifier":"Run an exhaustive search over all 2-colorings of the seven-vertex block $B$, and of the degree-5 variable gadget $V'_a$, with the anchor vertex fixed, and test each color class for the defining property of a linear forest. The paper's Lemmas 1 and 4 predict exactly one legal coloring in each case; any additional legal coloring — for instance, a coloring of $V'_a$ in which the two $a$-labeled vertices receive different colors — would refute the uniqueness lemmas on which the degree-5 reduction relies.","tokens_in":10927,"feed_emoji":"🧩","tokens_out":14522,"duration_ms":110376,"temperature":0.7,"pith_summary":"The paper studies how hard it is to decide whether a graph's vertices can be partitioned into few parts so that each part induces a linear forest — a disjoint union of paths. This number, the linear vertex arboricity, coincides with the minimum number of straight lines needed to cover the vertices of a crossing-free drawing in three dimensions, so its complexity controls a natural measure of drawing visual complexity. The paper establishes that the decision problem for two parts is NP-hard already for graphs of maximum degree 5, and that this is best possible: every graph of maximum degree at most 4, except $K_5$, is already known to have linear vertex arboricity at most 2. For planar graphs the same problem is NP-hard at maximum degree 6, leaving the degree-5 planar case open. On the positive side, for every fixed $k$, deciding whether the linear vertex arboricity is at most $k$ is fixed-parameter tractable with respect to treewidth, via a monadic second-order logic formulation.","feed_headline":"Graph splitting into two path-forests is NP-hard at degree 5","feed_subtitle":"Tight: every graph of maximum degree 4, except K5, can be split into two; planar graphs stay hard at degree 6.","key_machinery":"The machinery is a set of forcing gadgets. The degree-5 reduction is built on the graph $K_5^-$, obtained from $K_5$ by deleting one edge; in any legal 2-coloring its two degree-3 vertices share a color, and exactly one of the remaining triangle vertices shares that color. Variable gadgets, clause gadgets, linking gadgets, and a starter gadget are assembled from copies of this block so that the terminals labeled 0 all receive the same color, each variable's two literal vertices are forced to be equal and opposite to its negation vertex, and each clause's literal vertices cannot all have the wrong color. A satisfying assignment therefore corresponds exactly to a legal 2-coloring of the entire graph. The planar reduction uses a larger seven-vertex triangulated block $B$ with the same forcing behavior. For the treewidth result, the mechanism is a monadic second-order logic (MSO2) formula — logic with quantification over vertex and edge sets — whose predicates express 'connected set', 'set inducing a cycle', 'set containing a star', and 'path forest', and which triggers the metatheorem that MSO2-definable properties are decidable in linear time on bounded-treewidth graphs.","core_discovery":"The paper's central discovery is a sharp complexity threshold at maximum degree 5. It proves that the decision problem $2$-Lva, asking whether the vertices can be colored with two colors so that each color class induces a linear forest, is NP-hard even when the input graph has maximum degree 5, by a polynomial-time reduction from a planar bounded 3-SAT variant. The threshold is tight in a strong sense: a known degree bound shows that every graph of maximum degree at most 4, with the single exception of $K_5$, has linear vertex arboricity at most 2, so those instances are trivially decidable. For planar graphs the reduction gives NP-hardness at maximum degree 6 and leaves degree 5 open. The paper also proves that for every fixed $k$, deciding whether the linear vertex arboricity is at most $k$ is fixed-parameter tractable with respect to treewidth, by expressing the condition as a monadic second-order logic formula and invoking the corresponding linear-time metatheorem.","pith_inferences":["Editorial extension: The planar degree-5 gap may be closable with a different link or starter gadget, because the degree-6 planar reduction becomes degree-6 only in specific connection points.","Editorial extension: The MSO2 formula is short once $k$ is fixed, so an explicit dynamic program over a tree decomposition with an elementary running time is likely attainable for $k$-Lva.","Editorial extension: Because of the known equality between linear vertex arboricity and the 3D weak line cover number, the hardness results transfer to deciding whether a graph can be drawn crossing-free in three dimensions with its vertices covered by two straight lines.","Editorial extension: The same $K_5^-$ forcing block might yield hardness for other degree-bounded vertex-partition problems that forbid a fixed forest-like induced subgraph, although the paper does not explore that direction."],"forward_implications":["The exact value of the linear vertex arboricity is NP-hard to compute for graphs of maximum degree 5, because even distinguishing 2 from larger values is hard.","For graphs of maximum degree at most 4, 2-Lva is trivial: every such graph except $K_5$ is a yes-instance, and $K_5$ is the sole no-instance.","The para-NP-hardness with respect to maximum degree rules out any fixed-parameter algorithm for $k$-Lva parameterized by maximum degree, even for the constant $k = 2$, unless P equals NP.","For every fixed $k$, $k$-Lva is decidable in linear time on any graph class of bounded treewidth, with the running time depending only on treewidth and $k$ through a computable function.","For planar graphs, the maximum-degree-6 case is NP-hard, while the maximum-degree-5 case remains open; the authors report that a computer search found no 3-connected planar graph up to 12 vertices with maximum degree 5 that requires more than two colors."],"supporting_citations":[{"why":"Supplies the degree bound showing that every graph of maximum degree at most 4 except $K_5$ has linear vertex arboricity at most 2, which makes the degree-5 hardness result tight.","marker":"[18]"},{"why":"Provides the NP-hard source problem Clause-Linked-Planar-Exactly-3-Bounded-3-SAT that both reductions start from.","marker":"[12]"},{"why":"The monadic second-order logic metatheorem stating that MSO2-definable graph properties can be decided in linear time on bounded-treewidth graphs, the engine of the FPT result.","marker":"[6,7]"},{"why":"Gives the tree-decomposition approximation algorithm invoked in the FPT proof to apply the MSO2 metatheorem.","marker":"[16]"},{"why":"Established the earlier NP-hardness of 2-Lva in general, which the present paper sharpens to restricted maximum-degree classes and to planarity.","marker":"[3]"}],"fun_headline_variants":["Linear vertex arboricity 2 is NP-hard at max degree 5","Tight NP-hard threshold at degree 5 for path-forest split","2-LVA is NP-hard on degree-5 graphs, easy on degree-4","Hard to split into two linear forests when max degree hits 5"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reductions stand or fall on the claims that each gadget admits exactly one legal two-coloring once an anchor vertex is fixed; those claims are verified by case analysis on diagrams, with some cases handled by symmetry, so any unlisted alternative coloring would break the equivalence between the formula and the graph.","fun_headline_variants_meta":{"raw":{"variants":["Linear vertex arboricity 2 is NP-hard at max degree 5","Tight NP-hard threshold at degree 5 for path-forest split","2-LVA is NP-hard on degree-5 graphs, easy on degree-4","Hard to split into two linear forests when max degree hits 5"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000428,"raw_usage":{"total_tokens":2254,"prompt_tokens":1071,"completion_tokens":1183,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":687,"completion_tokens_details":{"reasoning_tokens":1101}},"tokens_in":687,"tokens_out":1183,"duration_ms":7088,"temperature":1.0,"reasoning_tokens":1101,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:24:11.338301+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an exhaustive search over all 2-colorings of the seven-vertex block $B$, and of the degree-5 variable gadget $V'_a$, with the anchor vertex fixed, and test each color class for the defining property of a linear forest. The paper's Lemmas 1 and 4 predict exactly one legal coloring in each case; any additional legal coloring — for instance, a coloring of $V'_a$ in which the two $a$-labeled vertices receive different colors — would refute the uniqueness lemmas on which the degree-5 reduction relies.","supporting_citations":[{"cited_title":"Bounds for the vertex linear arboricity","cited_arxiv_id":null,"evidence_quote":"Supplies the degree bound showing that every graph of maximum degree at most 4 except $K_5$ has linear vertex arboricity at most 2, which makes the degree-5 hardness result tight."},{"cited_title":"Fellows, Jan Kratochv ´ ıl, Matthias Middendorf, and Frank Pfeiffer","cited_arxiv_id":null,"evidence_quote":"Provides the NP-hard source problem Clause-Linked-Planar-Exactly-3-Bounded-3-SAT that both reductions start from."}],"review_version":1}