Source-linked AI summary
Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs
Gautam K. Das, Kamal Santra
TL;DR
Maximum Edge Open Packing asks for large sets of edges whose endpoints induce disjoint stars, and the paper studies this problem on three graph classes. It proves an AT-free preservation result and develops dynamic programs for chordal and convex bipartite graphs, yielding polynomial-time algorithms with the stated bounds.
Problem
The paper addresses how to find maximum edge open packings efficiently on AT-free, chordal, and convex bipartite graphs.
Source: §1 · p. 2Method
It applies maximum independent set to the AT-free oriented star-conflict graph and uses dynamic programming for chordal and convex bipartite graphs.
Source: §1 · p. 2Results
The algorithms run in O(n^2+m^4) time on AT-free graphs and O(n^4) time on chordal and convex bipartite graphs; the chordal bound does not require bounded clique number.
Source: §1 · p. 2Takeaways & Limitations
The paper leaves improving the running times and finding a polynomial-time algorithm for chordal bipartite graphs as natural next questions.
Source: §6 · p. 10The convex-bipartite algorithm assumes a convex ordering on one part and deletes isolated vertices before processing.
Source: §5 · p. 8
Abstract
from arXiv · showhide
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 $\rho_e^o(G)=\alpha(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.
1 Introduction
The paper develops maximum edge open packing algorithms for AT-free, chordal, and convex bipartite graphs. Its contributions combine a structural transformation for AT-free graphs with dynamic programming for the other two classes.
1 Introduction
- Edge open packing models mutually separated edge groups, allowing multiple selected edges to share a star centre, unlike induced matching [7, 17, 11].The paper also connects maximum edge open packing to feasible one-channel link sets under a secondary-interference model.Source: §1 · p. 1
- Earlier work gave polynomial-time algorithms for biconvex and cocomparability graphs; the latter use the oriented star-conflict graph and extend permutation- and interval-graph results [1] [13].The paper notes that biconvex graphs need not be AT-free, so the AT-free result does not subsume the biconvex result.Source: §1 · pp. 2–3
Our contributions
- The AT-free preservation theorem and maximum-independent-set correspondence yield an O(n^2+m^4)-time algorithm for Maximum Edge Open Packing.The oriented star-conflict graph A_G is AT-free whenever G is AT-free; A_G has 2m vertices and is constructed in O(n^2+m^2) time.Source: §1 · p. 2
- The chordal-graph algorithm runs in O(n^4) time without a clique-number bound, using a clique-tree-derived nice tree decomposition.Each clique contains at most two endpoints of a packing; the dynamic program records their roles in a partial star.Source: §1 · p. 2
- The convex-bipartite algorithm runs in O(n^4) time, extending the earlier biconvex algorithm and improving its explicit running-time bound.Two boundary indices separate consecutive star components in a left-to-right dynamic program.Source: §1 · p. 2
2 Preliminaries
The preliminaries establish the paper’s graph and packing terminology. They characterize edge open packings through induced endpoint subgraphs and define the graph classes used later.
2 Preliminaries
- Throughout, a star means K1,t for t ≥ 1, so K2 is a star and either endpoint may serve as its centre.The notation uses n for the number of vertices and m for the number of edges.Source: §2 · p. 3
- An edge open packing consists of edges whose endpoints induce a disjoint union of stars, including single edges; the induced subgraph contains exactly the selected edges.Equivalently, no two selected edges have a third edge joining their endpoints.Source: §2 · p. 3
- A chordal graph has no induced cycle of length at least four, and its maximal cliques form a clique tree; AT-free graphs contain no asteroidal triple.The cliques containing any vertex induce a connected subtree.Source: §2 · p. 3
- A convex bipartite graph has an ordering of one part in which every neighborhood in the other part is consecutive; biconvex graphs have such orders on both sides.Bipartite permutation graphs are properly contained in biconvex graphs, which are properly contained in convex bipartite graphs.Source: §2 · p. 3
3 Maximum Edge Open Packing in AT-Free Graphs
The oriented star-conflict graph converts Maximum Edge Open Packing into Maximum Independent Set, and the paper proves this transformation preserves AT-freeness. This yields an O(n^2 + m^4)-time algorithm on AT-free graphs.
3.1 The oriented star-conflict graph
- A_G has oriented edges of G as vertices, with incompatible orientations adjacent and compatible orientations independent.An edge open packing corresponds to an independent set in A_G, so ρ_e^o(G) = α(A_G).Source: §3.1 · pp. 3–4
3.2 Preservation of AT-freeness
- If G is AT-free, then its oriented star-conflict graph A_G is also AT-free.The proof shows that an asteroidal triple in A_G would yield one in G.Source: §3.2 · p. 4
3.3 Algorithm and running time
- The algorithm constructs A_G and applies a maximum independent set algorithm for AT-free graphs before translating the result back into an edge open packing.A_G has 2m vertices; constructing it takes O(n^2 + m^2) time, and the independent-set computation takes O(m^4) time.Source: §3.3 · p. 5
- Theorem 4 gives an O(n^2 + m^4)-time algorithm for Maximum Edge Open Packing on AT-free graphs.The bound is O(n^8) when expressed only in terms of n.Source: §3.3 · p. 5
4 Maximum Edge Open Packing in Chordal Graphs
The chordal-graph algorithm uses a clique-tree-derived nice tree decomposition and the fact that a packing has at most two endpoints in any clique. Its dynamic program computes an optimum packing in O(n^4) time.
4 Maximum Edge Open Packing in Chordal Graphs
- A nice rooted tree decomposition derived from a clique tree has clique bags and O(n^2) nodes.The construction uses empty root and leaf bags and introduce, forget, and join nodes.Source: §4 · p. 5
- Every clique contains at most two endpoints of a packing, and every edge induced by those endpoints belongs to the packing.This structural bound supports states with at most two active vertices in each clique bag.Source: §4 · p. 5, §4.1 · p. 5
4.1 States
- Each state records active bag vertices and their partial-star roles, while its table value counts selected edges with an endpoint outside the bag.At most two vertices are active; an edge wholly inside the bag remains uncounted until one endpoint is forgotten.Source: §4.1 · pp. 5–6
4.2 Transitions
- Introduce, forget, and join transitions preserve valid partial star forests, reject incompatible roles, and count each selected edge exactly once.At joins, child states must activate the same bag vertices; an edge inside the bag is counted when its first endpoint is forgotten.Source: §4.2 · pp. 6–7
4.3 Correctness
- The dynamic program represents every edge open packing, and each accepting root computation represents a packing with its recorded cardinality.The empty root bag leaves the empty state as the accepting state.Source: §4.3 · p. 7
4.4 Running time and reconstruction
- O(n^4) time suffices to compute the edge open packing number and an optimum packing in a chordal graph.The decomposition has O(n^2) nodes, and each node can be processed in O((b_t + 1)^2) time.Source: §4.4 · p. 8
5 Maximum Edge Open Packing in Convex Bipartite Graphs
For convex bipartite graphs, the algorithm appends separated star components from left to right, tracking two boundary indices. It computes an optimum packing in O(n^4) time and O(n^2) space.
5.1 Separation properties
- Ordering components by their leftmost X-vertex yields separation conditions for all later X- and Y-vertices.Given barriers α and β for a prefix, later X-vertices have index greater than β and later Y-vertices have left endpoint greater than α.Source: §5.1 · pp. 8–9
5.2 Dynamic programming table
- A partial solution is summarized by α, its rightmost selected X-index, and β, an upper bound on selected Y right endpoints.Future X-vertices must lie beyond β, and future Y-vertices must have left endpoint greater than α; retaining the largest value per barrier pair suffices.Source: §5.2 · p. 9
5.3 Transitions
- Each transition appends an X-centred or Y-centred star while enforcing the barriers that keep it separate from earlier and future components.For an X-centred star, the centre lies beyond β; for a Y-centred star, its left endpoint exceeds α.Source: §5.3 · p. 9
5.4 Correctness
- Every constructed solution is a packing, and processing the components of any packing yields a dynamic-program solution of at least its cardinality.The proof preserves prefix barriers and may add leaves while retaining compatibility with unprocessed components.Source: §5.4 · pp. 9–10
5.5 Running time and reconstruction
- O(n^4) time and O(n^2) space suffice to solve Maximum Edge Open Packing on convex bipartite graphs.The dynamic program has O(p^2) states and O(n^4) total time; predecessor records allow reconstruction of an optimum packing.Source: §5.5 · p. 10
6 Conclusion
The paper establishes algorithms for Maximum Edge Open Packing on AT-free, chordal, and convex bipartite graphs, including a chordal algorithm that handles unbounded clique number. It also identifies open questions about improving running times, extending polynomial-time solvability to chordal bipartite graphs, and parameterizing the results.
6 Conclusion
- The chordal dynamic program handles unbounded clique number, while the AT-free and convex bipartite algorithms run in O(n^2 + m^4) and O(n^4) time, respectively.The AT-free result follows from preservation of AT-freeness by the oriented star-conflict graph.Source: §6 · p. 10
- Whether the running times can be improved and whether Maximum Edge Open Packing is polynomial-time solvable on chordal bipartite graphs remain open questions.Further work could also examine graph classes where the oriented star-conflict construction preserves a structure tractable for maximum independent set.Source: §6 · p. 10
- For general graphs, treewidth yields fixed-parameter tractability through monadic second-order optimisation, but explicit running-time dependence and kernelisation bounds remain questions.The conclusion also asks whether the dependence on asteroidal number can be made fixed-parameter tractable.Source: §6 · pp. 10–11
- Polynomial-time solvability follows for each fixed bound on asteroidal number by mapping asteroidal sets of the oriented star-conflict graph to asteroidal sets of the original graph.The mapping uses the leaf coordinates, and the conclusion leaves fixed-parameter tractability of the dependence as an open question.Source: §6 · p. 11