{"id":"c0ef7321-13f0-4f7f-b357-e77124570f63","arxiv_id":"2510.16236","paper_version":3,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Claims polynomial-time algorithms for maximum edge open packing on proper interval, block, and split graphs, but the algorithms as written are incomplete or not polynomial.","lead":"The paper gives algorithms for the edge open packing number on three subclasses of chordal graphs: proper interval, block, and split graphs. The split-graph formula is simple and likely correct, but the claimed polynomial-time algorithms have serious gaps in their pseudocode and complexity analysis.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1 for proper interval graphs is exponential without memoization, so the claimed polynomial-time algorithm is not established.","rationale":"The reader's stated weakest assumption concerns the missing monotonicity of l(v_i) in Lemma 4, and the undefined ρ^o_e(G^B_v) in the block graph DP. Both are real gaps. However, the more decisive issue for the proper interval graph result is that Algorithm 1, as written, is exponential because it lacks memoization. The recursion tree on a path graph already gives exponential branching, independent of the monotonicity lemma. This directly contradicts the claimed polynomial-time algorithm and Theorem 6. The split-graph characterization appears sound, though the abstract/body runtime discrepancy remains a separate flaw. My read confirms the rejection: the central algorithmic claims for proper interval and block graphs are not established. I do not see a need to change the reader's REJECT verdict; hence UNCHANGED.","tokens_in":13516,"tokens_out":8393,"duration_ms":66314,"concrete_test":"Implement Algorithm 1 exactly as written (no memoization) and run it on path graphs P_n for n=1..30, counting the number of recursive calls to MaxEOP PIG. If the count grows exponentially (e.g., T(n)/T(n-1) > 1.4 for large n), the claimed polynomial-time algorithm fails. Alternatively, derive the recurrence T(n)=T(n-1)+T(n-3)+T(n-4)+O(n) for P_n and show its solution is exponential.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing concern is that Algorithm 1 (MaxEOP PIG), the entire basis for the claimed polynomial-time proper interval graph result, is not polynomial as written. It makes un-memoized recursive calls at lines 5, 9, and 14. For a path P_n with BCO v1,...,vn, l(v_i)=i+1, so k=2; the recursion calls MaxEOP PIG on G[v4..vn] (via H_2), on G[v5..vn] (via G^3_2), and on G[v2..vn] (via G'). The number of calls T(n) satisfies T(n) ≥ T(n-1)+T(n-3)+T(n-4), whose solution is exponential. Thus the algorithm's runtime is not O(n^2), and the proof of Theorem 6 ('runs in polynomial time') is false for the given pseudocode. This is not a missing proof detail but a direct failure of the algorithm as stated; the central claim that the paper provides an efficient proper-interval algorithm is unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Maximum Edge Open Packing Problem on three subclasses of chordal graphs: proper interval graphs, block graphs, and split graphs. It claims an O(n^2)-time algorithm for proper interval graphs, an O(n+m)-time algorithm for block graphs, and (in the abstract) an O(n^3)-time algorithm for split graphs, with the body claiming linear time for split graphs. The split-graph section gives a self-contained formula for the edge open packing number in terms of neighborhood sizes in the independent side of the split partition. The block-graph section develops recurrences based on a rooted cut-tree decomposition, and the proper-interval section develops recurrences based on a bicompatible elimination ordering. These results are presented as partial answers to an open question of Brešar and Samadi on chordal graphs.","tokens_in":13749,"tokens_out":2589,"duration_ms":23274,"significance":"If the algorithmic claims were correct, the paper would partially resolve a natural open question: whether the edge open packing number can be computed efficiently on chordal graphs. The split-graph characterization is explicit and appears sound, and the block-graph and proper-interval recurrences are structurally plausible. However, the central algorithmic claims for proper interval graphs and block graphs are not supported as written. In particular, the proposed proper-interval algorithm is not polynomial-time as stated, and the block-graph algorithm relies on an undefined quantity. These are not presentation issues; they undermine the main claimed results. The split-graph result, if taken alone, is a modest but correct contribution, though it is contradicted by the abstract/body complexity statement. The paper does not provide machine-checked proofs, implementations, or reproducible code, so the burden falls on the written recurrences and pseudocode, which currently fail on load-bearing points.","major_comments":[{"comment":"The claimed polynomial-time algorithm for proper interval graphs is not polynomial as written. Algorithm 1 makes recursive calls at lines 5, 9, and 14 without any memoization, and no bound on the number of recursive invocations is given. For a path P_n with BCO v1,...,vn, l(v_i)=i+1, so k=2 and the recursion calls MaxEOP PIG on G[v4..vn], G[v5..vn], and G[v2..vn]. The number of calls T(n) satisfies T(n) ≥ T(n-1)+T(n-3)+T(n-4), which grows exponentially. Thus the statement in Theorem 6 that the algorithm 'runs in polynomial time' is false for the provided pseudocode. The proper-interval graph result is therefore unsupported.","section":"§2, Algorithm 1 / Theorem 6"},{"comment":"The block-graph algorithm is incomplete because the value ρ_e^o(G^B_v) used in Lemma 10 and Algorithm 2, line 6, is never defined by a recurrence or computed in the algorithm. The quantities ρ_c, ρ_l, ρ' are defined for rooted graphs G_v associated with cut vertices, but G^B_v is a component after deleting v from a branch, and no formula for its edge open packing number is supplied. Without a definition or computation rule for ρ_e^o(G^B_v), the recurrence for ρ'(G_v) is not evaluable, and the claimed O(n+m) algorithm cannot be implemented. This is a load-bearing gap in the block-graph result.","section":"§3, Lemma 10 and Algorithm 2"},{"comment":"The paper makes conflicting complexity claims for split graphs: the abstract states an O(n^3)-time algorithm, while the body of §4 and Theorem 13 claim the problem 'can be solved in linear time.' Moreover, no pseudocode or explicit data-structure argument for the linear-time computation of ρ_1(G) and ρ_2(G) is given. The formula itself appears correct, but the computational claim needs to be stated consistently and justified.","section":"Abstract and §4, Theorem 13"}],"minor_comments":[{"comment":"In the proof of the reverse inequality for ρ''(G), the set S' is defined as S_j ∪ {v1vj, vjvp}, but S_j has not been defined in that case; it should be S_j^p. This is a typo, but it makes the proof harder to follow.","section":"§2, Lemma 4(ii)"},{"comment":"There is no explicit base case for graphs with fewer than two vertices or for empty induced subgraphs. The recursion may call MaxEOP PIG on an empty graph, and the return value is unspecified.","section":"Algorithm 1"},{"comment":"The line uses ρ_l(G_v) whereas the surrounding text and definitions use ρ_l(G_{v_i}); this indexing typo should be fixed.","section":"§3, Algorithm 2, line 22"},{"comment":"The BCO clique property is cited to [13], but the text earlier says BCOs characterize proper interval graphs and cites [10]. The attribution should be clarified so the reader knows which source proves which statement.","section":"§2, Observation 2"},{"comment":"The proof treats the case S=∅ and then assumes S≠∅, but it does not explicitly discuss the case where K is a single vertex. This is harmless because the formula still gives the correct value, but the edge case should be stated.","section":"§4, Theorem 13"}],"recommendation":"reject","confidential_remarks":"The split-graph formula appears to be a valid small contribution, and the structural recurrences for block graphs and proper interval graphs may be salvageable. However, the central algorithmic claims are not established as written: Algorithm 1 is exponential, and Lemma 10/Algorithm 2 depend on an undefined quantity. These are not cosmetic issues. A revision that supplies a correct polynomial-time algorithm for proper interval graphs (e.g., through dynamic programming with explicit memoization and a proof of polynomial state count) and a complete recurrence for block graphs could change the picture, but that is a substantial rewrite beyond a minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: the split graph result at the end is a solid little contribution, and the other two sections are not in working order as written. I would not desk-reject the paper, because the gaps look repairable, but the polynomial-time claims in Sections 2 and 3 need real fixes before they can stand.\n\nWhat's actually new: Theorem 13 gives a closed form for the edge open packing number of a split graph: max over pairs x,y in K of (l_x - l_xy + 1) and symmetrically, plus max over x in K of l_x. The proof is straightforward and checks out, with the usual edge case when |K|=1 (the max over an empty set needs a convention, but zero makes it work). This directly addresses the Brešar–Samadi open question for split graphs, and it is a legitimate, if modest, contribution.\n\nThe proper interval algorithm (Algorithm 1) has the right recursive intuition: peek at v1, decide whether it is in an edge from the initial clique, and split on whether that edge extends deeper. But the code recurses without memoization. On a path the recursion expands to T(n-1)+T(n-3)+T(n-4) calls, which is exponential. The paper simply asserts \"runs in polynomial time\" with no runtime proof. That's not a missing detail; it's a false statement about the algorithm as written. Memoization would almost certainly recover the claimed O(n^2), but that requires a revision.\n\nThe block graph algorithm is also incomplete. Lemma 10 and Algorithm 2 use the value rho_o^e(G^B_v) in line 6, but no recurrence or definition says how to compute that from the already-computed DP values. The lemmas for rho_c and rho_l are well-formed, but rho' depends on a quantity the algorithm never calculates. So the algorithm as written is not executable. Additionally, the abstract says O(n^3) for split graphs while the body says linear; those should agree.\n\nThe structural arguments for proper interval graphs rely on the BCO clique property, which is standard and fine, though the paper states rather than proves the needed neighborhood structure. I think the reader's worry about l(v_i) being non-decreasing is not a serious issue because Observation 2 implies the stronger clique property needed.\n\nBottom line: the split graph formula is real, the other two sections are plausible projects rather than completed proofs. This deserves a serious referee, and a careful report should ask for memoized recurrences and a completed block DP before the paper can be accepted.","headline":"The split graph formula is likely correct and worth keeping; the two algorithm sections are not in working order as written, but the gaps look fixable.","tokens_in":14182,"tokens_out":7428,"would_cite":true,"duration_ms":60546,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","05C69","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the maximum edge open packing number can be computed in polynomial time for proper interval graphs and block graphs, and in linear time for split graphs, partially answering Brešar and Samadi's open question on chordal","keywords":["edge open packing","proper interval graphs","block graphs","split graphs","chordal graphs","bi-compatible elimination ordering","cut-tree","polynomial-time algorithm"],"falsifier":"Run the proposed algorithm on all proper interval graphs up to, say, 10 vertices and compare its output with a brute-force enumeration of all edge subsets; a single mismatch, or a proper interval graph whose BCO has a right-neighbor function that decreases at some step, would disprove the O(n^2) claim.","tokens_in":13402,"feed_emoji":"📐","tokens_out":7045,"duration_ms":51395,"temperature":0.7,"pith_summary":"The paper tackles an open algorithmic question about chordal graphs: is the edge open packing number—the size of the largest set of edges with no third edge touching two of them—computable efficiently? It answers yes for three important subclasses: proper interval graphs, block graphs, and split graphs, giving polynomial-time algorithms for the first two and a linear-time algorithm for the third (as stated in the main text, though the abstract lists O(n^3)). The results are significant because the problem is NP-complete for several other graph families, so these positive results identify where tractability begins. The proof strategy is structural: each class has a natural decomposition that turns the problem into a small number of subproblems solved recursively or by formula.","feed_headline":"Efficient algorithms solve edge packing on three chordal classes","feed_subtitle":"Three chordal subclasses, proper interval, block, and split, get fast exact edge-packing algorithms.","key_machinery":"The machinery is threefold: (1) a bi-compatible elimination ordering (BCO) for proper interval graphs, which orders vertices so every suffix is again a proper interval graph and defines a right-neighbor function l(v_i) that marks where subproblem suffixes begin; (2) a rooted cut-tree for block graphs, whose nodes are blocks and cut vertices, with auxiliary parameters ρ_c, ρ_l, ρ′, ρ″ that describe how a cut vertex participates in an optimal edge open packing; (3) the clique–independent-set partition of a split graph, which reduces the problem to comparing two candidate star configurations using per-vertex counts l_x and shared-neighbor counts l_xy.","core_discovery":"On its own terms, the paper establishes that the Maximum Edge Open Packing Problem is solvable in polynomial time on three subclasses of chordal graphs. For proper interval graphs, it provides a recursive algorithm using a bi-compatible elimination ordering (BCO): the graph is split by the rightmost neighbor of the first vertex, and the optimum is the maximum of two cases depending on whether an edge incident to the first vertex is selected. For block graphs, it builds a rooted cut-tree and computes four auxiliary parameters—ρ_c, ρ_l, ρ′, ρ″—for each subgraph hanging from a cut vertex, then combines them bottom-up. For split graphs, it proves a closed formula: the EOP number equals the large","pith_inferences":["If the missing monotonicity lemma for BCO right-neighbor functions is supplied, the same recursion may extend to other interval graph hierarchies, such as unit interval graphs with alternate orderings, giving a testable route toward a full chordal graph algorithm.","The split graph formula suggests that for chordal graphs with a clique cutset, the EOP number may be computed by combining solutions on the separated components, paralleling the cut-tree recursion for block graphs; this is a conjecture the paper does not make.","The abstract's O(n^3) figure for split graphs conflicts with the body's linear-time claim; an erratum or clarification is needed, and if the body is right, the algorithm is input-optimal for split graphs.","The block graph algorithm's Lemma 10 uses a value ρ_e^o(G^B_v) without giving a recurrence for it; filling this gap is necessary for the O(n+m) bound to be verifiably complete."],"forward_implications":["Proper interval graphs admit an O(n^2) algorithm for the maximum edge open packing number, assuming a BCO is computable in linear time.","Block graphs admit an O(n+m) algorithm via dynamic programming on the cut-tree, where n and m are vertices and edges.","Split graphs admit a linear-time algorithm, with the optimum given by the closed formula max{max_{x≠y}(l_x − l_xy + 1, l_y − l_xy + 1), max_x l_x}.","These are the first polynomial-time algorithms for these subclasses, and they partially resolve the open question for chordal graphs.","The split graph formula implies the known one-edge value for complete graphs, since S empty gives ρ_e^o(K_n)=1."],"fun_headline_variants":["Edge open packing now solvable fast on three chordal graph classes","Three chordal subclasses get polynomial-time edge packing algorithms","Proper interval, block, split graphs get exact edge-packing algorithms","Packing edges on chordal subclasses: new efficient algorithms","Polynomial algorithms for edge open packing on three chordal families"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proper interval graph algorithm depends on an unproved monotonicity property of the right-neighbor function in a bi-compatible elimination ordering: that l(v_i) is non-decreasing as i increases; if that property fails on some proper interval graph, the recursive decomposition of Lemma 4 breaks down.","fun_headline_variants_meta":{"raw":{"variants":["Edge open packing now solvable fast on three chordal graph classes","Three chordal subclasses get polynomial-time edge packing algorithms","Proper interval, block, split graphs get exact edge-packing algorithms","Packing edges on chordal subclasses: new efficient algorithms","Polynomial algorithms for edge open packing on three chordal families"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000835,"raw_usage":{"total_tokens":3559,"prompt_tokens":901,"completion_tokens":2658,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":645,"completion_tokens_details":{"reasoning_tokens":2571}},"tokens_in":645,"tokens_out":2658,"duration_ms":15384,"temperature":1.0,"reasoning_tokens":2571,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T09:19:44.570726+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the proposed algorithm on all proper interval graphs up to, say, 10 vertices and compare its output with a brute-force enumeration of all edge subsets; a single mismatch, or a proper interval graph whose BCO has a right-neighbor function that decreases at some step, would disprove the O(n^2) claim.","supporting_citations":[],"review_version":1}