2026/08/05 by Gautam K. Das, Kamal Santra
Computer Science · Mathematics · #cs.DM #math.CO
arxiv created 2026/08/05 · arxiv updated 2026/08/07
Edge open packing is a relaxation of induced matching in which the selected edges may induce disjoint stars. We study the Maximum Edge Open Packing problem on permutation graphs, interval graphs, and well-partitioned chordal graphs. For the first two classes, we introduce an oriented star-conflict graph whose vertices are ordered edges. We prove that its compatibility graph admits a natural transitive orientation: a product-order orientation for permutation graphs and a left-to-right orientation for interval graphs. In each case, a maximum edge open packing is obtained from a maximum clique, equivalently a longest directed path, in the compatibility graph. Given the corresponding representation, both algorithms run in \(O(n2+m2)≤ O(n4)\) time, where \(n=|V(G)|\) and \(m=|E(G)|\). For well-partitioned chordal graphs, we give a dynamic program over a partition tree. Its states use the fact that the endpoint set of an edge open packing meets each clique bag in at most two vertices. Given a partition-tree representation, the edge open packing number is computed in \(O(n4)\) time, and an optimal packing can be reconstructed within the same time bound.