CS Paper Radar

Applying Changes to LDPC Codes by Using 3-Induced Matchings and Eigenvalues

Alireza Eshraghi Dehaghani, Sara Saeedi Madani, Dariush Kiani

cs.IT math.CO ·submitted 2026-10-18 17:45 UTC · v1

Abstract

The 2-switch operation for reducing the number of short cycles in Tanner graphs of LDPC codes has been utilized in some works. If this operation is appropriately applied to a 2-induced matching in a bipartite graph, then it surely preserves the bipartiteness of the graph. With a 2-induced matching, we have only one choice for applying this type of change to the graph. Using 3-induced matchings creates more potential and flexibility to apply certain changes to the Tanner graph. We present a necessary and sufficient condition for the existence of a 3-induced matching in bipartite graphs with girth at least 6. A 3-induced matching helps us to have more choices for applying a change to a bipartite graph while surely preserving the bipartiteness of the graph and keeping the degree sequences unchanged. Among all changes that we consider, we select the best change for reducing the number of cycles of length 6. The eigenvalues of subgraphs are used to reach a 3-induced matching, and a condition in some steps can be checked to ensure that the subgraph has at least one 3-induced matching. We present some numerical results regarding the steps at which the condition that guarantees the existence of a 3-induced matching is checked.

Closest papers

Nearest neighbours by meaning across the whole index.

Degree Realization with Maximum Matching

cs.DM cs.DS ·2026-10-30 ·Amotz Bar-Noy, Igor Kalinichev, David Peleg, Dror Rawitz
similarity 0.61
Abstract

The Maximum Matching Degree Realization problem requires, for a sequence $d$ of $n$ positive integers, to compute a realizing graph(whose degree sequence corresponds to $d$) with the maximum possible matching. We present a polynomial-time algorithm for this problem. The decision version of this problem requires to determine whether a sequence $d$ admits a realization with a matching of size $ν$ (without computing such a realization). Recently, it was shown that it can be done by verifying a series of inequalities. We improve the existing characterization by reducing the number of inequalities.

0.56

A 2/3-Approximation Algorithm for the Residual Maximum Matching Problem in General Graphs

cs.DS ·2026-10-20 ·Quanlong Niu, Riheng Jia
theory similarity 0.60
Abstract

The residual maximum matching problem asks for a maximum matching whose deletion leaves a graph with the largest possible matching number. For unweighted graphs, previous work provides a $1/2$-approximation guarantee in general graphs and a $2/3$ guarantee in graphs with a perfect matching. We present a $2/3$-approximation algorithm running in $O(n^5)$ time, extending the latter guarantee to general graphs. The algorithm improves the residual matching number through single-edge exchanges involving free vertices. We prove that, for any maximum matching that admits no further improvement by such exchanges, the residual matching number is at least $2/3$ of the optimum, and we give an example showing that this bound is tight.

0.09

A Canonical m-Atomic Decomposition of Bipartite Graphs via a Grid Model

cs.DS math.CO ·2026-08-20 ·Béla Jónás
theory similarity 0.59
Abstract · 60 pages. Structural decomposition of bipartite graphs via a grid model. Introduces the characteristic m of a brick, determines it for disco…

We study finite, connected, simple bipartite graphs in a grid model, in which a graph is drawn as a rectangular array and its structure is read off from empty subrectangles, called holes. In this model we attach to every brick a numerical invariant, its characteristic m, the difference between the number of rows and the largest proper independent set. A brick is excessive if m > 0. Our main results concern this invariant. We determine the characteristic of a disconnected excessive brick from those of its components, showing that m = min_i min{m_i, imb(W_i)} while the imbalance is additive; and we prove that an m-excessive brick is m-extendable, that is, every matching of size m extends to a maximum matching. Since Plummer's notion of n-extendability is defined only for graphs carrying a perfect matching, and our proof nowhere uses balance, the characteristic extends that notion canonically to unbalanced bipartite graphs. Using the characteristic we partition bipartite graphs into eleven structural classes. The underlying decomposition into atomic blocks is the classical decomposition into elementary components, and the description of the maximum proper independent sets by ideals of the block poset is likewise classical; the paper states precisely which results are classical and are not claimed here. What the grid model adds is a single geometric framework in which holes, characteristics and the block triangular form are read off from one picture.

0.32

Structural Complexity of Matching-Match: Dense and Sparse Graphs

cs.DS ·2026-09-22 ·Ilie Dumitru, Adrian Miclăuş, Alexandru Popa
theory similarity 0.59
Abstract

The Matching-Match puzzle asks whether the vertices of a fixed graph can be colored so that the multiset of color pairs induced by its edges is exactly a prescribed multiset. We study how the complexity of this realization problem depends on the host graph. On the dense side, we give a polynomial-time algorithm for complete $k$-partite graphs for every fixed number $k$ of parts, with arbitrary precoloring and an arbitrary number of colors. We prove a sharp complement-degree threshold: the problem is polynomial-time solvable when $Δ(\overline G)\le1$, but NP-complete on completely uncolored graphs already when $Δ(\overline G)=2$. This yields a dichotomy for uniform complete multipartite graphs, and connected diameter two already suffices for NP-completeness. We also prove W[1]-hardness on cographs parameterized by the number of colors. On the sparse side, completely uncolored paths and cycles admit a linear-time characterization by Euler trails and circuits, while counting feasible colorings is $\#P$-complete on both classes. Counting is nevertheless polynomial-time solvable on stars and complete graphs, even with arbitrary precoloring. A decomposition-transfer theorem yields NP-completeness already at tree-depth two. A separate path-decomposition reduction gives a maximum-degree threshold between one and two for completely uncolored disconnected host graphs with unrestrictedly many colors. Components with at most two edges are tractable, while a disjoint union of $P_4$'s is NP-complete. Finally, precoloring restores tractability in several cases: star forests are polynomial when every center is precolored, and two broad precoloring regimes on length-two spiders are polynomial even when the number of colors is unbounded.

0.21

Maximum Matching on Regular Nonbipartite Graphs

cs.DS cs.DM ·2026-09-12 ·Varsha Dani, Thomas P. Hayes, Seth Pettie
theory similarity 0.58
Abstract

Blocking flow-type maximum matching algorithms are based on finding maximal sets of shortest augmenting paths. They run in $O(m\sqrt{n})$ time, on both bipartite [HK73, Din70, Kar73a, Kar73a] and nonbipartite graphs [GT91, Gab17, Vaz24], but this time bound can be improved if the input is constrained. In this paper we consider $d$-regular bipartite and nonbipartite graphs. Previous algorithms show that a perfect matching in $d$-regular bipartite graphs can be computed in near-linear time deterministically [COS01] or sublinear time with high probability [GKK13]. On $d$-regular non-bipartite graphs, a $(1-1/(d+1))$-approximation can be computed in sublinear time $O(n \log n)$ with high probability [DH25], and hence a maximum matching can be computed in $O(n^2)$ time, w.h.p., which is slightly faster than the best deterministic algorithm for regular graphs [Yus13], running in O(n^2 log n) time. We prove that any blocking flow-type maximum matching algorithm based on finding shortest augmenting paths runs in $O(n^2)$ time on d-regular graphs, both bipartite and nonbipartite. On nonbipartite graphs this is an asymptotic improvement over $O(n^2 \log n)$ [Yus13] and an improvement over $O(m\sqrt{n})$ [GT91, Gab17, Vaz24] when $d = ω(\sqrt{n})$. It also improves [DH25] by making its $O(n^2)$ bound deterministic. However, the main take-away message is that no new algorithms are needed: the "classic" matching algorithms automatically outperform [Yus13, DH25]. We also consider extensions of our results to graphs that are only "nearly regular," meaning that their degrees all lie within a specified range, $[d, Δ]$.

0.24

Improved Pass Complexity for Semi-Streaming Matching in General Graphs via Budgeted Price Approach

cs.DS ·2026-10-15 ·Tatsuya Terao
similarity 0.58
Abstract · 11 pages

We present a simple deterministic semi-streaming algorithm that computes a $(1-\varepsilon)$-approximate maximum matching in general graphs in $O(1/\varepsilon^{2})$ passes. This matches the pass complexity of the auction algorithm of Assadi, Liu, and Tarjan~[SOSA'21] for bipartite graphs, and answers Open Question~2 of Assadi~[SOSA'24 \& TheoretiCS'25]. Our approach, which we call the \emph{budgeted price approach}, is very different from the previous $\mathrm{poly}(1/\varepsilon)$-pass semi-streaming algorithms for $(1-\varepsilon)$-approximation of matching in general graphs and improves their pass complexity. All previous approaches are augmenting-path-based and use $O(1/\varepsilon^{19})$ passes by Fischer, Mitrović, and Uitto~[STOC'22], $O(1/\varepsilon^{6})$ passes by Mitrović, Mukherjee, Sankowski, and Sheu~[ICALP'25], and $O(1/\varepsilon^{4})$ passes by Izumi, Kitamura, and Yamaguchi~['25].

0.26

A Parallel Greedy Algorithm for Maximal b-Matching in Hypergraphs

cs.DS cs.DC ·2026-11-11 ·Saeed Bakhshan, Daniel Grosu, Henrik Reinstädtler, Christian Schulz
published similarity 0.58
Abstract · 19 pages. Accepted to the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA 2027)

We present \parallelBatchBMatch, a parallel batch-vote algorithm for maximal $b$-matching in hypergraphs. The algorithm is deterministic for a given ordering of edges and produces the same output as the sequential greedy algorithm, i.e., the lexicographically first maximal $b$-matching. Under a uniformly random priority order it performs $O(m')$ expected work in the binary fork--join model, where $m'$ is the number of pins, the total number of vertex--edge incidences. The algorithm performs at most $m$ rounds for every priority order, where $m$ is the number of edges. Every round of the algorithm has $O(\log^2 m')$ depth with high probability, and thus the total depth of the algorithm is $O(m \log^2 m')$ with high probability. We implement the parallel algorithm in CUDA and evaluate it on real-world hypergraphs with capacities $b \in \{1, 3, 5\}$. The parallel algorithm computes the same matchings as the greedy algorithms and for the case of $b = 5$ it is up to $19.07$ times faster than the existing state-of-the art greedy algorithm.

0.38

Crown graphs maximise the representation number of bipartite graphs

cs.DM math.CO ·2026-09-24 ·Matthew J. Colbrook, Catherine Drysdale
theory similarity 0.57
Abstract

The representation number of a graph is the least positive integer $k$ for which its vertices can be arranged in a word, each occurring $k$ times, so that two distinct letters alternate precisely when the corresponding vertices are adjacent. We prove that every bipartite graph on $N\ge9$ vertices has representation number at most $\lceil N/4\rceil$. Together with the known representation number of crown graphs, this settles the conjecture that crowns maximise the representation number among bipartite graphs of the same order. The proof develops a construction of Mozhui and Krishna by reducing the choice of a representing word to an ordering problem for neighbourhoods. We characterise the obstructions to this ordering and use probability estimates to exclude them for all sufficiently large balanced bipartitions. Two finite assertions complete the argument, each established by a checked Boolean unsatisfiability certificate. A refinement of the ordering argument treats the remaining odd part sizes directly. The main theorem and the crown-extremality corollary, including the finite certificate arguments, have also been formalised and verified in Lean 4.

0.25