
## 24 **Martin Gebser And Joohyung Lee And Yuliya Lierler**

connected. Then there is a strongly connected component in (X,EC Π(X**)) whose**
atoms Y are not reached from any atom in X \ Y . Clearly Y **is a nonempty proper** subset of X, and so is X \ Y **. Furthermore, for every rule (12) in Π, at least one of** the following conditions holds:

$$|A\cap X|>1\ ,$$
|A ∩ X| > 1 , **(56)**
$$A\cap(X\setminus Y)=\varnothing\ ,$$
A ∩ (X \ Y ) = ∅ , **(57)**
$$\left(57\right)$$
$$B\cap Y=\varnothing\ ,$$
$\left(58\right)$ . 
$\left(59\right)$. 
B ∩ Y = ∅ , **(58)**
or

$$B\cap(X\setminus Y)\neq\emptyset\ .$$
B ∩ (X \ Y ) 6= ∅ . **(59)**
However, (56) contradicts the assumption that Π is HEF. Also the fact that at least one of the conditions (57), (58), and (59) holds contradicts **the assumption**
that X \ Y is outbound in X **for Π.**
From right to left: Assume that the elementary subgraph of X **for Π is strongly**
connected. For every nonempty proper subset Y of X, there is a minimum integer i ≥ 0 such that EC iΠ(X) does not contain any edge from an atom in Y **to an**
atom in X \ Y **, but** EC i+1 Π (X**) contains such an edge. Thus some rule (12) in Π**
satisfies |A ∩ X| = 1 , **(60)**

$$|A\cap X|=1\ ,$$
$$A\cap Y\neq\emptyset\ ,$$
$$(61)$$
A ∩ Y 6= ∅ , **(61)**
$$B\cap(X\setminus Y)\neq\emptyset\ ,$$
$$\operatorname{and}$$
$$B\cap Y=\varnothing\ .$$
(61), since $ Y$ . 
From (60) and (61), since Y ⊆ X,

$\mathcal{X}_{\downarrow}$. 
$$A\cap(X\setminus Y)=\varnothing\ .$$
This shows that Y is outbound in X for Π. We conclude that X **is an elementary**
loop of Π.

Although many properties of HCF programs still apply to HEF programs (e.g.,
equivalence between an HEF program and its shifted variant), the computational complexities of recognizing them are different. While an HCF program can be recognized in polynomial time (by computing the strongly connected components of its dependency graph), Fassetti and Palopoli (2010) showed that deciding whether a disjunctive program is HEF is coNP-complete.10 **Theorem 4 established a similar**
complexity gap by showing that elementary loops are hard to verify in **the case of**
arbitrary disjunctive programs, while for loops it remains a question **of reachability.**