Directed Hypergraphs: Problems, Algorithmic Results, and A Novel Decremental Approach
Directed Hypergraphs: Problems, Algorithmic Results, and A Novel Decremental Approach
Directed Hypergraphs: Problems, Algorithmic Results, and A Novel Decremental Approach
net/publication/220829288
CITATIONS READS
50 116
3 authors:
Daniele Frigioni
Università degli Studi dell'Aquila
95 PUBLICATIONS 1,047 CITATIONS
SEE PROFILE
All content following this page was uploaded by Paolo Franciosa on 10 January 2015.
A. Restivo, S. Ronchi Della Rocca, L. Roversi (Eds.): ICTCS 2001, LNCS 2202, pp. 312–328, 2001.
c Springer-Verlag Berlin Heidelberg 2001
Directed Hypergraphs: Problems, Algorithmic Results 313
for representing problem solving relationships (And-Or graphs [32] and recur-
sive label node hypergraphs [15]), in database theory for representing functional
dependencies among attributes (FD-graphs [5] and connections in acyclic hyper-
graphs [29,36]), in deductive databases [23], in fuzzy logic, for determining the
reliability of facts [8], in propositional logic, for satisfiability check (namely in
the case of Horn formulæ [9,21,33]), in formal languages (weighted context free
grammars [26]), in the theory of concurrency (Petri net paths [37]), in model
checking (dependency graphs [28] and boolean graphs [3]), in diagnostics [2].
More applications can be found in [1,4,34].
In all these applications we need to provide a formal representation for a set
of many-to-one implications and to study properties of the resulting structures
such as assessing reachability, evaluating flows and cuts, determining less ex-
pensive implication chains under various cost criteria (‘shortest’ hyperpaths). In
most cases determining hypergraph properties that consist in generalizations of
corresponding properties on ordinary graphs is a much more complex (usually
NP-hard) task. Therefore, the study of particular polynomial restrictions and of
polynomial time approximation algorithms is quite important and constitutes
a largely still unexplored field.
The purpose of this paper is twofold. First we want to review several basic
combinatorial problems that have been stated in terms of directed hypergraphs
and have been studied in the literature in the framework of different application
domains. Among them, transitive closure and transitive reduction [6,10], flow
and cut problems [16,21], minimum weight traversal problems [12,21,35]. For
such problems we illustrate some of the most important algorithmic results in
the context of both static and dynamic (mostly incremental) applications.
In second place, we want to address a specific dynamic problem which finds
several interesting applications especially in the framework of knowledge rep-
resentation: the maintenance of minimum weight hyperpaths under hyperarc
deletions and weight increases. For such problem we provide a new efficient al-
gorithm applicable for a large variety of hyperpath weight measures.
The paper is organized as follows. In section 2 the basic definitions con-
cerning hypergraphs and hyperpaths are given and various hyperpath weight
measures are presented. In Section 3 the problems of transitive closure and tran-
sitive reduction are discussed and the main algorithmic results are reviewed.
Section 4 is devoted to flows and cuts in hypergraphs. Section 5 is devoted to
hypergraph traversal problems with respect to a variety of hyperpath weight
measures. Finally, in Section 6 we give a summary of algorithmic results in
the dynamic framework and present a new efficient algorithm for maintaining
minimum weight hyperpaths under hyperarc eliminations and weight increase
operations. In the last section we draw some conclusions and suggest future
research directions.
314 Giorgio Ausiello et al.
The following definitions concerning directed hypergraphs are from [6] and [12],
and are consistent with the more general definitions given in [22].
A directed hypergraph H (see Fig. 1 for an example) is a pair N, A, where N
is a non empty set of nodes and A is a set of hyperarcs; a hyperarc e is an ordered
pair T, h, with T ⊆ N , T = ∅, and h ∈ N \ T ; T and h are called the tail and
the head of e, and are denoted by tail(e) and head(e), respectively. A set of
nodes is called a source set if it is the tail of some hyperarc; the source area of
H is the sum of the cardinalities of its source sets. The forward star of v ∈ N
is the set fstar(v) = {e ∈ A : v ∈ tail(e)}, while the backward star of v is the set
bstar(v) = {e ∈ A : v = head(e)}.
a
h5 e
h1 b
h2
h6 h8 h9
s h3 c t
h4
d h7 f
h10
The size of a hypergraph H is defined as size(H) = e∈A |tail(e)|. The
following different notion of size has been also used in the literature: a “compact”
hypergraph Hc is derived from H where a set of p hyperarcs having the same
tail T is represented by a single hyperarc from T to a dummy node c, plus p
hyperarcs from c to the original heads; the size of this hypergraph is denoted by
minsize(H) = size(Hc ). This parameter is called size of a hypergraph H in [12],
and is denoted by |H|.
Given a hypergraph H, a subhypergraph of H is a hypergraph H = N , A
with N ⊆ N and A ⊆ A. A subhypergraph is proper if at least one of the
inclusions is strict. A hyperpath in H from a set of nodes S ⊂ N, with S = ∅,
called source, to a target node t ∈ N is a subhypergraph ΠS,t = NΠS,t , AΠS,t
of H having the following property: if t ∈ S, then AΠS,t = ∅, otherwise its k ≥ 1
hyperarcs can be ordered in a sequence e1 , . . . , ek such that:
1. ∀ei ∈ AΠS,t , tail(ei ) ⊆ S ∪ {head(e1 ), . . . , head(ei−1 )}
2. t = head(ek )
3. No proper subhypergraph of ΠS,t is a hyperpath from S to t in H.
Directed Hypergraphs: Problems, Algorithmic Results 315
Let ΠS,t be a hyperpath from S to t, and let Z, t be the last hyperarc
in ΠS,t (i.e., the port of t), where Z = {z1 , z2 , . . . , zk }: then1 ΠS,t = ΠS,z1 ∪
ΠS,z2 ∪ . . . ∪ ΠS,zk ∪ {Z, t}, where ΠS,zi is the subhyperpath of ΠS,t going
from S to zi , 1 ≤ i ≤ k. The weight of ΠS,t depends on wZ,t , that gives the
weight of hyperarc Z, t, and on ψZ,t , that takes into account the weights of all
hyperpaths ΠS,zi . Function fZ,t combines these two weights. This is formalized
in the following definition.
Several weight measures have been introduced in the literature to define the
weight of a hyperpath in a functional directed hypergraph, by considering, given
a hyperarc e such that tail(e) = {x1 , x2 , . . . , xk }, different choices for functions
ψe and fe :
rank: fe (x, y) = x + y, ψe (x1 , x2 , . . . , xk ) = max1≤i≤k {xi }, and µ0 = 0;
gap: fe (x, y) = x + y, ψe (x1 , x2 , . . . , xk ) = min1≤i≤k {xi }, and µ0 = 0;
threshold: fe (x, y) = max {x, y}, ψe (x1 , x2 , . . . , xk ) = max1≤i≤k {xi }, and
µ0 = 0;
1
By a little abuse of notation, given two hypergraphs H1 = N1 , A1 and H2 =
N2 , A2 we denote the hypergraph N1 ∪ N2 , A1 ∪ A2 by H1 ∪ H2 .
316 Giorgio Ausiello et al.
Transitive closure.
In [6] the authors introduce the notion of transitive closure of a directed hy-
pergraph H = N, A as the hypergraph H+ = N, A+ such that X, i is
a hyperarc in A+ if and only if one of the following conditions hold:
– X, i ∈ A
– i∈X Extended reflexivity
– there exists a set of nodes Y = {n1 , n2 , . . . , nq } such that for each 1 ≤ j ≤ q,
X, nj ∈ A+ and Y, i ∈ A Extended transitivity
Note that, in our framework such definition is equivalent to say that a hy-
perarc X, i is in A+ if and only if there is a hyperpath in H from X to i. If X
and Y are singletons, then the extended reflexivity and transitivity coincide with
the usual notions of reflexivity and transitivity of graphs. Furthermore, note that
the size of the closure of a directed hypergraph can be exponential in the number
of nodes of the hypergraph, in fact, set X can be any element of 2N (the power
set of N ).
In the same paper it is shown that using a suitable representation of H, i.e.,
its FD-graph and the closure of the FD-graph (see [6] for the definitions), it
is possible to compute the transitive closure of a directed hypergraph without
falling into the exponential explosion of the hypergraph closure. In fact, the FD-
graph closure grows at most quadratically. Using this approach the transitive
closure of H is computed in O(size(H) · ns ) worst case time, where ns is the
number of source sets of H.
Directed Hypergraphs: Problems, Algorithmic Results 317
Transitive reduction.
The problem of finding the transitive reduction of a directed hypergraphs, that
is finding a minimal hypergraph that has the same closure of a given one, is
much more complex than in the case of graphs for two main reasons: i) the
closure of a hypergraph has an exponential number of hyperarcs; ii) in the case
of hypergraphs it is possible to define minimality with respect to a variety of
parameters, while in the case of graph the only notion of minimality is with
respect to the number of arcs. In [6], minimality in hypergraphs is defined with
respect to the following criteria:
1. minimum size;
2. minimum number of hyperarcs;
3. minimum number of source sets;
4. minimum source area.
In the same paper, it has been shown that, given a directed hypergraph H,
the problems of deciding whether there exists a hypergraph H with the same
closure of H, such that H is minimum with respect to criteria 1, 2 or 4 are
NP-hard, while deciding whether there exists a hypergraph H with the same
closure of H having the minimum number of source sets is polynomial and can
be done in O(size(H) · ns ) worst case time. Notice that the transitive reduction
of a directed graph, that corresponds to minimality with respect to number of
hyperarcs in a directed hypergraph, can be computed in polynomial time.
Flows in hypergraphs.
Flows in hypergraphs, also known as hyperflows, have been recently introduced
as generalizations of flows in graphs. In particular, in [16] the minimum cost
hyperflow problem is considered and some analogies with the standard minimum
cost flow problem in directed graphs are shown.
In what follows, we summarize the results given in [16]. Given a directed
hypergraph H = N, A, an upper capacity u(e) and a cost c(e) are associated
with each e ∈ A, and a positive real multiplier mv (e) is associated with each
v ∈ tail(e). Moreover, a real demand b(v) is associated with each v ∈ N . A flow
in H is a function f : A → R, that satisfies the following conservation constraint:
f (e) − mv (e)f (e) = b(v), ∀v ∈ N
head(e)=v v∈tail(e)
0 ≤ f (e) ≤ u(e), ∀e ∈ A
Cuts in hypergraphs.
The notion of cut in a directed hypergraph has been defined in [21] as follows.
A cut Cst between two nodes s and t of a directed hypergraph H = N, A is
a partition of N into two subsets Ns and Nt such that s ∈ Ns and t ∈ Nt . The
associated cutset is the set of all hyperarcs e ∈ A such that tail(e) ⊆ Ns and
head(e) ∈ Nt . The size of a cut is the number of hyperarcs in its cutset.
It is well known that the unsatisfiability of a propositional Horn formula
corresponds to the existence of a hyperpath in a hypergraph connecting two
special nodes s and t, where s corresponds to True and t to False [9,19]. As
a consequence, it is clear that the Maximum Horn Sat problem can be reduced to
the problem of finding a minimum cardinality cut in a directed hypergraph, i.e.,
a cut whose associated cutset has the minimum number of hyperarcs. In [21], the
authors also show that the latter problem is equivalent to the problem of finding
the minimum set of hyperarcs of H such that each hyperpath of H contains at
least one of these hyperarcs. Therefore, the minimum cardinality cut problem
can be formulated as the problem of assigning 0/1 weights to the hyperarcs of
H in order to make the weight of each hyperpath larger than or equal to 1, and
to minimize the sum of the assigned weights.
Based on this result, the authors propose three different IP formulations
for the minimum cardinality cut problem, by using three different measures to
assign hyperpath weights, that is: the cost, the distance (rank ), and the value
(traversal cost ). They also show that these three formulations and the well known
ILP formulation of the Max Horn SAT problem are all equivalent.
Finally, they investigate the properties of the relaxations of these IP for-
mulations by showing that they define a hierarchy. The weakest relaxation in
Directed Hypergraphs: Problems, Algorithmic Results 319
the hierarchy, that is the relaxation of the formulation making use of the value
(traversal cost ) weight function, is shown to correspond to the dual of a hyper-
graph max flow problem with unit capacities [16]. This implies that the well-
known max-flow-min-cut theorem for directed graphs (see, e.g., [17]) holds in
the case of directed hypergraphs with unit upper capacities. For example, if we
assume unit upper capacities for all the hyperarcs in the hypergraph of Fig. 1,
and mv (e) = 1/|tail(e)| for each v ∈ tail(e), then the minimum cut and the
maximum flow are both equal to 2.
In the case of non unit upper capacities, the size of a cut is the sum of the
upper capacities of the hyperarcs in the cutset. An interesting feature of hyper-
graphs is that, if hyperarcs have arbitrary upper capacities, then the max-flow-
min-cut theorem does not hold any longer, even in the restrictive case in which
we fix mv (e) = 1/|tail(e)| for each v ∈ tail(e). In fact, if in the hypergraph shown
in Fig. 1 we assume the following upper capacities: u(h1 ) = u(h2 ) = u(h3 ) =
u(h4 ) = 10, u(h5 ) = 2, u(h6 ) = 1, u(h7 ) = 1, u(h8 ) = 1, u(h9 ) = 4, u(h10 ) = 1,
then the minimum cut is 3 (partitioning nodes into the sets {s, a, b, c, d, f } and
{e, t}), while the maximum flow is 5.
weight resulting
measure µ fe (we , ψe ) ψe (µ1 , . . . , µk ) properties
rank + max
we > 0 SSUP SUP, WINF SSUP
gap + min
we > 0 SSUP WSUP, INF SWSUP
bottleneck min min
we > 0 WSUP, INF WSUP, INF WSUP, INF
threshold max max
we > 0
traversal cost
SUP, WINF
+
P
SUP, WINF SUP, WINF
handle any sequence of hyperarc deletions and weight increase operations. This
improves over the solution in [35] when applied to the decremental maintenance
of minimum rank hyperpaths in the case of integer hyperarc weights in [1, C].
In the next subsection, we propose a new decremental algorithm, with respect
to those given in [7,35], that applies to all weight function in SWSUP. This
algorithm is based on a novel approach, since it essentially performs a bfs-like
visit, rather than a Dijkstra-like visit.
is pruned any time a hyperarc is found that does not belong to any minimum
weight hyperpath and/or whose weight does not change.
The i-th iteration of the for loop at Line 5 identifies the set of nodes hav-
ing weight i (after the update), whose weight and/or port changes due to the
hyperarc update, by selecting all nodes v such that w(v) = i, w (v) = i and
p (v) = p(v), and all nodes v such that w(v) < i and w (v) = i.
Inspected nodes are temporarily stored in an array of sets of nodes, named
NewWeightSet. A node v is put in NewWeightSet(i) if and only if w (v) is
known to be at least i. Nodes are extracted from set NewWeightSet(i) by in-
creasing i, and for each node v we check whether there is a hyperarc h such
that fh (wh , ψh (tail(h))) = i. If this is the case, the weight of node v is set to i,
otherwise v is inserted into some set NewWeightSet(j), where j > i, for future
inspection.
Procedure Update(e,v), called at Lines 2 and 16 of Procedure
Weight Increase, updates F (e), by re-evaluating ψe and fe under the increase
of weight(v), v ∈ tail(e), or we .
Directed Hypergraphs: Problems, Algorithmic Results 325
7 Concluding Remarks
There is a large body of results on implicative structures, that is structures in
which we need to provide a formal representation for a set of many-to-one impli-
cations and to study the resulting properties, such as determining less expensive
implication chains under various cost criteria. Our aim has been to illustrate the
most important problems and the main algorithmic results that are available in
the literature. Besides we have discussed in particular the problem of maintain-
ing chains of implications under implication elimination. This problem consists
of maintaining minimum hyperpaths (under some minimality criteria) under hy-
perarc deletions, and can be efficiently tackled for several natural hyperpath
weight measures.
It is worth noting that the higher complexity of the problems we have dis-
cussed in this paper with respect to the complexity of the corresponding prob-
lems in graphs, arises from the peculiar combinatorial features of implicative
structures (see, e.g., [12,31] for the notions of path, distance, cycle, etc). The
comprehension of such aspects can be greatly enhanced by making use of a uni-
form representation of implicative structures in terms of directed hypergraphs.
326 Giorgio Ausiello et al.
Future research directions might address various goals. On one side, it would
be desirable to determine hypergraph properties under which hypergraph prob-
lems become tractable; on the other side, approximability properties of hyper-
graph problems should be better explored; finally, since the connection between
flows and cuts in hypergraphs is significantly different with respect to graphs, the
complexity of the various formulations of flow problems in hypergraphs deserves
further investigation.
References
1. P. Alimonti, E. Feuerstein, and U. Nanni. Linear time algorithms for liveness
and boundedness in conflict–free petri nets. In Proceedings of Latin American
symposium on Theoretical INformatics (LATIN’92), volume 583 of Lecture Notes
in Computer Science, pages 1–14. Springer-Verlag, 1992. 313, 319
2. C. Alonso, B. Pulido, and G. G. Acosta. On line industrial diagnosis : an attempt
to apply artificial intelligence techniques to process control. In 11th International
Conference on Industrial and Engineering Applications of Artificial Intelligence
and Expert Systems (IEA-98-AIE), volume 1415 of Lecture Notes in Artificial In-
telligence, pages 804–813. Springer-Verlag, 1998. 313
3. H. R. Andersen. Model checking and boolean graphs. Theoretical Computer Sci-
ence, 126(1):3–30, 1994. 313
4. J. Aráoz. Forward chaining is simple(x). Operations Research Letters, 26:23–26,
2000. 313
5. G. Ausiello, A. D’Atri, and D. Saccà. Graph algorithms for functional dependency
manipulation. Journal of the ACM, 30(4):752–766, 1983. 313
6. G. Ausiello, A. D’Atri, and D. Saccà. Minimal representation of directed hyper-
graphs. SIAM Journal on Computing, 15(2):418–431, 1986. 313, 314, 316, 317
7. G. Ausiello, P. G. Franciosa, D. Frigioni, and R. Giaccio. Decremental mainte-
nance of minimum rank hyperpaths and minimum models of Horn formulæ. Tech-
nical Report ALCOMFT-TR-01-19, IST Programme of the EU IST-1999-14186
(ALCOM-FT), 2001. http://www.brics.dk/cgi-alcomft/db?state=reports. 322,
323, 325
8. G. Ausiello and R. Giaccio. On-line algorithms for satisfiability problems with
uncertainty. Theoretical Computer Science, 171(1–2):3–24, 1997. 313, 319, 322
9. G. Ausiello and G. F. Italiano. On-line algorithms for polynomially solvable satis-
fiability problems. Journal of Logic Programming, 10(1/2/3–4):69–90, 1991. 313,
318, 319, 322
10. G. Ausiello, G. F. Italiano, and U. Nanni. Dynamic maintenance of directed hy-
pergraphs. Theoretical Computer Science, 72(2-3):97–117, 1990. 313, 322
11. G. Ausiello, G. F. Italiano, and U. Nanni. Optimal traversal of directed hyper-
graphs. Technical Report TR-92-073, International Computer Science Institute,
Berkeley, CA, September 1992. 315, 319
12. G. Ausiello, G. F. Italiano, and U. Nanni. Hypergraph traversal revisited: Cost
measures and dynamic algorithms. In Symposium on Mathematical Foundations of
Computer Science (MFCS’98), volume 1450 of Lecture Notes in Computer Science,
pages 1–16. Springer-Verlag, 1998. 313, 314, 315, 321, 325
13. C. Berge. Graphs and Hypergraphs. North-Holland, Amsterdam, The Netherlands,
1973. 312
Directed Hypergraphs: Problems, Algorithmic Results 327