Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs
Abstract
An edge open packing is a set of edges whose endpoints induce a disjoint union of stars. We study the problem of finding a maximum edge open packing in AT-free, chordal, and convex bipartite graphs. For AT-free graphs, we use the oriented star-conflict graph AG, introduced by Das and Santra, for which ρeo(G)=α(AG), and prove that AG is AT-free whenever G is AT-free. Consequently, a known maximum independent set algorithm for AT-free graphs yields an O(n2+m4)-time algorithm for Maximum Edge Open Packing, where n and m denote the numbers of vertices and edges of G, respectively. For chordal graphs, we develop an O(n4)-time dynamic programming algorithm over a nice tree decomposition derived from a clique tree, exploiting the structural fact that the endpoint set of an edge open packing intersects every clique in at most two vertices. Finally, for convex bipartite graphs, we obtain an O(n4)-time dynamic programming algorithm based on two boundary indices that separate consecutive star components. This result extends the previously known algorithm for biconvex bipartite graphs and, in particular, provides an improved explicit running-time bound for that class.
Related
- Maximum number of spanning trees in bipartite graphs with a given diameter
- Roman Domination on Circular-Convex, Triad-Convex Bipartite Graphs and P4-Tidy Graphs
- Exact penalties for maximum-edge bicliques in bipartite graphs
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
- Maximum Likelihood Degrees via One-Edge Chordal Completion
BibTeX
@misc{das2026maximum,
title = {{Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs}},
author = {Gautam K. Das and Kamal Santra},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02275},
eprint = {2610.02275},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02275},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs
AU - Gautam K. Das
AU - Kamal Santra
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02275
UR - https://arxiv.org/abs/2610.02275
AB - An edge open packing is a set of edges whose endpoints induce a disjoint union of stars. We study the problem of finding a maximum edge open packing in AT-free, chordal, and convex bipartite graphs. For AT-free graphs, we use the oriented star-conflict graph A_G, introduced by Das and Santra, for which ρ_e^o(G)=α(A_G), and prove that A_G is AT-free whenever G is AT-free. Consequently, a known maximum independent set algorithm for AT-free graphs yields an O(n^2+m^4)-time algorithm for Maximum Edge Open Packing, where n and m denote the numbers of vertices and edges of G, respectively. For chordal graphs, we develop an O(n^4)-time dynamic programming algorithm over a nice tree decomposition derived from a clique tree, exploiting the structural fact that the endpoint set of an edge open packing intersects every clique in at most two vertices. Finally, for convex bipartite graphs, we obtain an O(n^4)-time dynamic programming algorithm based on two boundary indices that separate consecutive star components. This result extends the previously known algorithm for biconvex bipartite graphs and, in particular, provides an improved explicit running-time bound for that class.
ER -