{"id":"2dc217e5-e991-4a7a-a3c7-7246107c9081","arxiv_id":"2607.08183","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Covering points by boundaries of axis-parallel rectangles is NP-complete in the free-placement setting, W[1]-hard when rectangles are preset, and fixed-parameter tractable in the solution size k.","lead":"This paper introduces a new geometric covering problem: every point must lie exactly on the boundary of an axis-parallel rectangle, not inside it. It maps out which versions stay solvable when few rectangles are allowed, giving NP-hardness and fixed-parameter tractability results.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's running-time bound is unsupported: Lemma 49 multiplies per-line guesses incorrectly (k^{O(k)} per line over 4k lines gives k^{O(k^2)}, not k^{O(k)}), and no global bound on exceptional points is given to restore 2^{O(k log k)}.","rationale":"The reader's conditional verdict is appropriate, but the specific weakest assumption they chose — left-side monotone functions in the CSP — is a syntactic issue that is straightforwardly repairable by introducing auxiliary variables for each function application, as the paper already does implicitly for other values. The more serious obstacle to the central claim is the counting error in Lemma 49, which invalidates the precise running time 2^{O(k log k)} stated in Theorem 4. The FPT membership itself may survive with a slower f(k), since k^{O(k^2)} n^{O(1)} is still FPT, so the verdict should remain CONDITIONAL rather than REJECT. The check I propose is analytic: recompute the product of per-line guesses and test whether a global bound on exceptional incidences exists. This is a concrete, decisive test of whether the headline complexity is correct as stated.","tokens_in":36258,"tokens_out":9685,"duration_ms":94902,"concrete_test":"Re-derive the total number of global guesses in Section 6.12 by explicitly multiplying the per-line bounds over all |ImpLines| ≤ 4k lines. Then check whether the sum over all lines of the guessed exceptional-point counts K(σ,λ) is necessarily O(k). Construct a point set with k rectangles where one vertical side crosses 4k horizontal ImpLines and contributes one exceptional point on each line; if such a configuration is feasible, the product of exceptional-pattern choices alone is (2k)^{Θ(k^2)}, contradicting Lemma 49's k^{O(k)} total. If a global O(k) bound on exceptional incidences can be proven, the theorem's running time may be salvageable; otherwise the stated exponent must be weakened to 2^{O(k^2 log k)}.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is the FPT running time 2^{O(k log k)} n^{O(1)} for BCCAPR. The proof of that bound rests on Lemma 49, which counts global guesses. For each of the at most 4k lines in ImpLines, the paper allows per-line choices bounded by k^{O(k)} (endpoint orderings, gap vectors, exceptional patterns). Multiplying over the lines gives (k^{O(k)})^{4k} = k^{O(k^2)} = 2^{O(k^2 log k)}, not k^{O(k)} as written. This is not a typo only: the per-line exceptional-pattern count is individually k^{O(k)} because K(σ,λ), the number of exceptional points on a line, can be as large as 2k, and there is no argument bounding the sum of K(σ,λ) over all lines by O(k). In fact, a single rectangle side can be exceptional on many horizontal ImpLines (one point per line), so the total number of exceptional incidences can be Θ(k^2). Consequently the number of guesses can be 2^{Θ(k^2 log k)}, which is still FPT but does not match the theorem's stated exponent. The reader's concern about left-side monotone functions in the CSP is real but easily repaired by introducing auxiliary variables; the counting error directly affects the headline complexity and is therefore the more load-bearing issue.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies boundary covering, where every input point must lie on the boundary of at least one chosen axis-parallel rectangle. It introduces BCDAPR, the discrete variant in which rectangles are chosen from a given family, and proves W[1]-hardness in the parameter k by a reduction from 3-Regular 2-CSP. It then studies BCCAPR, the continuous variant with freely placed rectangles. NP-completeness of BCCAPR is claimed via an intermediate NP-completeness proof for covering points by axis-aligned L-shapes. The paper's main algorithmic claim is an FPT algorithm for BCCAPR with running time 2^{O(k log k)} n^{O(1)}, obtained by enumerating skeletons, endpoint orderings, gap vectors, and exceptional patterns, and reducing each branch to a Distinct Domain Monotone 2-CSP instance solvable in polynomial time.","tokens_in":36528,"tokens_out":12563,"duration_ms":120787,"significance":"If correct, the paper would establish an interesting contrast: discrete rectangle-boundary covering is W[1]-hard while the continuous version is NP-hard yet fixed-parameter tractable for small k. The idea of compressing the geometric interaction into a small number of 'important lines' and then using monotone 2-CSP as a polynomial-time backend is appealing and potentially reusable. The L-shape gadget in Section 5 is also a nice contribution. However, as written the paper contains load-bearing problems in the W[1]-hardness reduction, in the formal validity of the produced CSP instances, and in the running-time count. These issues affect the two main theorems and must be repaired before the paper can be accepted.","major_comments":[{"comment":"With the natural unit-spaced placement of the points aL_j and aB_j on the square sides, the bottom side of BL_p is the segment from the left side of the square to aB_{p+1}. The constraint points beta^{(ij)}_p are placed between aB_p and aB_{p+1}, so they lie on the bottom side of BL_p and are covered by the variable rectangle selected for assignment a_p. This contradicts the assertion in Lemma 10 that exactly three constraint points are 'not covered by the selected variable rectangles'. Since the soundness argument uses this uncoveredness to force the selected constraint rectangle to match the variable assignment, the reduction as written does not establish Theorem 9. A modified gadget that keeps the beta points off all four selected variable-rectangle sides is needed.","section":"Section 4.1, variable gadget and Lemma 10"},{"comment":"The definition of Distinct Domain Monotone 2-CSP in Section 3.2 allows only constraints of the form z_i ⋄ f(z_j), with the monotone function applied to the right-hand variable. However, the constructed gap constraints include A_h(coord_h(e_first)) = GapFn(1), A_h(coord_h(e_next^r)) = B_h(coord_h(e_end^r)) + GapFn(r+1), and the symmetric B_h constraints, where the monotone prefix-count functions A_h and B_h are applied to left-hand expressions. These are not of the allowed form. The assertion at the end of Section 6.11 that every constraint is of the form z ⋄ f(z') is therefore false. The issue is repairable by introducing auxiliary variables to hold the values A_h(...) and B_h(...), but as written Proposition 8 is applied to objects that may not be valid CSP instances.","section":"Section 6.10, constraints (H2), and end of Section 6.11"},{"comment":"The running-time bound is arithmetically incorrect. Lemma 46 gives k^{O(k)} exceptional-pattern choices per line (because K can be as large as 2k, and each of the K exceptional points has up to 2k choices of rectangle and side). Lemma 37 gives up to (2k)! endpoint orderings per line. Combining the per-line choices over up to 4k lines yields at most (k^{O(k)})^{4k} = k^{O(k^2)} = 2^{O(k^2 log k)} global guesses, not k^{O(k)} as claimed at the end of Lemma 49. The proof would need a global bound on the total number of exceptional incidences over all lines, or a per-line bound of 2^{O(k)}, to justify the advertised 2^{O(k log k)} running time. The algorithm would still be FPT with the weaker bound, but the paper's headline exponent is unsupported as written.","section":"Section 6.12, Lemma 49"}],"minor_comments":[{"comment":"The sentence 'by the pigeonhole principle, at least one of |C* ∩ Vvert| or |C* ∩ Vhor| must exceed 2k' is false in general when |C*| > 4k; the two parts could be 3k and k. The lemma's conclusion can be justified directly from the fact that any k-rectangle solution induces a vertex cover of size at most 4k, so the pigeonhole remark should be removed or rewritten.","section":"Section 6.2, Lemma 26"},{"comment":"The text says the total running time is k^{O(k)} · n^{O(1)} while also saying each CSP instance is solved by Proposition 8. For clarity, the proof should explicitly state that the polynomial-time CSP solver is run on each branch and that its cost is included in the n^{O(1)} factor.","section":"Section 6.12, Lemma 49"},{"comment":"The manuscript contains several formatting and typographical artifacts: 'envel⌢pe' in the author affiliation, duplicated Proposition 6/8 numbering, 'CVIT 2016' running headers, and inconsistent use of notation such as 2^{O(klogk)}. These should be corrected in revision.","section":"Throughout"},{"comment":"NP membership of BCCAPR is asserted for rectangles with real coordinates. Since Lemma 25 guarantees a grid-aligned optimal solution, coordinates can be taken from the input point coordinates; this justification should be stated explicitly before Theorem 24.","section":"Section 5.5, Theorem 24"},{"comment":"The paper relies on [1] for the polynomial-time algorithm for Distinct Domain Monotone 2-CSP. Since two authors of the present paper are also authors of [1], a short self-contained proof or at least a precise statement of the algorithm's invariant would strengthen the presentation and make the reduction self-contained.","section":"Section 3.2, Proposition 8"}],"recommendation":"major_revision","confidential_remarks":"The paper has interesting ideas, especially the boundary-covering formulation and the L-shape reduction, but the current version is not publishable as is. The W[1]-hardness gadget appears to cover rather than expose the constraint points, which would invalidate Theorem 1 as written; this needs a concrete coordinate check by the authors. The FPT running-time count and the CSP-form validity are also in need of repair. I would encourage the authors to revise; these issues seem fixable, but the W[1]-hardness construction may require a genuinely different gadget design."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth sending to referees, but not acceptable as is. The paper defines a natural boundary-covering variant for axis-parallel rectangles, proves W[1]-hardness for the discrete version, NP-completeness for L-shapes and continuous rectangles, and gives an FPT algorithm for the continuous case. The NP-hardness reductions are well-structured; the L-shape-to-rectangle guard argument is clean, and using Distinct Domain Monotone 2-CSP as a target is a nice idea. The overall algorithmic strategy is plausible and worth engaging with.\n\nThere are two load-bearing problems. First, the W[1]-hardness gadget: with the rectangle definitions as written, the constraint points between a_p and a_{p+1} on the bottom side of the variable square are covered by the selected variable rectangle BL_p (and RB_p), because BL_p's bottom side runs through that interval. Lemma 10's soundness argument depends on those points being uncovered, so the proof of Theorem 1 is incorrect as written. This looks like an off-by-one indexing error in the definitions of BL_j and RB_j; swapping the indices would create the intended gap. But as printed, the W[1]-hardness proof is not valid.\n\nSecond, the FPT running time: Lemma 49 multiplies per-line guesses over up to 4k lines, and each line has k^{O(k)} choices, giving k^{O(k^2)} = 2^{O(k^2 log k)} global guesses, not 2^{O(k log k)}. The paper gives no global O(k) bound on exceptional points, and in fact a single rectangle side can be exceptional on many ImpLines, so the total number of exceptional incidences can be quadratic. Thus Theorem 4's stated running time is unsupported. The algorithm may still be FPT with a worse exponent, but the headline bound needs either a correct global counting argument or a revised statement.\n\nThe CSP syntax issue the reader flagged is real but minor: several constraints apply monotone functions to the left-hand variable, e.g., A_h(coord_h(e_first)) = constant, which is outside the stated syntax. That is easily repaired with auxiliary constant variables and by rewriting constraints as z_i ≥ f(z_j).\n\nBottom line: the paper deserves a serious referee, but it needs major revision before I would trust the theorems. The new problems and the high-level approach are solid enough that the work should not be desk-rejected.","headline":"Interesting boundary-covering paper with a promising FPT/NP-hardness split, but the W[1]-hardness gadget has an off-by-one coverage bug and the claimed 2^{O(k log k)} running time does not follow from the proof as written.","tokens_in":37075,"tokens_out":11740,"would_cite":true,"duration_ms":104921,"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":"Boundary covering of points by freely placed axis-parallel rectangles is fixed-parameter tractable when parameterized by the number of rectangles, even though the problem is NP-complete.","keywords":["boundary covering","axis-parallel rectangles","fixed-parameter tractability","W[1]-hardness","NP-completeness","Distinct Domain Monotone 2-CSP","L-shape cover","geometric covering"],"falsifier":"Take a small Yes-instance (for example, four points forming a unit square with k=1), run the Section 6 reduction, and inspect the generated CSP: if any constraint has the form f(z_i) = z_j or f(z_i) ≤ z_j with a non-identity monotone function on the left, the instance is not a valid Distinct Domain Monotone 2-CSP as defined, and the paper's appeal to the polynomial-time algorithm is incomplete without additional argument.","tokens_in":36085,"feed_emoji":"📐","tokens_out":8585,"duration_ms":75017,"temperature":0.7,"pith_summary":"The paper studies boundary covering: given a set of points in the plane, cover every point with the boundary (not the interior) of at most k axis-parallel rectangles. It proves that the discrete variant, where rectangles must be chosen from a given family, is W[1]-hard, so no algorithm of the form f(k) n^{O(1)} is expected under standard complexity assumptions. For the continuous variant, where rectangles may be placed anywhere, it proves NP-completeness but then gives a fixed-parameter algorithm with running time 2^{O(k log k)} n^{O(1)}. The algorithm guesses a small structural skeleton of the rectangle–point interaction, then reduces the remaining geometry to a polynomial-time-solvable constraint satisfaction problem. This matters because it draws a clean complexity line: the problem is as hard as any NP problem in general, yet becomes quickly solvable when the allowed number of rectangles is small.","feed_headline":"Boundary covering by rectangles is tractable for small k","feed_subtitle":"Even though the problem is NP-complete, an algorithm runs in 2^{O(k log k)} n^{O(1)} time.","key_machinery":"The core mechanism is the reduction to Distinct Domain Monotone 2-CSP: a constraint satisfaction problem where each variable has its own finite numeric domain and every constraint compares a variable to a monotone function of another variable (e.g., x ≤ f(y)). To make the reduction, the algorithm guesses a 'skeleton' — a mapping of each of the 4k rectangle sides to one of the at most 4k distinguished lines (or to a free/unassociated value) — then guesses the left-to-right order of endpoints on each line, counts how many exceptional points fall into each gap between balanced-parentheses blocks of that order, and assigns each exceptional point to a covering vertical or horizontal side. These g","core_discovery":"The central claim is that continuous axis-parallel rectangle boundary covering is fixed-parameter tractable parameterized by the number k of rectangles. The proof works by discretizing coordinates to grid lines, computing a set of at most 4k lines that together contain all input points, guessing a skeleton that specifies which rectangle side lies on which of these lines (or is unaligned), and then encoding the remaining feasibility as a Distinct Domain Monotone 2-CSP, a class with a polynomial-time algorithm. The paper also establishes NP-completeness of the continuous problem through an intermediate hardness proof for axis-aligned L-shapes, and W[1]-hardness of the discrete version.","pith_inferences":["The skeleton-and-CSP approach is likely reusable for other axis-parallel boundary-covering families, such as squares or rectangles with a fixed aspect ratio, because the core steps (grid discretization, few covering lines, endpoint orderings) do not rely on rectangles having arbitrary side lengths.","The NP-completeness of L-shape cover hints that boundary covering is sensitive to the shape family: covering by lines is polynomial-time solvable, while covering by L-shapes or rectangles is NP-complete, so one could test other simple shapes for a similar dichotomy.","A direct check of the reduction is whether every generated CSP constraint has the declared form z_i ⋄ f(z_j) with the function on the right; if some constraints place monotone counting functions on the left, a minor repair with auxiliary variables would be needed to keep the polynomial-time solver applicable."],"forward_implications":["A Yes-instance with n points and k rectangles can be solved in time 2^{O(k log k)} n^{O(1)}, making the problem practical when k is small, up to roughly log n / log log n.","The discrete variant BCDAPR is W[1]-hard, so no fixed-parameter algorithm exists for it under the standard FPT ≠ W[1] assumption.","The continuous problem is NP-complete, so no polynomial-time algorithm for arbitrary k is expected; the FPT result shows the hardness is concentrated in the dependence on k.","Boundary covering by axis-aligned L-shapes is NP-complete, and the reduction from L-shapes to rectangles shows that fairly simple geometric families already produce hard boundary-covering problems."],"fun_headline_variants":["Continuous rectangle boundary covering is FPT","NP-complete yet FPT: rectangle boundary covering","Rectangle boundary covering: FPT algorithm for k rectangles","Cover points on rectangle edges in FPT time"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The FPT algorithm depends on the polynomial-time solver for Distinct Domain Monotone 2-CSP applying to the instances it builds, but the reduction in Section 6.10 generates constraints such as A_h(coord_h(e_first)) = GapFn(1) where a monotone counting function appears on the left-hand side, a form the paper's CSP definition does not allow.","fun_headline_variants_meta":{"raw":{"variants":["Continuous rectangle boundary covering is FPT","NP-complete yet FPT: rectangle boundary covering","Rectangle boundary covering: FPT algorithm for k rectangles","Cover points on rectangle edges in FPT time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002142,"raw_usage":{"total_tokens":8235,"prompt_tokens":916,"completion_tokens":7319,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":660,"completion_tokens_details":{"reasoning_tokens":7260}},"tokens_in":660,"tokens_out":7319,"duration_ms":47278,"temperature":1.0,"reasoning_tokens":7260,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T07:56:04.276985+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small Yes-instance (for example, four points forming a unit square with k=1), run the Section 6 reduction, and inspect the generated CSP: if any constraint has the form f(z_i) = z_j or f(z_i) ≤ z_j with a non-identity monotone function on the left, the instance is not a valid Distinct Domain Monotone 2-CSP as defined, and the paper's appeal to the polynomial-time algorithm is incomplete without additional argument.","supporting_citations":[],"review_version":2}