1

Hardness Results on Finding Leafless
Elementary Trapping Sets and Elementary

arXiv:1711.10543v1 [] 28 Nov 2017

Absorbing Sets of LDPC Codes
Ali Dehghan and Amir H. Banihashemi, Senior Member, IEEE
Department of Systems and Computer Engineering, Carleton University, Ottawa, Ontario, Canada

Abstract
Leafless elementary trapping sets (LETSs) are known to be the problematic structures in the error
floor region of low-density parity-check (LDPC) codes over the additive white Gaussian (AWGN)
channel under iterative decoding algorithms. While problems involving the general category of trapping
sets, and the subcategory of elementary trapping sets (ETSs), have been shown to be NP-hard, similar
results for LETSs, which are a subset of ETSs are not available. In this paper, we prove that, for a
general LDPC code, finding a LETS of a given size a with minimum number of unsatisfied check nodes
b is NP-hard to approximate with any guaranteed precision. We also prove that finding the minimum
size a of a LETS with a given b is NP-hard to approximate. Similar results are proved for elementary
absorbing sets, a popular subcategory of LETSs.
Index Terms: Low-density parity-check (LDPC) codes, trapping sets (TS), elementary trapping sets
(ETS), leafless elementary trapping sets (LETS), absorbing sets (ABS), elementary absorbing sets
(EABS), computational complexity, NP-hardness.

I.

INTRODUCTION

The error floor of low-density parity-check (LDPC) codes under iterative decoding algorithms
is attributed to certain combinatorial structures in the Tanner graph of the code, collectively
referred to as trapping sets. A trapping set is often classified by its size a and the number of
unsatisfied check nodes b in its induced subgraph. In this case, the trapping set is said to belong
to the (a, b) class. The problematic trapping sets that cause the error floor depend not only
on the Tanner graph of the code, but also on the channel model, quantization scheme and the
decoding algorithm. For variable-regular LDPC codes over the additive white Gaussian noise

2

(AWGN) channel, the culprits are known to be a subcategory of trapping sets, called leafless
elementary trapping sets (LETSs) [1], [2]. Leafless ETSs are also the majority of problematic
structures in the error floor region of irregular LDPC codes over the AWGN channel [3]. The
term “elementary” indicates that all the check nodes in the induced subgraph of the trapping set
have degree one or two, and the term “leafless” means that each variable node is connected to
at least two satisfied check nodes, i.e., the normal graph [1] of the trapping set contains no leaf.
There has been a flurry of research activity to characterize different categories of trapping
sets and to devise search algorithms to find them [1] – [8]. In particular, recently, Hashemi and
Banihashemi [2] proposed a characterization of LETSs for variable-regular Tanner graphs based
on a hierarchy of graphical structures that starts from a simple cycle and expands recursively
to reach the targeted LETS. The characterization, referred to as dpl, is based on three simple
expansion techniques, dubbed dot (degree-one-tree), path, and lollipop, and has the property that
it generates a LETS at each and every step of the expansion process. Within this framework, the
authors of [2] proved the optimality of dpl search, in that, it can find LETSs within a certain range
of a ≤ amax and b ≤ bmax , exhaustively, by starting from simple cycles whose maximum length
is minimized, and by generating the minimum number of undesirable structures that are outside
the range of interest. The complexity of the dpl search of [2] depends highly on the multiplicity
of short simple cycles in the graph and the number of LETS structures in different classes within
the range of the search. It was shown in [9] that the multiplicities of simple cycles of different
fixed lengths in random bipartite graphs tend to independent Poisson random variables with fixed
expected values, as the size of the graph tends to infinity (for fixed degree distributions). It was
further shown in [10] that the average multiplicity of LETS structures within different (a, b)
classes, where a and b are fixed values, tends to zero or a non-zero constant asymptotically.
While these results verify the efficiency of the dpl search on average and for small (fixed)
values of amax and bmax , they do not provide much insight into the worst-case computational
complexity of the algorithm.
McGregor and Milenkovic [11] studied the computational complexity of finding different
categories of trapping sets. In particular, they showed that for a given a, finding an (a, b) trapping
set with minimum b is an NP-hard problem. Also, given b, it was shown that finding an (a, b)
ETS with minimum a is NP-hard [11]. In fact, the results of [11] indicate that, for any constant
ǫ, there is no polynomial-time ǫ-approximation algorithm for any of the two problems, unless
RP=NP or P=NP, respectively. On the other hand, when a problem is NP-hard, the restricted

3

cases of that problem can be NP-hard or polynomial time solvable. We thus cannot judge the
computational complexity of finding LETSs based on that of finding ETSs. Moreover, to the
best of our knowledge, there is no result on the worst-case computational complexity of finding
LETSs. The fact that LETSs are the main problematic structures in the error floor region of LDPC
codes over the AWGN channel [2], [12], however, makes such a problem worth investigating.
In this paper, we study the computational complexity of finding LETSs in variable-regular
LDPC codes. In particular, we consider the following two problems: (i) for a given (dv , dc )regular Tanner graph G and an integer a, find an (a, b) LETS with minimum b in G, and (ii) for a
given b, find a LETS with minimum size a in G. We prove that both problems are NP-hard, even
to approximate with any guaranteed precision, no matter how fast the precision scales with the
size of the problem. This implies that there is no polynomial-time algorithm to even approximate
the solution to any of these problems, unless P = NP. In addition, we study the computational
complexity of finding elementary absorbing sets (EABS), a subcategory of LETSs. Absorbing
sets are the fixed points of bit-flipping decoding algorithms [13], [14], and are also shown to be
relevant in the context of quantized decoders over the AWGN channel [14]. Among absorbing
sets, the elementary ones are known to be the most problematic. We note that EABSs and LETSs
are identical sets for variable-regular LDPC codes with dv = 3. For other values of dv , EABSs
are a subset of LETSs. For EABSs, we prove that both Problems (i) and (ii) are still NP-hard,
even to approximate with any guaranteed precision.
The organization of the rest of the paper is as follows: In Section II, we present some
preliminaries including some definitions and notations. This is followed in Sections III and
IV by our results on the worst-case computational complexity of finding LETSs and EABSs,
respectively. The paper is concluded with some remarks in Section V.
II. P RELIMINARIES
We say that a graph G is simple if it has no loop or parallel edges. Throughout this paper,
all graphs are simple. For a graph G, we denote the node set and the edge set of G by V (G)
and E(G), or by V and E (if there is no ambiguity about the graph), respectively. The number
of edges connected to a node v is called the degree of v, and is denoted by d(v). Also, the
maximum degree and the minimum degree of a graph G, denoted by ∆(G) and δ(G), respectively,
are defined to be the maximum and the minimum degree of its nodes, respectively. A node v
is called leaf if d(v) = 1. A leafless graph is a graph G with δ(G) ≥ 2. In this work, we

4

consider graphs to be connected (note that disconnected graphs can be considered as the union
of connected ones).
A graph G = (V, E) is called bipartite if the node set V can be partitioned into two disjoint
subsets U and W , i.e., V = U ∪ W and U ∩ W = ∅, such that every edge in E connects a node
from U to a node from W . Such a bipartite graph is denoted by G = (U ∪ W, E).
Each m × n parity check matrix H of a linear block code of block length n, in general, and
an LDPC code, in particular, can be represented by a bipartite (Tanner) graph G = (U ∪ W, E),
where U = {u1 , u2 , . . . , un } is the set of variable nodes and W = {w1 , w2 , . . . , wm } is the set
of check nodes. A Tanner graph is called variable-regular with variable degree dv if the degree
of every variable node is dv . Also, a (dv , dc )-regular Tanner graph is a variable-regular Tanner
graph in which the degree of every check node is dc . For an LDPC code (Tanner graph), if H
is full-rank, the rate is given by R = 1 − d¯v /d¯c , where d¯v and d¯c are the average variable and
check degrees, respectively. In this work, we consider LDPC codes (Tanner graphs) in which
d¯v is constant with respect to n. This implies that, given R, in the asymptotic regime where
n → ∞, the density of H and that of the Tanner graph tends to zero. This is consistent with
the term “low-density” in “low-density parity-check.”
Let G = (U ∪ W, E) be a bipartite graph. For a set S, where S ⊆ U, the set N(S), where
N(S) ⊆ W , denotes the set of neighbors of S in G. Also, the induced subgraph G(S) of S
in G, is defined as the graph with the set of nodes S ∪ N(S) and the set of edges {ui wj :
ui wj ∈ E, ui ∈ S, wj ∈ N(S)}. In the graph G(S), the set of check nodes with odd and even
degrees are denoted by No (S) and Ne (S), respectively. Also, the terms unsatisfied check nodes
and satisfied check nodes are used to refer to the check nodes in No (S) and Ne (S), respectively.
For a given Tanner graph G = (U ∪ W, E), a set S ⊂ U is called an (a, b) trapping set (TS)
if |S| = a and |No (S)| = b. An elementary trapping set (ETS) is a trapping set for which each
check node in G(S) has degree either one or two. For a given set S, S ⊂ U, we say that S is a
leafless ETS (LETS) if S is an ETS and if the graph which is obtained from G(S) by removing
all the check nodes of degree one and their incident edges is leafless. An absorbing set (ABS)
S is a TS for which all the variable nodes in S are connected to more nodes in Ne (S) than in
No (S). Also, an elementary absorbing set (EABS) S is an ABS for which all the check nodes
in G(S) have degree either one or two.
Consider a formula Φ = (X, C) in Boolean logic, where the two sets X = {x1 , . . . , xn } and
C = {c1 , . . . , cm } are the sets of variables and clauses of Φ, respectively. Each variable can take

5

one of the two truth values “True (1 or T )” or “False (0 or F ).” A truth assignment ℓ(x), x ∈ X,
for Φ = (X, C) is an assignment of truth values to all the variables in X, with corresponding
assignment of a truth value to Φ. We use the notation ℓ̄ for a truth assignment whose truth values
ℓ̄(x) are T or F if and only if the corresponding truth values ℓ(x) of ℓ are F or T , respectively.
We say that a formula Φ is in conjunctive normal form (CNF) if it is a conjunction of clauses,
where a clause is a disjunction of literals. A literal is either a variable x or the negation ¬x of a
variable x. For example, (x ∨ ¬y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ ¬y ∨ ¬z) is a CNF formula with the set
of variables {x, y, z} and the set of clauses {(x ∨ ¬y ∨ z), (x ∨ y ∨ z), (x ∨ ¬y ∨ ¬z)}. Throughout
this paper, all the formulas are assumed to be in conjunctive normal form. In the following,
we sometimes represent a CNF formula by the collection of its clauses. With a slight abuse of
notation, and to simplify the equations, we would also refer to a CNF formula Φ = (X, C) to
mean the set of its clauses C.
For a given formula Φ, we say that Φ has a γ–IN–β truth assignment if each clause in Φ has
exactly β literals and there is a truth assignment for Φ such that each clause has exactly γ true
literals. For instance, for the formula (x ∨ y ∨ z) ∧ (¬x ∨ ¬y ∨ z) ∧ (¬x ∨ y ∨ ¬z), the assignment
ℓ : ℓ(x) = T, ℓ(y) = ℓ(z) = F , is a 1–IN–3 truth assignment. A γ–IN–β SAT problem is the
problem of determining whether there exists a γ–IN–β truth assignment for a given formula Φ
(where in Φ every clause contains β literals). We say that a formula is monotone if there is no
negation in the formula.
The following problems are of interest in proving our results:
1) Monotone 1–IN–3 SAT: Given a monotone formula Φ = (X, C) such that every clause in
C contains three variables, is there a 1–IN–3 truth assignment for Φ?
2) Cubic Monotone 1-IN-3 SAT: Given a monotone formula Φ = (X, C) such that every
clause in C contains three variables and every variable appears in exactly three clauses, is
there a 1–IN–3 truth assignment for Φ?
3) Monotone 2–IN–β SAT: Given a monotone formula Υ = (X, C) such that every clause in
C contains β variables, is there a 2–IN–β truth assignment for Υ?
4) Cubic Monotone 2-IN-β SAT: Given a monotone formula Ψ = (X, C) such that every
clause in C contains β variables and every variable appears in exactly three clauses, is
there a 2–IN–β truth assignment for Ψ?
5) α–Monotone 2–IN–β SAT: Given a monotone formula φ = (X, C) such that every clause
in C contains β variables and every variable appears in exactly α clauses, is there a 2–IN–β

6

truth assignment for φ?
Problems 1 and 2 above are shown in [15] and [16], respectively, to be NP-complete. As an
intermediate result to prove the NP-hardness of the problems under consideration, we start from
Problem 1 and demonstrate in three steps, through polynomial-time reductions, that Problems
3–5 are all NP-complete as well.
The problems of direct interest in this work are the followings:
•

Min-b-LETS: Given an (α, β)-regular Tanner graph G and a positive integer a, find the
minimum non-negative integer b such that there is an (a, b) LETS in G.

•

Min-a-LETS: Given a Tanner graph G and a non-negative integer b, find the minimum
positive integer a such that there is an (a, b) LETS in G.

•

Min-b-EABS: Given a (α, β)-regular Tanner graph G and a positive integer a, find the
minimum non-negative integer b such that there is an (a, b) EABS in G.

•

Min-a-EABS: Given a Tanner graph G and a non-negative integer b, find the minimum
positive integer a such that there is an (a, b) EABS in G.

In the rest of the paper, we prove that all the above problems are NP-hard to approximate
with any guaranteed precision, i.e., there is no polynomial-time algorithm to approximate the
solution to any of these problems, unless P = NP.
III. C OMPUTATIONAL C OMPLEXITY

OF

F INDING LETS S

Theorem 1. For any integers α and β satisfying 3 ≤ α ≤ β, Min-b-LETS is NP-hard to
approximate (with any guaranteed precision).
Proof. To prove the result, we reduce Monotone 1–IN–3 SAT to a decision problem corresponding
to Min-b-LETS in four steps.
Step 1. (Reduction of Monotone 1–IN–3 SAT to Monotone 2–IN–β SAT) Let Φ be an instance
of Monotone 1–IN–3 SAT. In this step, we convert the formula Φ into a monotone formula Υ
such that in Υ every clause contains β variables, and there is a truth assignment for variables in
Φ such that each clause in Φ has exactly one true literal if and only if there is a truth assignment
for variables in Υ such that each clause in Υ has exactly two true literals.
We consider three cases: (1)β = 3, (2)β = 4, and (3)β ≥ 5.
Case 1 (β = 3): Assume that ℓ is a 1–IN–3 truth assignment for Φ. It is easy to see that ℓ̄ is
a 2–IN–3 truth assignment for Φ. Hence, Φ has a 1–IN–3 truth assignment if and only if it has
a 2–IN–3 truth assignment. We thus choose Υ = Φ.

7

Case 2 (β = 4): Consider the formula Φ = (X, C) and let x′ be a new variable such that
x′ ∈
/ X. Replace each clause c in the formula Φ with c ∨ x′ , and call the resultant formula
Υ = (X ∪ x′ , C ′ ). If Φ has a 1–IN–3 truth assignment ℓ, then we select a truth assignment ℓ′ for
Υ by defining ℓ′ (x) = ℓ(x), ∀x ∈ X, and ℓ′ (x′ ) = T . It is now easy to see that ℓ′ is a 2–IN–β
truth assignment for Υ. On the other hand, assume that ℓ′ is a 2–IN–β truth assignment for Υ.
If ℓ′ (x′ ) = T , then ℓ′ is also a 1–IN–3 truth assignment for Φ. Otherwise, if ℓ′ (x′ ) = F , then ℓ′
is a 2–IN–3 truth assignment for Φ. In this case, ℓ̄′ will be a 1–IN–3 truth assignment for Φ.
Case 3 (β ≥ 5): Consider the collection of following β − 1 clauses and call them S:
(x1 ∨ x2 ∨ . . . ∨ xβ−1 ∨ y1 ),
(x1 ∨ x2 ∨ . . . ∨ xβ−1 ∨ y2 ),
..
.
(x1 ∨ x2 ∨ . . . ∨ xβ−1 ∨ yβ−2 ),
(y1 ∨ y2 ∨ . . . ∨ yβ−2 ∨ x1 ∨ x2 ).
Assume that ℓ is an arbitrary 2–IN–β truth assignment for S, and let i and j be two arbitrary
integers such that 1 ≤ i < j ≤ β −2. If we have ℓ(yi ) 6= ℓ(yj ), then, based on Assignment ℓ, it is
impossible that both clauses (x1 ∨ x2 ∨ . . . ∨ xβ−1 ∨ yi ) and (x1 ∨ x2 ∨ . . . ∨ xβ−1 ∨ yj ) have exactly
two true literals. Thus, we must have ℓ(y1 ) = ℓ(y2 ) = · · · = ℓ(yβ−2). Since, based on Assignment
ℓ, there must be exactly two true literals in the clause (y1 ∨ y2 ∨ . . . ∨ yβ−2 ∨ x1 ∨ x2 ), and since
β − 2 ≥ 3, we conclude ℓ(y1 ) = ℓ(y2 ) = · · · = ℓ(yβ−2) = F , and thus ℓ(x1 ) = ℓ(x2 ) = T .
Consequently, ℓ(x3 ) = ℓ(x4 ) = · · · = ℓ(xβ−1 ) = F .
For each i, 1 ≤ i ≤ β − 3, consider the collection of following clauses and call them Si :
(xi1 ∨ xi2 ∨ . . . ∨ xiβ−1 ∨ y1i ),
(xi1 ∨ xi2 ∨ . . . ∨ xiβ−1 ∨ y2i ),
..
.
i
(xi1 ∨ xi2 ∨ . . . ∨ xiβ−1 ∨ yβ−2
),
i
(y1i ∨ y2i ∨ . . . ∨ yβ−2
∨ xi1 ∨ xi2 ).
β−3
Now, consider the collection of clauses H = C ∪{∪i=1
Si }, where C is the set of clauses in Φ. In

H, replace each clause c ∈ C (which has 3 variables) with the clause c∨x13 ∨x23 ∨. . . ∨x3β−3 . Call
the resultant formula Υ. In Υ, each clause has exactly β variables. For each i, 1 ≤ i ≤ β − 3, if
ℓ is a 2–IN–β truth assignment for Si , then ℓ(xi3 ) = F . Thus, the formula Φ has a 2–IN–3 truth
assignment if and only if Υ has a 2–IN–β truth assignment. On the other hand, the formula Φ
has a 2–IN–3 truth assignment if and only if it has a 1–IN–3 truth assignment. This completes

8

the proof for this case.
Step 2. (Reduction of Monotone 2–IN–β SAT to Cubic Monotone 2–IN–β SAT) In this step,
we convert Υ to a monotone formula Ψ such that in Ψ every clause contains β variables, every
variable appears in exactly 3 clauses, and there is a truth assignment for Υ such that each clause
in Υ has exactly two true literals if and only if there is a truth assignment for Ψ such that each
clause in Ψ has exactly two true literals.
j

z1

c2

j
z t-1

ztj

k-1 circles

k-1 circles

k-1 circles

k-1 circles

k-1 circles

z 2tj

k-1 circles

k-1 circles

j
z t+1

c1

z2j

c3
k-1 circles

z3tj

Fig. 1. Graph Ft,k,j representing Formula Ωt,k,j .

First, consider the graph Ft,k,j shown in Figure 1. This graph represents a formula in the
following way: Every circle is a variable, every square is a clause and a clause c contains a
variable v if and only if they are connected through an edge in the graph. Call the formula that
is represented by Ft,k,j , Ωt,k,j . In Ωt,k,j , every variable occurs at most three times, each clause
contains exactly k ≥ 3 variables and there is no negation. Parameter j is an index that all the
variables in Ωt,k,j have as superscript. The graph Ft,k,j contains 3t black variable nodes, each of
degree two.
It is easy to see that there are some 2–IN–k truth assignments for Ωt,k,j . For instance, one
can assign T to black and grey variable nodes and F to white ones. Another example is to
assign F to black variable nodes, T to grey and one of the white variable nodes in each group
of k − 2 white nodes, and F to the rest of white nodes. In the following, we prove that in any
2-IN-k truth assignment for Ωt,k,j , the values of all black variable nodes must be equal, i.e.,

9

either they are all assigned “T ,” or they are all equal to “F ” (Fact 1). In Ft,k,j , consider the
j
three black nodes z1j , z2j and zt+1
. Clause c1 contains z1j , Clause c2 contains z2j and Clause c3
j
j
contains zt+1
. Also, there are k − 1 variables, which we call them v1j , v2j , . . . , vk−1
, such that
j
j
j
j
). Assume
∨ v1j ∨ . . . ∨ vk−1
) and c3 = (zt+1
), c2 = (z2j ∨ v1j ∨ . . . ∨ vk−1
c1 = (z1j ∨ v1j ∨ . . . ∨ vk−1
j
that ℓ is a 2–IN–k truth assignment for Ωt,k,j . Then, we must have ℓ(z1j ) = ℓ(z2j ) = ℓ(zt+1
).

Otherwise, it is impossible to have exactly two true literals in all three clauses c1 , c2 and c3 .
Using a similar argument, one can see that in any 2-IN-k truth assignment, the values of all the
black variable nodes must be equal
Now, consider the formula Υ′ = (X, C ′ ), which has the same set of variables as Υ = (X, C),
but each clause in C is copied nine times to form C ′ . Each variable xj in Υ′ , therefore, appears
in 3h(xj ) clauses, where h(xj ) ≥ 3. Now, for each variable xj in Υ′ = (X, C ′ ), consider
a copy of the formula Ωh(xj ),β,j . In this formula (corresponding to the graph Fh(xj ),β,j ), let
j
{z1j , z2j , . . . , z3h(x
} be the set of black variable nodes. Replace each appearance of xj in Υ′
j)
j
with one of the variables z1j , z2j , . . . , z3h(x
, and call the resultant formula Υ′′ . Now, consider the
j)
S
set of clauses { xj ∈X Ωh(xj ),β,j ∪ Υ′′ }, and call it Ψ. In Ψ, every clause contains β variables

and every variable appears in exactly three clauses. By Fact 1, it is straightforward to verify that
Formula Ψ has a 2–IN–β truth assignment if and only if Υ has a 2–IN–β truth assignment.

Step 3. (Reduction of Cubic Monotone 2–IN–β SAT to α–Monotone 2–IN–β SAT) In this
step, we convert Ψ to a monotone formula φ such that in φ every clause contains β variables,
every variable appears in α clauses, and Ψ has a 2–IN–β truth assignment if and only if φ has
a 2–IN–β truth assignment. The proof for α = 3 is trivial. In the following, we thus consider
α > 3.
For each variable x in Ψ = (X, C) and each i, 1 ≤ i ≤ α, consider the following clauses and
call them Di,x :
1
1
1
(xi ∨ y1,x
∨ y2,x
. . . ∨ yβ−1,x
),
2
2
2
(xi ∨ y1,x
∨ y2,x
. . . ∨ yβ−1,x
),
..
.
α−3
α−3
α−3
. . . ∨ yβ−1,x
).
∨ y2,x
(xi ∨ y1,x
S
Let T = i,x Di,x . If Ψ has γ variables, then T has α(α − 3)γ clauses. Also, note that for

each x ∈ X and each 1 ≤ i ≤ α, the variable xi appears α − 3 times in T .
For each variable x ∈ X, the set T contains the following clauses:
1
1
1
(x1 ∨ y1,x
∨ y2,x
. . . ∨ yβ−1,x
),

10

1
1
1
(x2 ∨ y1,x
∨ y2,x
. . . ∨ yβ−1,x
),
..
.
1
1
1
(xα ∨ y1,x
∨ y2,x
. . . ∨ yβ−1,x
).

Therefore, if ℓ is a 2-IN-β truth assignment for T , then ℓ(x1 ) = ℓ(x2 ) = · · · = ℓ(xα ) (Fact 2).
Consider α copies of Ψ = (X, C), and for each x ∈ X and i, 1 ≤ i ≤ α, in copy i, replace
all the x variables with xi . Call the resultant formula Ψ′ . Next, consider the union of Ψ′ and the
set of clauses T , and call it φ. In T , xi appears α − 3 times and in Ψ′ , it appears 3 times. Thus,
in total (in φ), Variable xi appears α times.
Now, we show that Ψ has a 2–IN–β truth assignment if and only if φ has a 2–IN–β truth
assignment. Let ℓ be a 2–IN–β truth assignment for φ. Define the assignment f for Ψ such
that f (x) = T or F if ℓ(x1 ) = T or F , respectively. It is easy to see that f is a 2–IN–β truth
assignment for Ψ. Now, assume that f is 2–IN–β truth assignment for Ψ. Define the assignment
ℓ for φ as following:

ℓ(v) =




f (x),







T,



T,






F,





F,

if v = xi , x ∈ X, 1 ≤ i ≤ α
j
if v = y1,x
, 1 ≤ j ≤ α − 3, x ∈ X
j
if v = y2,x
, f (x) = F, 1 ≤ j ≤ α − 3, x ∈ X
j
if v = y2,x
, f (x) = T, 1 ≤ j ≤ α − 3, x ∈ X

Otherwise.

By Fact 2, it is easy to check that ℓ is a 2–IN–β truth assignment for φ.
Step 4. (Reduction of α–Monotone 2–IN–β SAT to Min-b-LETS) Let φ be an instance of
α–Monotone 2–IN–β SAT Problem. We first construct a bipartite graph G = (U ∪ W, E) from
φ: For each variable x and each clause c in φ, we create a variable node x in U, and a check
node c in W , respectively. Next, if Variable x appears in Clause c of φ, we connect the variable
node x to the check node c in G. Clearly, the resultant graph is an (α, β)-regular Tanner graph.
2|W |
We use G as an input instance of Min-b-LETS Problem and select a =
as the input size
α
2|W |
of the LETS. Now, in what follows, we first show that if there is a (
, b) LETS in G, then
α
2|W |
we must have b = 0. Next, we show that there is a (
, 0) LETS in G if and only if φ has
α
a 2–IN–β truth assignment. (We note that the existence of any polynomial-time algorithm that
provides an approximate solution to Min-b-LETS with any guaranteed precision can be used to

11

solve the problem exactly for the input a =

2|W |
, and thus, unless P = NP, such an algorithm
α

does not exist.)
2|W |
, then in the induced
α
subgraph G(S) of S in G, we have |Ne (S)| = |W | and |No (S)| = b = 0 (Fact 3). Let S be a
2|W |
LETS of size a =
in G. If we count the number of edges in G(S) from the U side of the
α
graph, we have
2|W |
× α = 2|W | .
(1)
|E(G(S))| = a × dv =
α
In the following, we show that if G has a LETS S of size a =

On the other hand, by counting the number of edges in G(S) from the W side, we have
|E(G(S))| ≤ 2|N(S)| ≤ 2W ,

(2)

where the first inequality is due to the fact that in a LETS, check degrees are either one or two.
From (1) and (2), we obtain |N(S)| = |Ne (S)| = |W |, and |No (S)| = 0.

2|W |
, 0) LETS
α
S. Define the truth assignment ℓ : X → {T, F }, such that ℓ(x) = T if x ∈ S, and ℓ(x) = F ,
Now, we prove the “only if” part of the main claim. Assume that G has a (

otherwise. By Fact 3, every check node in G is connected to exactly two variable nodes in S
and thus every clause in φ has exactly two true literals. Assignment ℓ is thus a 2–IN–β truth
assignment for φ.
For the “if part” of the claim, assume that φ has a 2–IN–β truth assignment ℓ. Let S be a
subset of U containing all the variables nodes for which ℓ(x) = T . Since ℓ is a 2–IN–β truth
assignment for φ, we have N(S) = Ne (S) = W , and each check node in Ne (S) has degree
two. This means S is a LETS with b = 0. Now, by counting the number of edges form the two
2|W |
2|W |
. Hence, G(S) is a (
, 0) LETS in G.
sides of G(S), we have a =
α
α
Theorem 2. Min-a-LETS is NP-hard to approximate (with any guaranteed precision).
Proof. To prove the result, we reduce Cubic Monotone 1–IN–3 SAT Problem to a decision
problem corresponding to Min-a-LETS Problem.
Let Φ = (X, C) be an instance of Cubic Monotone 1–IN–3 SAT Problem. It is easy to see
that |X| = |C|. Throughout the proof, we use η to denote |X|. First, we construct a Tanner
graph G = (U ∪ W, E) from the formula Φ: For each variable x ∈ X, we create two variable
nodes x1 and x2 in U. For each clause c ∈ C, we create a copy of the gadget Dc,2η+1 shown
in Fig. 2. (In Fig. 2, circles and squares represent variable and check nodes, respectively.) Next,
for each clause c ∈ C, if variable x appears in c, then we connect the variable nodes x1 and x2

12

to the check nodes wc1 and wc2 of the gadget Dc,2η+1 , respectively. (See Fig. 3 for an example
of the Tanner graph G constructed from a cubic monotone formula with three variables in each
clause.)
wc

wc

1

2

gc1

yc1

yc2

ycz

ycz-1

gc2

gc3

Fig. 2. Gadget Dc,z .

Note that Tanner graph G has 5η variable nodes and η(2η + 3) check nodes. We use G as
the input instance of Min-a-LETS Problem and select b = η(2η + 1) as the input value of b.
Now, in the following, we first show that if G has an (a, η(2η + 1)) LETS, then, we must have
a = η + 2η/3 (Fact 10). Next, we prove that G has a (η + 2η/3, η(2η + 1)) LETS if and only if
Φ has a 1–IN–3 truth assignment. (Any polynomial-time algorithm that can solve Min-a-LETS
approximately with any guaranteed precision, can also provide an exact solution to the problem
for the input b = η(2η + 1). Such an algorithm thus cannot exist, unless P = NP.)
The followings are some properties of LETSs in G:
•

Fact 4 Consider a LETS S in G. Then, for each c ∈ C, since the neighbors of the nodes
yc1, yc2 , . . . , yc2η+1 are the same, we have {yc1, yc2 , . . . , yc2η+1 } ⊂ No (S) or {yc1, yc2 , . . . , yc2η+1 } ⊂
Ne (S) or none of the nodes yc1 , yc2, . . . , yc2η+1 is in N(S).

•

Fact 5 For a LETS S in G, if {yc1 , yc2, . . . , yc2η+1 } ⊂ No (S), then gc1 ∈ S, gc2 ∈
/ S and
gc3 ∈
/ S.

•

Fact 6 Consider a LETS S in G with b = η(2η + 1) = 2η 2 + η. Then, for every c ∈ C,
{yc1, yc2, . . . , yc2η+1 } ⊂ No (S). (Otherwise, b is at most η(2η + 3) − (2η + 1) = 2η 2 + η − 1,
which is a contradiction.)

•

Fact 7 For a LETS S in G with b = η(2η + 1), for each c ∈ C, we have gc1 ∈ S, gc2 ∈
/S
and gc3 ∈
/ S. (Follows from Facts 5 and 6.)

13

x1//

x1/

x1

x2

x 2/

x 2//

Fig. 3. Tanner graph G corresponding to the formula (x ∨ x′ ∨ x′′ ) ∧ (x ∨ x′ ∨ x′′ ) ∧ (x ∨ x′ ∨ x′′ ).

•

Fact 8 For a LETS S in G with b = η(2η+1), by Facts 6 and 7, for each c ∈ C, wc1 ∈ Ne (S)
and wc2 ∈ Ne (S). Thus, for each c ∈ C, the check node wc1 has exactly one neighbor in the
set {x1 : x ∈ X}.

•

Fact 9 Similar to Fact 8, for a LETS S in G with b = η(2η + 1), for each c ∈ C, the check
node wc2 has exactly one neighbor in the set {x2 : x ∈ X}.

•

Fact 10 For an (a, b) LETS S in G with b = η(2η + 1), we must have a = η + 2η/3. (This
follows from Facts 7–9 and that the degree of each variable node in {x1 , x2 : x ∈ X} is
three.)

Now, we prove that G has an (η + 2η/3, η(2η + 1)) LETS if and only if Φ has a 1–IN–3 truth
assignment. Assume that G has an (η + 2η/3, η(2η + 1)) LETS S. Define the truth assignment
ℓ : X → {T, F }, such that for each x ∈ X, ℓ(x) = T , if x1 ∈ S, and ℓ(x) = F , otherwise. By
Fact 8, ℓ is a 1–IN–3 truth assignment for Φ. Next, assume that the formula Φ has a 1–IN–3 truth
assignment ℓ. Consider variables x ∈ X with truth value T , and include their corresponding x1
and x2 variable nodes in S. Also, for each c ∈ C, include gc1 in S. It is then easy to see that S

14

is an (η + 2η/3, η(2η + 1)) LETS in G.
IV. C OMPUTATIONAL C OMPLEXITY

OF

F INDING EABS S

Theorem 3. For any integers α and β satisfying 3 ≤ α ≤ β, Min-b-EABS is NP-hard to
approximate (with any guaranteed precision).
Proof. Similar to Step 4 of the proof of Theorem 1, we reduce α–Monotone 2–IN–β SAT Problem
to Min-b-EABS Problem. The construction of the Tanner graph G is identical. In Step 4 of the
2|W |
proof of Theorem 1, we proved that if there is a (
, b) LETS in G, then b = 0, and also that
α
2|W |
there is a (
, 0) LETS in G if and only if the formula φ has a 2–IN–β truth assignment.
α
2|W |
Similarly, it can be proved that if there is a (
, b) EABS in G, then b = 0. Moreover,
α
considering that in a variable-regular Tanner graph, LETSs with b = 0 are identical to EABSs
2|W |
, 0)
with b = 0, we conclude that the necessary and sufficient condition for G to have a (
α
EABS is that the formula φ has a 2–IN–β truth assignment.
Theorem 4. Min-a-EABS is NP-hard to approximate (with any guaranteed precision).
Proof. We reduce Cubic Monotone 1–IN–3 SAT Problem to a decision problem corresponding
to Min-a-EABS Problem.
Let Φ = (X, C) be an instance of Cubic Monotone 1–IN–3 SAT Problem, where η = |X| =
|C|. In the following, we construct a Tanner graph G = (U ∪ W, E) from Φ. For each variable
x ∈ X, we create two variable nodes x1 and x2 in U. For each clause c ∈ C, we create a copy
Fc,2η+1 of the gadget shown in Fig. 4. For every clause c ∈ C, and for every variable x ∈ X that
appears in c, we connect variable nodes x1 and x2 to the check nodes wc1 and wc2 , respectively.
Note that Tanner graph G has 7η variable nodes and η(4η + 4) check nodes. We use G as
the input instance of Min-a-EABS Problem and select b = η(2η + 1) as the input value of b.
Now, in what follows, we first show that if G has an (a, η(2η + 1)) EABS, then we must have
a = 2η + 2η/3 (Fact 18). Next, we prove that G has a (2η + 2η/3, η(2η + 1)) EABS if and
only if Φ has a 1–IN–3 truth assignment. (Again, the fact that any approximate polynomial-time
algorithm can find the exact solution to Min-a-EABS for G and the input b = η(2η + 1) implies
that the problem is NP-hard to approximate.)
In the following, we study some properties of EABSs in G:

15

wc

1

wc

2

gc1

yc1

yc2

gc2

ycz

ycz-1

sc1

gc3

sc2

gc4

scz

scz-1

gc5

Fig. 4. Gadget Fc,z .

•

Fact 11 Consider an EABS S in G. For each c ∈ C, we have either {yc1 , yc2, . . . , yc2η+1 } ⊂
No (S) or {yc1, yc2 , . . . , yc2η+1 } ⊂ Ne (S) or none of the nodes yc1 , yc2, . . . , yc2η+1 is in N(S).
}⊂
} ⊂ No (S) or {s1c , s2c , . . . , s2η+1
Similarly, for each c ∈ C, we have {s1c , s2c , . . . , s2η+1
c
c
Ne (S) or none of the nodes s1c , s2c , . . . , s2η+1
is in N(S).
c

•

Fact 12 For an EABS S in G, if {yc1, yc2, . . . , yc2η+1 } ⊂ No (S), then gc1 ∈ S, gc2 ∈
/ S and
/ S and gc5 ∈
/ S.
} ⊂ No (S), then gc1 ∈ S, gc4 ∈
/ S. Similarly, if {s1c , s2c , . . . , s2η+1
gc3 ∈
c

•

Fact 13 For an EABS S in G, if {yc1, yc2 , . . . , yc2η+1 } ⊂ No (S), then {s1c , s2c , . . . , s2η+1
}⊂
c
Ne (S). (Otherwise variable node gc1 is connected to more nodes in No (S) than in Ne (S),
which is in contradiction with the definition of absorbing sets.) Similarly, if {s1c , s2c , . . . , s2η+1
}⊂
c
No (S), then {yc1, yc2 , . . . , yc2η+1 } ⊂ Ne (S).

•

Fact 14 Consider an EABS S in G with b = η(2η + 1) = 2η 2 + η. For each c ∈ C,
} ⊂ No (S). (Otherwise, by Fact 13, b can
{yc1, yc2, . . . , yc2η+1 } ⊂ No (S) or {s1c , s2c , . . . , s2η+1
c
be at most 2η 2 + η − 1.)

•

Fact 15 Consider an EABS S in G with b = η(2η + 1). For each c ∈ C, gc1 ∈ S, and
exactly one of the variable nodes gc2 , gc3 , gc4 , or gc5 is also in S. (Follows from Facts 13 and
14.)

•

Fact 16 For an EABS S in G with b = η(2η + 1), for each c ∈ C, wc1 , wc2 ∈ Ne (S). (By
Facts 14 and 15, and the definition of absorbing sets.)

•

Fact 17 For an EABS S in G with b = η(2η + 1), for each c ∈ C, the check node wc1 has
exactly one neighbor in the set {x1 : x ∈ X}. Similarly, for each c ∈ C, the check node

16

wc2 has exactly one neighbor in the set {x2 : x ∈ X}.
•

Fact 18 For an (a, b) EABS S in G with b = η(2η + 1), we have a = 2η + 2η/3. (Follows
from Facts 15–17, and that the degree of each variable node in {x1 , x2 : x ∈ X} is three.)

Now, we prove that G has an (η + 2η/3, η(2η + 1)) EABS if and only if Φ has a 1–IN–3 truth
assignment. Assume that G has a (2η + 2η/3, η(2η + 1)) EABS S. Define the truth assignment
ℓ such that for each x ∈ X, ℓ(x) = T if x1 ∈ S, and ℓ(x) = F , otherwise. By Fact 17, ℓ is
a 1–IN–3 truth assignment for Φ. Conversely, assume that Φ has a 1–IN–3 truth assignment ℓ.
Let S be a subset of U such that for each x ∈ X, we have x1 , x2 ∈ S if and only if ℓ(x) = T .
Also, for each c ∈ C, add gc1 and gc2 to S. It is easy to see that S is a (2η + 2η/3, η(2η + 1))
EABS in G.
V. CONCLUSION
In this paper, we discussed the computational complexity of finding leafless elementary trapping sets (LETSs) and elementary absorbing sets (EABSs) of LDPC codes, and proved that
such problems are NP-hard to even approximate with any guaranteed precision. This, under the
assumption of P 6= NP, implies that there does not exist any polynomial-time algorithm to find
such structures (of even the smallest size). The hardness results proved in this paper for LETSs
and EABSs are stronger than similar results proved in [11] for trapping sets and ETSs, in the
sense that, while the results of [11] indicate that there is no polynomial-time ǫ-approximation
algorithm, for any constant ǫ, to solve the TS and ETS problems, our results imply that no
polynomial-time approximation algorithm exists to solve the LETS and EABS problems no
matter how fast the precision of the algorithms scales with the size of the problem.
We also note that the intermediate results obtained in this work on NP-hardness of Monotone
2–IN–β SAT, Cubic Monotone 2-IN-β SAT, and α–Monotone 2–IN–β SAT Problems may be
useful in the study of the hardness of other problems which are of interest in Computer Science
or Coding.
R EFERENCES
[1] M. Karimi and A. H. Banihashemi, “On characterization of elementary trapping sets of variable-regular LDPC codes,”
IEEE Trans. Inform. Theory, vol. 60, no. 9, pp. 5188–5203, Sep. 2014.
[2] Y. Hashemi and A. H. Banihashemi, “New characterization and efficient exhaustive search algorithm for leafless elementary
trapping sets of variable-regular LDPC codes,” IEEE Trans. Inform. Theory, vol. 62, no. 12, pp. 6713– 6736, Dec. 2016.

17

[3] Y. Hashemi and A. H. Banihashemi, “Characterization and efficient exhaustive search algorithm for elementary
trapping sets of irregular LDPC codes,” submitted to IEEE Trans. Inf. Theory, Oct. 2016, available online at:
http://arxiv.org/abs/1611.10014.
[4] G. B. Kyung and C.-C. Wang, “Finding the exhaustive list of small fully absorbing sets and designing the corresponding
low error-floor decoder,” IEEE Trans. Commun., vol. 60, no. 6, pp. 1487–1498, Jun. 2012.
[5] M. Karimi and A. H. Banihashemi, “Efficient algorithm for finding dominant trapping sets of LDPC codes,” IEEE Trans.
Inform. Theory, vol. 58, no. 11, pp. 6942–6958, Nov. 2012.
[6] D. V. Nguyen, S. K. Chilappagari, M. W. Marcellin, and B. Vasić, “On the construction of structured LDPC codes free of
small trapping sets,” IEEE Trans. Inform. Theory, vol. 58, no. 4, pp. 2280–2302, Apr. 2012.
[7] Y. Hashemi and A. H. Banihashemi, “On characterization and efficient exhaustive search of elementary trapping sets of
variable-regular LDPC codes,” IEEE Comm. Lett., vol. 19, no. 3, pp. 323–326, Mar. 2015.
[8] H. Falsafain and S. R. Mousavi, “Exhaustive enumeration of elementary trapping sets of an arbitrary Tanner graph,” IEEE
Comm. Lett., vol. 20, no. 9, pp. 1713–1716, Sep. 2016.
[9] A. Dehghan and A. H. Banihashemi, “On the Tanner graph cycle distribution of random LDPC, random protographbased LDPC, and random quasi-cyclic LDPC code ensembles,” Submitted to IEEE Trans. Inf. Theory, available online at:
http://arxiv.org/abs/1701.02379.
[10] A. Dehghan and A. H. Banihashemi, “Asymptotic average number of different categories of trapping sets, absorbing sets
and stopping sets in random regular and irregular LDPC code ensembles,” submitted to IEEE Trans. Inf. Theory, Apr.
2017, available online at: https://arxiv.org/abs/1705.06798.
[11] A. McGregor and O. Milenkovic, “On the hardness of approximating stopping and trapping sets,” IEEE Trans. Inform.
Theory, vol. 56, no. 4, pp. 1640–1650, Apr. 2010.
[12] B. K. Butler and P. H. Siegel, “Error floor approximation for LDPC codes in the AWGN channel,” IEEE Trans. Inform.
Theory, vol. 60, no. 12, pp. 7416–7441, Dec. 2014.
[13] H. Xiao and A. H. Banihashemi, “Estimation of bit and frame error rates of finite-length low-density parity-check codes
on binary symmetric channels,” IEEE Trans. Commun., vol. 55, no. 12, pp. 2234–2239, Dec. 2007.
[14] L. Dolecek, Z. Zhang, V. Anantharam, M. J. Wainwright, and B. Nikolić, “Analysis of absorbing sets and fully absorbing
sets of array-based LDPC codes,” IEEE Trans. Inform. Theory, vol. 56, no. 1, pp. 181–201, Jan. 2010.
[15] T. J. Schaefer, “The complexity of satisfiability problems,” in Proceedings of the tenth annual ACM symposium on Theory
of computing, pp. 216–226, ACM, 1978.
[16] C. Moore and J. M. Robson, “Hard tiling problems with simple tiles,” Discrete Comput. Geom., vol. 26, no. 4, pp. 573–590,
2001.

