{"id":"99038401-5d59-40b1-8508-af18d5c4e7f7","arxiv_id":"2411.14038","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A characterization of direction-monotone spanning trees leads to fixed-parameter polynomial algorithms for shortest monotone spanning trees and to a degree lower bound of 2k.","lead":"This paper studies a new type of spanning tree: a tree on a point set where every path between two vertices is monotone with respect to at least one direction from a given set. It presents algorithms for finding the shortest such tree when the number of allowed directions is fixed, and shows that such trees can have much higher vertex degrees than ordinary minimum spanning trees.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 7's XP claim for MMST(S,k) rests on an unproven exchange argument for k≥3; if the k=2 argument does not extend, the direction-selection algorithm can miss optimal D.","rationale":"The reader's strongest claim correctly identifies Theorem 1's characterization as the fulcrum, and its correctness is credible. The weakest point, as the reader says, is the exchange argument in Theorem 7. I examined whether the k=2 argument extends: for each direction d, the set of directions preserving monotonicity of every d-monotone path is an open sector containing d, so a generic simultaneous perturbation should work, and σ representatives exist by the Goodman-Pollack cell argument. This suggests the gap is fillable, but the paper does not fill it, and the proof of Theorem 7 also conflates 'general position' with 'directions from σ'. Since the XP claim for k≥3 depends on this step, a conditional verdict is appropriate rather than full acceptance. The runtime inconsistency in Theorem 7 is real but does not threaten the XP classification. The characterization proof itself and the k=1,2 algorithms appear sound; I have no independent counterexample.","tokens_in":32145,"tokens_out":29410,"duration_ms":282813,"concrete_test":"Supply the missing exchange lemma for k=3 and verify it computationally: for every point set S with n≤8, enumerate all optimal direction triples by brute force over a fine angular discretization, and check that each resulting D-monotone tree is also D'-monotone for some triple D' from the Goodman-Pollack sequence σ with S in D'-general position. If any optimal tree is missed by σ, Theorem 7 is false. Independently, recompute the runtime product in Theorem 7; the described enumeration gives O(n^{4k-1} log n), not O(n^{2k(2k-1)} log n).","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix C, Theorem 7, asserts: 'By using an exchange argument as in the proof of Theorem 6, it can be proven that it is sufficient to restrict ourselves to sets D of k directions for which S is in D-general position.' The algorithm then enumerates only direction sets drawn from the Goodman-Pollack sequence σ. The cited Theorem 6 proof covers k=2 only: it perturbs one non-general direction while keeping the other fixed. For k≥3, no proof is given that (i) a simultaneous perturbation of all k directions preserves D-monotonicity of an optimal tree, and (ii) a representative from σ can replace each perturbed direction without losing optimality. This is the load-bearing step for the abstract's claim that MMST(S,k) is in XP for every k: if the exchange argument fails, the search over σ is incomplete and the returned tree may be suboptimal. The gap is probably repairable - for each d, intersect the open monotonicity intervals of all paths that are d-monotone and choose a generic direction in the intersection - but the paper does not supply this argument. A separate, non-load-bearing arithmetic slip: C(h,k)·O(n^{2k-1}) = O(n^{4k-1} log n), not the stated O(n^{2k(2k-1)} log n).","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the minimum monotone spanning tree problem. For a point set S and a set D of directions, a spanning tree is D-monotone if the unique path between every pair of vertices is monotone with respect to some direction in D. The central contribution is a structural characterization (Theorem 1) of D-monotone spanning trees in terms of wedge sets of leaf paths, branches, and disjointness conditions. Using this characterization, the authors give an XP algorithm for MMST(S,D) parameterized by |D|, an O(n^2)-time algorithm for |D|=2, algorithms for MMST(S,k) for k=1 and k=2, an XP algorithm for general k, and a construction showing that minimum k-directional monotone spanning trees can have degree 2k, in contrast to the degree bound 6 for Euclidean MSTs. The proofs are largely self-contained, with several details deferred to appendices.","tokens_in":32397,"tokens_out":7785,"duration_ms":77371,"significance":"If the results are correct, the paper contributes a reusable structural characterization of D-monotone spanning trees and establishes exact complexity-theoretic upper bounds (XP) for natural parameterized geometric optimization problems. The algorithms are deterministic and are derived from the characterization rather than from heuristic fitting or numerical search, which is a strength. The degree-2k construction is a clean and explicit counterpoint to the bounded-degree property of classical Euclidean MSTs. The main caveat is that the XP claim for MMST(S,k) with k >= 3 depends on an unproven exchange argument in the proof of Theorem 7; this part of the paper needs to be completed or corrected before the advertised result can be considered established.","major_comments":[{"comment":"The step limiting the search to k-tuples of directions from the Goodman-Pollack sequence sigma is not proved for k >= 3. The proof says only: \"By using an exchange argument as in the proof of Theorem 6, it can be proven that it is sufficient to restrict ourselves to sets D of k directions for which S is in D-general position.\" Theorem 6 covers only k = 2 and perturbs one direction while keeping the other fixed. For k >= 3 one must show that an optimal D-monotone tree T remains D'-monotone under a simultaneous perturbation D' of all k directions, and that each perturbed direction can be replaced by a direction from sigma without increasing the optimum. This is load-bearing because the abstract claims that MMST(S,k) is in XP for every k. The gap appears repairable, e.g., by intersecting the open monotonicity intervals of all paths in T and selecting generic directions with representatives in sigma, but the argument must be supplied in full.","section":"Appendix C, proof of Theorem 7"},{"comment":"The stated running time is arithmetically inconsistent with the proof. The proof applies Theorem 2, which has running time O(f(k) * n^{2k-1} log n), to each of the C(h,k) = O(n^{2k}) direction sets obtained from sigma, yielding O(f(k) * n^{4k-1} log n) after absorbing h = O(n^2). The paper instead claims O(f(k) * n^{2k(2k-1)} log n). The corrected bound is still in XP, but the stated complexity should be fixed.","section":"Appendix C, Theorem 7"},{"comment":"The induction step in the proof of the converse direction of Theorem 1 asserts that if both the leading and trailing wedges of W_{P_m} change when passing to W_{P_{m+1}}, then |W_{B_{b_{m+1},b_m}}| > k. This is plausible but is stated without a formal argument, and it is essential for the characterization on which all subsequent algorithms rest. Please expand this step so that the reader can verify the wedge counting in the case analysis, especially with respect to the orientation of the branch B_{b_m,b_{m+1}}.","section":"Theorem 1, proof of converse direction"}],"minor_comments":[{"comment":"In the last paragraph of the proof, the expression \"W_{P_m}(b_m) \\subset W_{b_m,b_{m+1}}(b_m)\" appears to contain a typographical error: W_{b_m,b_{m+1}} is not defined, and the intended set is presumably W_{b_m \\setminus b_{m+1}}. Please correct the subscript.","section":"Theorem 1, proof of converse direction"},{"comment":"The final sentence of the proof says \"it is sufficient to restrict ourselves to sets D of k directions for which S is D-monotone.\" This should read \"S is in D-general position,\" since the former is a property of trees, not of point-direction pairs.","section":"Appendix C, Theorem 7"},{"comment":"There is a typo in the sentence \"The assignment A of the wedges of WD to the leaves of H defines, for each leaf path, a reagion that must contain it.\" Replace \"reagion\" with \"region.\"","section":"Appendix B, proof of Lemma 11"}],"recommendation":"major_revision","confidential_remarks":"The single blocking issue is the missing exchange argument in Theorem 7 for k >= 3. Since the abstract and the contribution list explicitly claim XP for every k, this cannot be left as a pointer to a prior proof that only covers k = 2. If the authors can provide the missing argument, or alternatively restrict the claim to k <= 2 and state the general case as open, the paper would be in good shape. The arithmetic slip in the stated runtime of Theorem 7 should also be corrected, and the minor typographical issues are straightforward to fix."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the paper is worth reading and worth sending to a referee. It introduces a new problem (minimum D-monotone spanning trees), gives a structural characterization, and backs it with XP algorithms and a degree lower bound. The main thing to check is Theorem 7: the proof of the k>=3 direction-selection step is incomplete, and the stated running time has an arithmetic slip.\n\nWhat's genuinely new: the problem as posed — unrooted trees, arbitrary finite direction sets — is not in the earlier rooted/uniform work of Mastakas and Symvonis. The characterization in Theorem 1 (leaf paths and branches D-monotone, pairwise disjoint wedge sets, and region disjointness for branches/leaf paths) is a real structural insight. Based on it, the prescribed-D algorithm in Theorem 2 is clean, and the k=1 and k=2 results look correct; the O(n^2) speed-up for two directions is nontrivial. The degree lower bound (a 2k-star for every even k) is a nice contrast to the Euclidean MST's degree-6 bound. The paper is generally careful with its geometric lemmas; Lemma 6, Lemma 8, and Lemma 9 are properly proved in the appendix.\n\nThe soft spots are concentrated in Theorem 7. The proof says 'By using an exchange argument as in the proof of Theorem 6, it can be proven...' but Theorem 6 only perturbs one direction while holding the other fixed. For k >= 3 you need to perturb several directions, and the paper doesn't show that the perturbations can be chosen compatibly (or that a representative from the Goodman-Pollack sequence exists after all k perturbations). I think the gap is repairable — intersect, for each direction, the open monotonicity intervals of the paths that use it, then pick a generic direction in the intersection — but the paper doesn't supply that argument, and it's load-bearing for the claim that MMST(S,k) is in XP for every k. The same theorem also has an arithmetic slip: C(h,k) * O(n^{2k-1} log n) is O(n^{4k-1} log n), not O(n^{2k(2k-1)} log n). This doesn't affect the XP classification, but the stated bound is wrong. There is also a small typo in the proof ('S is D-monotone' probably should be 'S is in D-general position').\n\nThe characterization and the k=1, k=2 algorithms appear correct; I didn't find defects in them. The citation pattern is fine; the paper builds on the rooted monotone MST literature honestly.\n\nRecommendation: send it to peer review. It's a solid paper that a good referee can work with. Ask the authors to write out the exchange argument for k>=3 and fix the running time. I'd cite the characterization and the degree bound in my own work.","headline":"New problem, a real structural characterization, and XP algorithms with a fixable gap at k>=3; worth a serious referee.","tokens_in":32947,"tokens_out":7429,"would_cite":true,"duration_ms":60396,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68U05","05C05","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"For any fixed set of directions, the shortest spanning tree whose every path is monotone can be computed in polynomial time; for two directions, in quadratic time.","keywords":["monotone spanning tree","D-monotone tree","minimum spanning tree","monotone drawing","computational geometry","XP algorithm","homeomorphically irreducible tree","vertex degree bound"],"falsifier":"Run an exhaustive search over all small point sets in general position with, say, six points and $k=2$ or $k=3$: check whether the spanning trees satisfying conditions (a)–(c) of Theorem 1 are exactly the $D$-monotone spanning trees, and whether the best tree over all $k$-direction sets is matched by the best tree using only directions from slopes of point pairs. A single mismatch in either test would refute the characterization or the direction-restriction claim on which the XP algorithms rest.","tokens_in":31955,"feed_emoji":"🌲","tokens_out":20716,"duration_ms":175131,"temperature":0.7,"pith_summary":"Minimum spanning trees are classically easy to compute, but this paper adds a geometric constraint: every path between two vertices must be monotone, meaning the vertices appear in the same order as their projections on a line, with the direction of monotonicity chosen from a prescribed set $D$. The paper proves a structural characterization of such $D$-monotone spanning trees and uses it to show that a shortest one can be found in polynomial time for any fixed number of directions, and in quadratic time for two directions. When the direction set is not prescribed, choosing the best $k$ directions is also polynomial for every fixed $k$, with explicit $O(n^2 \\log n)$ and $O(n^6)$ algorithms for $k=1$ and $k=2$. The paper also shows that monotonicity can force large degree: for every even $k$ there is a point set whose unique shortest $k$-monotone spanning tree is a star of degree $2k$, in contrast to the classical Euclidean minimum spanning tree, whose degree is at most six.","feed_headline":"Shortest monotone spanning tree is tractable for fixed direction sets","feed_subtitle":"A characterization reduces the search to finitely many tree shapes; algorithms run in quadratic time for 2 directions.","key_machinery":"The machinery is the decomposition of a $D$-monotone spanning tree into leaf paths and branches, each carrying a wedge set. With $k$ directions, the lines through a point perpendicular to those directions cut the plane into $2k$ wedges; the wedge set of a directed path is the smallest consecutive block of wedges containing all directions that path travels in. Two derived objects do the work: $W_{u\\setminus v}(u)$, the wedge region of the subtree at $u$ that avoids $v$, and $R_{u,v}$, the region of the branch or leaf path between $u$ and $v$. Theorem 1 makes monotonicity equivalent to three conditions on these objects, Lemma 11 shows that a fixed tree shape, vertex mapping, and wedge assignment determine a unique candidate tree in $O(n \\log n + nk + k)$ time, and a counting lemma bounds the number of homeomorphically irreducible trees (embedded trees with no degree-2 vertices) with at most $\\ell$ leaves by $O(7^\\ell \\ell!)$.","core_discovery":"The central claim is a characterization (Theorem 1): a spanning tree $T$ of a point set $S$ is $D$-monotone if and only if (a) every leaf path and every branch of $T$ is $D$-monotone, (b) the wedge sets of any two leaf paths are disjoint, and (c) for every branch or leaf path $P_{u,v}$, the region $R_{u,v}$ of that path is disjoint from the wedge region $W_{u\\setminus v}(u)$ of the subtree hanging from $u$ away from $v$. This turns a condition on every pair of vertices into local conditions on $O(k)$ paths, which is what makes enumeration feasible. The paper argues that once a tree shape, a mapping of branching vertices to points, and an assignment of the $2k$ wedges to leaves are fixed, the optimal tree is unique and can be built in near-linear time by sorting points along two boundary directions. Enumerating shapes, mappings, and wedge assignments yields the XP algorithm for a prescribed direction set, and applying that over direction sets drawn from the slopes of point pairs yields the XP algorithm for choosing $k$ directions.","pith_inferences":["The characterization suggests a recognition algorithm the paper does not spell out: a given geometric spanning tree can be checked for $D$-monotonicity by testing the $O(k)$ conditions (a)–(c) rather than all vertex pairs.","The degree-$2k$ lower bound hints that monotone trees behave like hub-and-spoke structures under restricted direction sets, which could matter for routing or network design where paths must be non-backtracking; the paper does not explore applications.","A natural stress test for the XP algorithm is to compare the length of the shortest $k$-monotone spanning tree with the ordinary Euclidean MST on random point sets; the paper gives no computational data, and the gap should grow with $k$ and with anisotropy of the point distribution.","The XP results leave open whether the direction-choice problem stays polynomial when $k$ is part of the input; the next target is to prove NP-hardness for variable $k$ or to find a fixed-parameter-tractable algorithm."],"forward_implications":["For every fixed $k$, both versions of the problem — directions prescribed or directions chosen — can be solved in polynomial time, with exponents linear in $k$ for the prescribed case and quadratic in $k$ for the chosen case.","A $D$-monotone spanning tree has at most $2k$ leaves and maximum degree at most $2k$, so the enumeration over tree shapes is finite and the degree bound is tight in the worst case.","For two prescribed directions, the minimum $D$-monotone spanning tree can be found in $O(n^2)$ time, improving the generic $O(n^3 \\log n)$ bound for that case.","For choosing one direction, the optimum is a monotone spanning path, computable in $O(n^2 \\log n)$ time by sweeping the circular sequence of directions defined by slopes of point pairs.","The shortest $k$-monotone spanning tree can be forced to have a vertex of degree $2k$, so monotonicity, unlike the Euclidean MST property, does not keep degrees small."],"supporting_citations":[{"why":"It supplies the sector-of-directions characterization of monotone paths that Theorem 1 and the algorithms build on.","marker":"[4]"},{"why":"It gives the circular sequence of directions defined by point-pair slopes, which the $k=1$ algorithm and the direction-selection algorithm enumerate.","marker":"[26]"},{"why":"It bounds and enumerates homeomorphically irreducible trees, limiting the number of tree shapes the XP algorithm must try.","marker":"[29]"},{"why":"It provides constant-time convex intersection tests used in Lemma 11 to check condition (c) of the characterization.","marker":"[13]"},{"why":"It supplies the sine-sum identity that evaluates the length of the forced path in the degree-$2k$ construction.","marker":"[34]"},{"why":"It supplies the trigonometric inequality used to prove that the forced path is longer than the star, establishing the degree lower bound.","marker":"[41]"},{"why":"It gives the classical degree-at-most-six bound for Euclidean MSTs that the degree-$2k$ result contrasts with.","marker":"[46]"}],"fun_headline_variants":["Fixed direction sets make shortest monotone tree tractable","Quadratic time for two-direction monotone spanning trees","Monotone spanning trees: XP parameterized by direction count"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that, for $k \\ge 3$, no optimal direction set is lost by restricting to directions taken from the finite list of slopes of lines through pairs of input points and by perturbing the points into general position; the paper states that an exchange argument proves this, but does not supply the argument.","fun_headline_variants_meta":{"raw":{"variants":["Fixed direction sets make shortest monotone tree tractable","Quadratic time for two-direction monotone spanning trees","Monotone spanning trees: XP parameterized by direction count"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000804,"raw_usage":{"total_tokens":3617,"prompt_tokens":1115,"completion_tokens":2502,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":731,"completion_tokens_details":{"reasoning_tokens":2450}},"tokens_in":731,"tokens_out":2502,"duration_ms":21149,"temperature":1.0,"reasoning_tokens":2450,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:36:01.362453+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an exhaustive search over all small point sets in general position with, say, six points and $k=2$ or $k=3$: check whether the spanning trees satisfying conditions (a)–(c) of Theorem 1 are exactly the $D$-monotone spanning trees, and whether the best tree over all $k$-direction sets is matched by the best tree using only directions from slopes of point pairs. A single mismatch in either test would refute the characterization or the direction-restriction claim on which the XP algorithms rest.","supporting_citations":[{"cited_title":"Monotone drawings of graphs","cited_arxiv_id":null,"evidence_quote":"It supplies the sector-of-directions characterization of monotone paths that Theorem 1 and the algorithms build on."},{"cited_title":"Robinson, and Allen J","cited_arxiv_id":null,"evidence_quote":"It bounds and enumerates homeomorphically irreducible trees, limiting the number of tree shapes the XP algorithm must try."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the sine-sum identity that evaluates the length of the forced path in the degree-$2k$ construction."},{"cited_title":"Mitrinovi´ c","cited_arxiv_id":null,"evidence_quote":"It supplies the trigonometric inequality used to prove that the forced path is longer than the star, establishing the degree lower bound."},{"cited_title":"Papadimitriou and Umesh V","cited_arxiv_id":null,"evidence_quote":"It gives the classical degree-at-most-six bound for Euclidean MSTs that the degree-$2k$ result contrasts with."}],"review_version":1}