Recently, Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and showed it to be the most efficient machine teaching model satisfying the benchmark for collusion-avoidance set by Goldman and Mathias. A teaching map $T$ for a concept class $\mathcal{C}$ assigns a (teaching) set $T(C)$ of examples to each concept $C \in \mathcal{C}$. A teaching map is non-clashing if no pair of concepts are consistent with the union of their teaching sets. The size of a non-clashing teaching map (NCTM) $T$ is the maximum size of a teaching set $T(C)$, $C \in \mathcal{C}$. The non-clashing teaching dimension $\text{NCTD}(\mathcal{C})$ of $\mathcal{C}$ is the minimum size of an NCTM for $\mathcal{C}$. $\text{NCTM}^+$ and $\text{NCTD}^+(\mathcal{C})$ are defined analogously, except the teacher may only use positive examples. We study NCTMs and $\text{NCTM}^+\text{s}$ for the concept class $\mathcal{B}(G)$ consisting of all balls of a graph $G$. We show that the associated decision problem $\text{B-NCTD}^+$ for $\text{NCTD}^+$ is NP-complete in split, co-bipartite, and bipartite graphs. Surprisingly, we even prove that, unless the ETH fails, $\text{B-NCTD}^+$ does not admit an algorithm running in time $2^{2^{o(\mathtt{vc})}}\cdot n^{\mathcal{O}(1)}$, nor a kernelization algorithm outputting a kernel with $2^{o(\mathtt{vc})}$ vertices, where $\mathtt{vc}$ is the vertex cover number of $G$. We complement these lower bounds with matching upper bounds. These are extremely rare results: it is only the second problem in NP to admit such a tight double-exponential lower bound parameterized by $\mathtt{vc}$, and only one of very few problems to admit such an ETH-based conditional lower bound on the number of vertices in a kernel. For trees, interval graphs, cycles, and trees of cycles, we derive $\text{NCTM}^+\text{s}$ or NCTMs for $\mathcal{B}(G)$ of size proportional to its VC-dimension. For Gromov-hyperbolic graphs, we design an approximate $\text{NCTM}^+$ for $\mathcal{B}(G)$ of size $2$, in which only pairs of balls with Hausdorff distance larger than some constant must satisfy the non-clashing condition.

Abstract. A Robinson space is a dissimilarity space [Formula: see text] (i.e., a set [Formula: see text] of size [Formula: see text] and a dissimilarity [Formula: see text] on [Formula: see text]) for which there exists a total order [Formula: see text] on [Formula: see text] such that [Formula: see text] implies that [Formula: see text]. Recognizing if a dissimilarity space is Robinson has numerous applications in seriation and classification. An mmodule of [Formula: see text] (generalizing the notion of a module in graph theory) is a subset [Formula: see text] of [Formula: see text] which is not distinguishable from the outside of [Formula: see text]; i.e., the distance from any point of [Formula: see text] to all points of [Formula: see text] is the same. If [Formula: see text] is any point of [Formula: see text], then [Formula: see text], and the maximal-by-inclusion mmodules of [Formula: see text] not containing [Formula: see text] define a partition of [Formula: see text], called the copoint partition. In this paper, we investigate the structure of mmodules in Robinson spaces and use it and the copoint partition to design a simple and practical divide-and-conquer algorithm for recognition of Robinson spaces in optimal [Formula: see text] time.

Abstract. One of the open problems in machine learning is whether any set-family of VC-dimension [Formula: see text] admits a sample compression scheme of size [Formula: see text]. In this paper, we study this problem for balls in graphs. For a ball [Formula: see text] of a graph [Formula: see text], a realizable sample for [Formula: see text] is a signed subset [Formula: see text] of [Formula: see text] such that [Formula: see text] contains [Formula: see text] and is disjoint from [Formula: see text]. A proper sample compression scheme of size [Formula: see text] consists of a compressor and a reconstructor. The compressor maps any realizable sample [Formula: see text] to a subsample [Formula: see text] of size at most [Formula: see text]. The reconstructor maps each such subsample [Formula: see text] to a ball [Formula: see text] of [Formula: see text] such that [Formula: see text] includes [Formula: see text] and is disjoint from [Formula: see text]. For balls of arbitrary radius [Formula: see text], we design proper labeled sample compression schemes of size 2 for trees, of size 3 for cycles, of size 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. For balls of a given radius, we design proper labeled sample compression schemes of size 2 for trees and of size 4 for interval graphs. We also design approximate sample compression schemes of size 2 for balls of [Formula: see text]-hyperbolic graphs.

One of the open problems in machine learning is whether any set-family of VC-dimension d admits a sample compression scheme of size O(d). In this paper, we study this problem for balls in graphs. For balls of arbitrary radius r, we design proper sample compression schemes of size 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. We also design approximate sample compression schemes of size 2 for balls of δ-hyperbolic graphs.

We examine connections between combinatorial notions that arise in machine learning and topological notions in cubical/simplicial geometry. These connections enable to export results from geometry to machine learning. Our first main result is based on a geometric construction by Tracy Hall (2004) [20] of a partial shelling of the cross-polytope which can not be extended. From it, we derive a maximum class of VC dimension 3 without corners. This refutes several previous works in machine learning. In particular, it implies that the previous constructions of optimal unlabeled sample compression schemes for maximum classes are erroneous. On the positive side we present a new construction of an optimal unlabeled sample compression scheme for maximum classes. We leave as open whether our unlabeled sample compression scheme extends to ample classes, which generalize maximum classes. Towards resolving this question, we provide a geometric characterization in terms of unique sink orientations of the associated 1-inclusion graph.

This paper considers completions of tope graphs of complexes of oriented matroids (COMs) to ample partial cubes of the same Vapnik--Chervonenkis dimension (VC-dimension). We show that these exist for oriented matroids (OMs) and complexes of uniform oriented matroids (CUOMs). This implies that tope graphs of OMs and CUOMs satisfy the sample compression conjecture---one of the central open questions of learning theory. We conjecture that the tope graph of every COM can be completed to an ample partial cube without increasing the VC-dimension.

The median of a set of vertices P of a graph G is the set of all vertices x of G minimizing the sum of distances from x to all vertices of P. In this paper, we present a linear time algorithm to compute medians in median graphs, improving over the existing quadratic time algorithm. We also present a linear time algorithm to compute medians in the 𝓁₁-cube complexes associated with median graphs. Median graphs constitute the principal class of graphs investigated in metric graph theory and have a rich geometric and combinatorial structure. Our algorithm is based on the majority rule characterization of medians in median graphs and on a fast computation of parallelism classes of edges (Θ-classes or hyperplanes) via Lexicographic Breadth First Search (LexBFS). To prove the correctness of our algorithm, we show that any LexBFS ordering of the vertices of G satisfies the following fellow traveler property of independent interest: the parents of any two adjacent vertices of G are also adjacent.

We provide a counterexample to a conjecture by Thiagarajan (1996, 2002) that regular event structures correspond to event structures obtained as unfoldings of finite 1-safe Petri nets . The same counterexample is used to disprove a closely related conjecture by Badouel, Darondeau, and Raoult (1999). Using that domains of events structures are CAT(0) cube complexes, we construct our counterexample from an example by Wise (1996, 2007) of a nonpositively curved square complex whose universal cover contains an aperiodic plane. We prove that other counterexamples to Thiagarajan's conjecture arise from aperiodic 4-way deterministic tile sets of Kari and Papasoglu (1999) and Lukkarila (2009). On the positive side, using breakthrough results by Agol (2013) and Haglund and Wise (2008, 2012) from geometric group theory, we prove that Thiagarajan's conjecture holds for strongly hyperbolic regular event structures.

International audience

Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices u and v can be determined efficiently by merely inspecting the labels of u and v, without using any other information. One of the important problems is finding natural classes of graphs admitting distance labeling schemes with labels of polylogarithmic size. In this paper, we show that the class of cube-free median graphs on n nodes enjoys distance labeling scheme with labels of O(log^3 n) bits.

Nielsen et al. [35] proved that every 1-safe Petri net N unfolds into an event structure E N . By a result of Thiagarajan [46], these unfoldings are exactly the trace-regular event structures. Thiagarajan [46] conjectured that regular event structures correspond exactly to trace-regular event structures. In a recent paper (Chalopin and Chepoi [12]), we disproved this conjecture, based on the striking bijection between domains of event structures, median graphs, and CAT(0) cube complexes. However, we proved that Thiagarajan’s conjecture is true for regular event structures whose domains are principal filters of universal covers of finite special cube complexes. In the current article, we prove the converse: To any finite 1-safe Petri net N , one can associate a finite special cube complex X N such that the domain of the event structure E N (obtained as the unfolding of N ) is a principal filter of the universal cover X̃ N of X N . This establishes a bijection between 1-safe Petri nets and finite special cube complexes and provides a combinatorial characterization of trace-regular event structures. Using this bijection and techniques from graph theory and geometry (MSO theory of graphs, bounded treewidth, and bounded hyperbolicity), we disprove yet another conjecture by Thiagarajan (from the paper with Yang [48]) that the monadic second-order logic of a 1-safe Petri net (i.e., of its event structure unfolding) is decidable if and only if its unfolding is grid-free. It was proven by Thiagarajan and Yang [48] that the MSO logic is undecidable if the unfolding is not grid-free. Our counterexample is the trace-regular event structure that arises from a virtually special square complex Z. The domain of this event structure Ė Z is the principal filter of the universal cover Z̃ of Z in which to each vertex we added a pendant edge. The graph of the domain of Ė Z has bounded hyperbolicity (and, thus, the event structure Ė Z is grid-free) but has infinite treewidth. Using results of Seese, Courcelle, and Müller and Schupp, we show that this implies that the MSO theory of the event structure Ė Z is undecidable.

In this paper, we study Gromov hyperbolicity and related parameters, that represent how close (locally) a metric space is to a tree from a metric point of view. The study of Gromov hyperbolicity for geodesic metric spaces can be reduced to the study of graph hyperbolicity. Our main contribution in this note is a new characterization of hyperbolicity for graphs (and for complete geodesic metric spaces). This characterization has algorithmic implications in the field of large-scale network analysis, which was one of our initial motivations. A sharp estimate of graph hyperbolicity is useful, {e.g.}, in embedding an undirected graph into hyperbolic space with minimum distortion [Verbeek and Suri, SoCG'14]. The hyperbolicity of a graph can be computed in polynomial-time, however it is unlikely that it can be done in subcubic time. This makes this parameter difficult to compute or to approximate on large graphs. Using our new characterization of graph hyperbolicity, we provide a simple factor 8 approximation algorithm for computing the hyperbolicity of an n-vertex graph G=(V,E) in optimal time O(n^2) (assuming that the input is the distance matrix of the graph). This algorithm leads to constant factor approximations of other graph-parameters related to hyperbolicity (thinness, slimness, and insize). We also present the first efficient algorithms for exact computation of these parameters. All of our algorithms can be used to approximate the hyperbolicity of a geodesic metric space.

We investigate the impact the negative curvature has on the traffic congestion in large-scale networks. We prove that every Gromov hyperbolic network G admits a core, thus answering in the positive a conjecture by Jonckheere, Lou, Bonahon, and Baryshnikov, Internet Mathematics, 7 (2011) which is based on the experimental observation by Narayan and Saniee, Physical Review E, 84 (2011) that real-world networks with small hyperbolicity have a core congestion. Namely, we prove that for every subset X of vertices of a graph with δ-thin geodesic triangles (in particular, of a δ-hyperbolic graph) G there exists a vertex m of G such that the ball B(m, 4δ) of radius 4δ centered at m intercepts at least one half of the total flow between all pairs of vertices of X, where the flow between two vertices x,y ∊ X is carried by geodesic (or quasi-geodesic) (x, y)-paths. Moreover, we prove a primal- dual result showing that, for any commodity graph R on X and any r ≥ 8δ, the size στ(R) of the least r-multi-core (i.e., the number of balls of radius r) intercepting all pairs of R is upper bounded by the maximum number of pairwise (2r – 5δ)- apart pairs of R and that an r-multi-core of size σr–5δ (R) can be computed in polynomial time for every finite set X. Our result about total r-multi-cores is based on a Helly-type theorem for quasiconvex sets in δ-hyperbolic graphs (this is our second main result). Namely, we show that for any finite collection Q of pairwise intersecting ∊-quasiconvex sets of a δ-hyperbolic graph G there exists a single ball B(c, 2∊ + 5δ) intersecting all sets of Q. More generally, we prove that if Q is a collection of 2r-close (i.e., any two sets of Q are at distance ≤ 2r) ε-quasiconvex sets of a δ-hyperbolic graph G, then there exists a ball B(c,r*) of radius r* := max{2e + 5δ, r + e + 3δ} intersecting all sets of Q. These kind of Helly-type results are also useful in geometric group theory. Using the Helly theorem for quasiconvex sets and a primal-dual approach, we show algorithmically that the minimum number of balls of radius 2∊ + 5δ intersecting all sets of a family Q of ∊-quasiconvex sets does not exceed the packing number of Q (maximum number of pairwise disjoint sets of Q). We extend the covering and packing result to set-families KQ in which each set is a union of at most κ ε-quasiconvex sets of a δ-hyperbolic graph G. Namely, we show that if r ≥ ∊ + 2δ and nr (κ Q) is the maximum number of mutually 2r-apart members of κ Q, then the minimum number of balls of radius r + 2∊ + 6δ intersecting all members of KQ is at most 2K2nr(KQ) and such a hitting set and a packing can be constructed in polynomial time for every finite KQ (this is our third main result). For set- families consisting of unions of κ balls in δ-hyperbolic graphs a similar result was obtained by Chepoi and Estellon (2007). In case of δ = 0 (trees) and ∊ = r = 0, (subtrees of a tree) we recover the result of Alon (2002) about the transversal and packing numbers of a set-family in which each set is a union of at most κ subtrees of a tree.

In the bidirected minimum Manhattan network problem, given a set T of n terminals in the plane, no two terminals on the same horizontal or vertical line, we need to construct a network N(T) of minimum total length with the property that the edges of N(T) belong to the axis-parallel grid defined by T and are oriented in a such a way that every ordered pair of terminals is connected in N(T) by a directed Manhattan path. In this article, we present a polynomial factor 2-approximation algorithm for the bidirected minimum Manhattan network problem. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(2), 167–178 2017

In this note, we prove that all cop-win graphs $G$ in the game in which the robber and the cop move at different speeds $s$ and $s'$ with $s'0$, this establishes a new---game-theoretical---characterization of Gromov hyperbolicity. We also show that for weakly modular graphs the dependency between $\delta$ and $s$ is linear for any $s'

In this paper, we present a counterexample to a conjecture of Rozoy and Thiagarajan from 1991 (also called the nice labeling problem) asserting that any (coherent) event structure with finite degree admits a labeling with a finite number of labels or, equivalently, that there exists a function $f:\mathbb{N}\mapsto\mathbb{N}$ such that an event structure with degree $\leq n$ admits a labeling with at most $f(n)$ labels. Our counterexample is based on Burling's construction from 1965 of 3-dimensional box hypergraphs with clique number 2 and arbitrarily large chromatic numbers and the bijection between domains of event structures and median graphs established by Barthélemy and Constantin in 1993.

In the classical cop and robber game, two players, the cop $\mathcal{C}$ and the robber $\mathcal{R}$, move alternatively along edges of a finite graph $G=(V,E)$. The cop captures the robber if both players are on the same vertex at the same moment of time. A graph G is called cop win if the cop always captures the robber after a finite number of steps. Nowakowski and Winkler [Discrete Math., 43 (1983), pp. 235–239] and Quilliot [Problèmes de jeux, de point fixe, de connectivité et de représentation sur des graphes, des ensembles ordonnés et des hypergraphes, Thèse de doctorat d'état, Université de Paris VI, Paris, 1983] characterized the cop-win graphs as graphs admitting a dismantling scheme. In this paper, we characterize in a similar way the class $\mathcal{CWFR}(s,s')$ of cop-win graphs in the game in which the robber and the cop move at different speeds s and $s'$, $s'\leq s$. We also establish some connections between cop-win graphs for this game with $s'1$. In particular, we characterize the graphs which are cop-win for any value of k.

Squaregraphs were originally defined as finite plane graphs in which all inner faces are quadrilaterals (i.e., 4-cycles) and all inner vertices (i.e., the vertices not incident with the outer face) have degrees larger than three. The planar dual of a finite squaregraph is determined by a triangle-free chord diagram of the unit disk, which could alternatively be viewed as a triangle-free line arrangement in the hyperbolic plane. This representation carries over to infinite plane graphs with finite vertex degrees in which the balls are finite squaregraphs. Algebraically, finite squaregraphs are median graphs for which the duals are finite circular split systems. Hence squaregraphs are at the crosspoint of two dualities, an algebraic one and a geometric one, and thus lend themselves to several combinatorial interpretations and structural characterizations. With these and the 5-colorability theorem for circle graphs at hand, we prove that every squaregraph can be isometrically embedded into the Cartesian product of five trees. This embedding result can also be extended to the infinite case without reference to an embedding in the plane and without any cardinality restriction when formulated for median graphs free of cubes and further finite obstructions. Further, we exhibit a class of squaregraphs that can be embedded into the product of three trees, and we characterize those squaregraphs that are embeddable into the product of just two trees. Finally, finite squaregraphs enjoy a number of algorithmic features that do not extend to arbitrary median graphs. For instance, we show that minimum-size median-generating sets of finite squaregraphs can be computed in polynomial time, whereas, not unexpectedly, the corresponding problem for median graphs turns out to be NP-hard. Finite squaregraphs can be recognized in linear time by a Breadth-First-Search.

In this paper, we present a factor 16 approximation algorithm for the following NP-hard distance fitting problem: given a finite set $X$ and a distance $d$ on $X$, find a Robinsonian distance $d_R$ on $X$ minimizing the $l_{\infty}$-error $||d-d_R||_{\infty}=\mbox{max}_{x,y\in X}\{ |d(x,y)-d_R(x,y)|\}.$ A distance $d_R$ on a finite set $X$ is Robinsonian if its matrix can be symmetrically permuted so that its elements do not decrease when moving away from the main diagonalalong any row or column. Robinsonian distances generalize ultrametrics, line distances and occur in the seriation problems and in classification.

δ-Hyperbolic metric spaces have been defined by M. Gromov via a simple 4-point condition: for any four points u,v,w,x, the two larger of the sums d(u,v)+d(w,x), d(u,w)+d(v,x), d(u,x)+d(v,w) differ by at most 2δ. Given a finite set S of points of a δ-hyperbolic space, we present simple and fast methods for approximating the diameter of S with an additive error 2δ and computing an approximate radius and center of a smallest enclosing ball for S with an additive error 3δ. These algorithms run in linear time for classical hyperbolic spaces and for δ-hyperbolic graphs and networks. Furthermore, we show that for δ-hyperbolic graphs G=(V,E) with uniformly bounded degrees of vertices, the exact center of S can be computed in linear time O(|E|). We also provide a simple construction of distance approximating trees of δ-hyperbolic graphs G on n vertices with an additive error O(δlog2 n). This construction has an additive error comparable with that given by Gromov for n-point δ-hyperbolic spaces, but can be implemented in O(|E|) time (instead of O(n2)). Finally, we establish that several geometrical classes of graphs have bounded hyperbolicity.

Given a vector objective function f = (f1,...,fn) defined on a set X, a point y∈X is dominated by a point x∈ X if fi(x) < fi(y) forall i∈(1,...,n) and there exists an index j∈(1,...,n) such that fj(x) < fj(y). The non-dominated pointsof X are called the Pareto optima of f. H. Kuhn(1973) applied the concept of Pareto optimality to distancefunctions and characterized the convex hull conv (T) of any set T=(t1,...,tn) of Rm as the set of all Paretooptima of the vector function d2(x)=(d2(x,t1),...,d2(x,tn)), where d2(x,y)is the Euclidean distance between x,y∈ Rm. Motivatedby this result, given a set T=(t1,...,tn) of points of ametric space (X,d), we call the set Pd(T) of all Paretooptima of the function d(x)=(d(x,t1),...,d(x,tn)) the Pareto envelope of T. In this paper, we investigate the Pareto envelopes in Rm endowed with l1- or l∞-distances. We characterize PI(T) in all dimensions and PM(T) in R3. Usingthese results, we design efficient algorithms for constructing theseenvelopes in R3, in particular, an optimal O(n logn)-time algorithm for PM(T) and an O(n log2n)-time algorithmfor PI(T).

In this paper, we consider a class of cellular networks, called irregular cellular networks, which may have a non-uniform distribution of base stations and a non-uniform cell size. The communications (between base stations) graph of such a cellular network forms a so-called trigraph, i.e., a plane triangulation with inner vertices of degree at least six. We show that each trigraph with n vertices admits a labeling that assigns O(log/sup 2/ n) bit labels to vertices of the graph such that the distance between any two vertices u and v can be determined in constant time by merely inspecting the labels of u and v, without using any other information about the graph. Furthermore, we show that there is a labeling, assigning labels of size O(log/sup 2/ n) bits to vertices, which allows, given the label of a source vertex and the label of a destination, to compute in constant time the port number of the edge from the source that heads in the direction of the destination. These two results for trigraphs provide elegant solutions to a few problems in irregular cellular networks. The distance labeling scheme allows efficient implementation of the distance-based tracking protocol, by providing information, generally not available to the user, and means for accurate cell distance determination. Our routing and distance labeling schemes provide compact and efficient routing and connection re-routing protocols. Although these results are primarily developed for cellular networks, they may find applications also in other types of wireless networks that have a fixed backbone infrastructure.

Summary form only given. Triangular systems are the subgraphs of the regular triangular grid which are formed by a simple circuit of the grid and the region bounded by this circuit. They are used to model cellular networks where nodes are base stations. We propose an addressing scheme for triangular systems by employing their isometric embeddings into the Cartesian product of three trees. This embedding provides a simple representation of any triangular system with only three small integers per vertex, and allows to employ the compact labeling schemes for trees for distance queries and routing. We show that each such system with n vertices admits a labeling that assigns O(log/sup 2/n) bit labels to vertices of the system such that the distance between any two vertices u and v can be determined in constant time by merely inspecting the labels of u and v, without using any other information about the system. Furthermore, there is a labeling, assigning labels of size O(log n) bits to vertices, which allows, given the label of a source vertex and the label of a destination, to compute in constant time the port number of the edge from the source that heads in the direction of the destination. These results are used in solving some problems in cellular networks. Our addressing and distance labeling schemes allow efficient implementation of distance and movement based tracking protocols in cellular networks, by providing information, generally not available to the user, and means for accurate cell distance determination. Our routing and distance labeling schemes provide elegant and efficient routing and connection rerouting protocols for cellular networks.

Abstract Given a tree T = (V, E) endowed with a length function l and a cost function c, the diameter lowering problem consists in finding the reals 0 ≤ x(e) ≤ l(e), e ∈ E such that the tree obtained from T by decreasing the length of every edge e by x(e) units has a minimal diameter subject to the constraint ∑e∈Ec(e)x(e) ≤ B, where B is the available budget (analogously, one can minimize the cost of lowering subject to a diameter constraint). We present an O(|V|2) algorithm for solving this problem by developing and using algorithms of similar complexity for related eccentricity lowering problems. © 2002 Wiley Periodical, Inc.

The shortest-path metric d of a graph G=(V,E) is called $\delta$-{\it hyperbolic} if for any four vertices $u,v,w,x\in X$ the two larger of the three sums d(u,v)+d(w,x),d(u,w)+d(v,x),d(u,x)+d(v,w) differ by at most $\delta.$ In this paper, we characterize the graphs with 1-hyperbolic metrics in terms of a convexity condition and forbidden isometric subgraphs.

The median set of a graph G with weighted vertices comprises the vertices minimizing the average weighted distance to the vertices of G. We characterize the graphs in which, with respect to any nonnegative vertex weights, median sets always induce connected subgraphs. The characteristic conditions can be tested in polynomial time (by employing linear programming) and are immediately verified for a number of specific graph classes.

We show that the embedding of metric spaces into the l1-grid ℤ2 can be characterized in essentially the same fashion as in the case of the l1-plane ℝ2. In particular, a metric space can be embedded into ℤ2 iff every subspace with at most 6 points is embeddable. Moreover, if such an embedding exists, it can be constructed in polynomial time (for finite spaces). © 1998 John Wiley & Sons, Inc. Networks 32: 127–132, 1998

Recently in several papers, graphs with maximum neighborhood orderings were characterized and turned out to be algorithmically useful. This paper gives a unified framework for characterizations of those graphs in terms of neighborhood and clique hypergraphs which have the Helly property and whose line graph is chordal. These graphs are dual (in the sense of hypergraphs) to chordal graphs. By using the hypergraph approach in a systematical way new results are obtained, some of the old results are generalized, and some of the proofs are simplified.

A distance-preserving elimination ordering of a graph G is a linear ordering v 1 ,v 2,..., v n of the vertices such that each subgraph G i =G(v 1 ,...,v i ),i < n, is an isometric subgraph of G. We prove that the ordering of the vertices of a pseudo-modular or a house-free weakly modular graph G produced by the breadth-first search is distance preserving. We specify this result by showing that if, in addition, G does not contain the cycles C n , n\geq 5, and the bipyramids $bipyr(C_m), m\geq 6,$ as an isometric subgraph, then any ordering produced by the lexicographic breadth-first search is a domination elimination ordering (i.e., every vertex v i is dominated by some vertex v j , j < i, or, in other words, every vertex v k , k < i, adjacent to v i is also adjacent to v j ).

Let $\cal C$ be a family of cliques of a graph G=(V,E). Suppose that each clique C of $\cal C$ is associated with an integer r(C)$, where $r(C) \ge 0$. A vertex vr-dominates a clique C of G if $d(v,x) \le r(C)$ for all $x \in C$, where d(v,x) is the standard graph distance. A subset $D \subseteq V$ is a clique r-dominating set of G if for every clique $C \in \cal C$ there is a vertex $u \in D$ which r-dominates C. A clique r-packing set is a subset $P \subseteq \cal C$ such that there are no two distinct cliques $C',C'\in P$ r-dominated by a common vertex of G. The clique r-domination problem is to find a clique r-dominating set with minimum size and the clique r-packing problem is to find a clique r-packing set with maximum size. The formulated problems include many domination and clique-transversal-related problems as special cases. In this paper an efficient algorithm is proposed for solving these problems on dually chordal graphswhich are a natural generalization of strongly chordal graphs. The efficient algorithm is mainly based on the tree structure and special vertex elimination orderings of dually chordal graphs. In some important particular cases where the algorithm works in linear time the obtained results generalize and improve known results on strongly chordal graphs.