Edge open packing on subclasses of chordal graphs

Kamal Santra

REVIEW 3 major objections 5 minor 16 references

Edge open packing on subclasses of chordal graphs

T0 review · 3 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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

desk verdict 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. read the letter →

arxiv 2510.16236 v3 pith:7PF7A524 submitted 2025-10-17 math.CO cs.DM

Kamal Santra This is my paper · ORCID

classification math.COcs.DM MSC 05C8505C6968R10

keywords edgeopenpackingproperintervalgraphsblocksplitchordalbi-compatibleeliminationorderingcut-treepolynomial-timealgorithm

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

What'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.

The 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.

The 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.

The 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.

Bottom 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.

Referee Report

3 major / 5 minor

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.

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 (3)

[§2, Algorithm 1 / Theorem 6] 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.
[§3, Lemma 10 and Algorithm 2] 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.
[Abstract and §4, Theorem 13] 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.

minor comments (5)

[§2, Lemma 4(ii)] 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.
[Algorithm 1] 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.
[§3, Algorithm 2, line 22] The line uses ρ_l(G_v) whereas the surrounding text and definitions use ρ_l(G_{v_i}); this indexing typo should be fixed.
[§2, Observation 2] 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.
[§4, Theorem 13] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the algorithms are derived from structural lemmas, not from fitted parameters or self-citation chains.

full rationale

The paper's derivations are self-contained in the relevant sense. The recurrences in Section 2 (Lemmas 4–5) are justified directly from the definition of an edge open packing set and from the clique structure of proper interval graphs given by a BCO; the split graph formula in Theorem 13 follows from the fact that an EOP set in a split graph is a star centered at a clique vertex; and the block graph recurrences in Lemmas 8–11 are structural decompositions along a rooted cut-tree. None of these quantities is fitted to data, none is renamed from a known result, and no prediction is forced by construction. The cited background results, such as the BCO characterization of proper interval graphs [10] and the BCO property in Observation 2 [13], are external and are used as tools rather than as the target result. The only self-citation, [14] by Pandey and Santra, appears in the introduction and is not load-bearing for any algorithm. Possible correctness concerns—such as the un-memoized recursive calls in Algorithm 1 and the implicit reliance on ρ_e^o(G_v^B) in Lemma 10—are algorithmic or proof-completeness issues, not circularity, because they do not make the claimed results equivalent to their assumptions by definition. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The algorithms rely on standard structural characterizations of proper interval, block, and split graphs. No new entities are introduced. One unstated monotonicity assumption is load-bearing for the proper interval recursion.

assumptions (5)

standard math Every proper interval graph admits a bi-compatible elimination ordering (BCO), and the neighbors of each vertex in a BCO form a suffix such that consecutive indices induce cliques (Observation 2 of [13]).
Used in Lemma 4 to assert {v1,...,vk} is a clique and to restrict the edges in an EOP set; cited from Panda and Das [13].
domain assumption In a proper interval graph with BCO, l(v_i) is non-decreasing in i.
Implicitly used in Lemma 4(ii) to ensure that vertices beyond l(v_p) are not adjacent to v_j; the paper never states or proves this.
standard math Chordal graphs are exactly the graphs with a perfect elimination ordering (Fulkerson and Gross [9]).
Background for chordal graph subclasses; not directly used in proofs but frames the open question.
standard math For a block graph, the cut-tree can be built in O(n+m) time and each block is a clique (Aho et al. [1]).
Basis for Algorithm 2's decomposition.
domain assumption In a split graph, a maximum clique K can be found in linear time and no vertex of the independent set is adjacent to all of K.
Theorem 13 assumes K is the maximum clique; the paper does not state how the partition is obtained, but it is standard.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Edge open packing on subclasses of chordal graphs." pith.science (2026). https://pith.science/paper/7PF7A524

@misc{pith2026251016236,
  author       = {Pith},
  title        = {Pith review of: Edge open packing on subclasses of chordal graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7PF7A524}},
  note         = {Machine review of arXiv:2510.16236}
}

abstract

Packing problems in graphs are fundamental in combinatorial optimization and arise naturally in applications such as resource allocation, scheduling, and communication networks. A classical example is the \emph{induced matching} problem, where one seeks a set of edges whose endpoints induce a matching. In 2022, Chelladurai et al. introduced the notion of \emph{edge open packing}, which can be viewed as a relaxation of induced matching: instead of forcing the selected edges to induce only isolated edges, edge open packing allows them to induce disjoint stars. For a graph \(G=(V,E)\), two edges \(e_1,e_2\in E(G)\) are said to have a common edge if there exists an edge \(e\in E(G)\setminus\{e_1,e_2\}\) joining an endpoint of \(e_1\) to an endpoint of \(e_2\). A set \(D\subseteq E(G)\) is an \emph{edge open packing set} if no two edges in \(D\) have a common edge, and the maximum cardinality of such a set is the \emph{edge open packing number} \(\rho_e^o(G)\). The corresponding optimization problem is the \textsc{Maximum Edge Open Packing Problem}. In this paper, we study the computational complexity of the \textsc{Maximum Edge Open Packing Problem}. Motivated by an open question posed by Bre\v{s}ar and Samadi concerning chordal graphs, we investigate the problem on three subclasses of chordal graphs. We give an \(O(n^2)\)-time algorithm for proper interval graphs, an \(O(n+m)\)-time algorithm for block graphs, where \(n=|V(G)|\) and \(m=|E(G)|\), and an \(O(n^3)\)-time algorithm for split graphs. These results provide partial answers to the open question and contribute to the algorithmic understanding of edge packing parameters in chordal graph classes.

Figures

Figures reproduced from arXiv: 2510.16236 by the authors.

**Figure 1.** On the right is a block graph G, in the middle is its cut-tree T v1 G , and on the left side are the graphs Gv and GB v , respectively Let G be a block graph and T v G be its rooted cut-tree. Now if we take an arbitrary EOP set S of Gv, we have three possibilities: (a) v is the center of a star from Gv[S], (b) v is a leaf of a star from Gv[S], or (c) v is not incident with an edge from S. If v belongs to a K1,1-comp… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 1 linked inside Pith

[1]

A. V. Aho, J. E. Hopcroft, and J. D. Ullman.The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974

1974
[2]

Breˇ sar, T

B. Breˇ sar, T. Dravec, J. Hedˇ zet, and B. Samadi. Induced matching vs edge open packing: Trees and product graphs.Discrete Mathematics, 348(7):114458, 2025

2025
[3]

Breˇ sar and B

B. Breˇ sar and B. Samadi. Edge open packing: complexity, algorithmic aspects, and bounds.Theo- retical Computer Science, 1022:114884, 2024

2024
[4]

K. Cameron. Induced matchings.Discrete Applied Mathematics, 24(1-3):97–102, 1989

1989
[5]

D. M. Cardoso, O. J. Cerdeira, C. Dominicc, and P. J. Cruz. Injective edge coloring of graphs. Filomat, 33(19):6411–6423, 2019

2019
[6]

Chelladurai, K

G. Chelladurai, K. Kalimuthu, and S. Soundararajan. Edge open packing sets in graphs.RAIRO- Operations Research, 56(5):3765–3776, 2022

2022
[7]

K. K. Dabrowski, M. Demange, and V. V. Lozin. New results on maximum induced matchings in bipartite graphs and beyond.Theoretical Computer Science, 478:33–40, 2013

2013
[8]

Foucaud, H

F. Foucaud, H. Hocquard, and D. Lajou. Complexity and algorithms for injective edge-coloring in graphs.Information Processing Letters, 170:106121, 2021

2021

Show all 16 references

[9]

Fulkerson and O

D. Fulkerson and O. Gross. Incidence matrices and interval graphs.Pacific Journal of Mathematics, 15(3):835–855, 1965

1965
[10]

R. E. Jamison and R. Laskar. Elimination orderings of chordal graphs.Combinatorics and Applica- tions, pages 192–200, 1982. 11

1982
[11]

V. V. Lozin. On maximum induced matchings in bipartite graphs.Information Processing Letters, 81(1):7–11, 2002

2002
[12]

Z. Miao, Y. Song, and G. Yu. Note on injective edge-coloring of graphs.Discrete Applied Mathe- matics, 310:65–74, 2022

2022
[13]

B. S. Panda and S. K. Das. A linear time recognition algorithm for proper interval graphs.Infor- mation Processing Letters, 87(3):153–161, 2003

2003
[14]

Pandey and K

A. Pandey and K. Santra. Edge open packing: further characterizations.arXiv preprint arXiv:2508.01935, 2025

2025 arXiv
[15]

L. J. Stockmeyer and V. V. Vazirani. Np-completeness of some generalizations of the maximum matching problem.Information Processing Letters, 15(1):14–19, 1982

1982
[16]

D. B. West.Introduction to graph theory, volume 2. Prentice hall, 2001. 12

2001

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [1]

A. V. Aho, J. E. Hopcroft, and J. D. Ullman.The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974

1974

[2] [2]

Breˇ sar, T

B. Breˇ sar, T. Dravec, J. Hedˇ zet, and B. Samadi. Induced matching vs edge open packing: Trees and product graphs.Discrete Mathematics, 348(7):114458, 2025

2025

[3] [3]

Breˇ sar and B

B. Breˇ sar and B. Samadi. Edge open packing: complexity, algorithmic aspects, and bounds.Theo- retical Computer Science, 1022:114884, 2024

2024

[4] [4]

K. Cameron. Induced matchings.Discrete Applied Mathematics, 24(1-3):97–102, 1989

1989

[5] [5]

D. M. Cardoso, O. J. Cerdeira, C. Dominicc, and P. J. Cruz. Injective edge coloring of graphs. Filomat, 33(19):6411–6423, 2019

2019

[6] [6]

Chelladurai, K

G. Chelladurai, K. Kalimuthu, and S. Soundararajan. Edge open packing sets in graphs.RAIRO- Operations Research, 56(5):3765–3776, 2022

2022

[7] [7]

K. K. Dabrowski, M. Demange, and V. V. Lozin. New results on maximum induced matchings in bipartite graphs and beyond.Theoretical Computer Science, 478:33–40, 2013

2013

[8] [8]

Foucaud, H

F. Foucaud, H. Hocquard, and D. Lajou. Complexity and algorithms for injective edge-coloring in graphs.Information Processing Letters, 170:106121, 2021

2021