It has been proved by Boros and Makino that there is no output-polynomial-time algorithm enumerating the minimal redundant sets or the maximal irredundant sets of a hypergraph, unless P = NP. The same question was left open for graphs, with only a few tractable cases known to date. In this paper, we focus on graph classes that capture incidence relations such as bipartite, co-bipartite, and split graphs, motivated by their strong relation with hypergraphs. Concerning maximal irredundant sets, we show that the problem on co-bipartite graphs is as hard as in general graphs and tractable in split and strongly orderable graphs, the latter being a generalization of chordal bipartite graphs. As for minimal redundant sets enumeration, we first show that the problem is intractable in split and co-bipartite graphs, answering the aforementioned open question. Then, we show that it is tractable on (C₃,C₅,C₆,C₈)-free graphs, a class of graphs incomparable to strongly orderable graphs, and which also generalizes chordal bipartite graphs. Our positive results rely on the structural properties of these graph classes and thus cannot be easily extended to bipartite graphs, for which the question remains open for both problems.

In the content-oblivious (CO) model, proposed by Censor-Hillel et al. (PODC 2022 & Distributed Computing 2023), processes operate in an asynchronous network and communicate solely through pulses: zero-size messages that carry no information beyond their mere existence.

We study leader election in oriented ring networks under a content-oblivious asynchronous message-passing model in which an adversary may arbitrarily corrupt message contents. This highly stringent model captures extreme communication unreliability.

Leader Election is an important primitive for programmable matter, since it is often an intermediate step for the solution of more complex problems. Although the leader election problem itself is well studied even in the specific context of programmable matter systems, research on fault tolerant approaches is more limited. We consider the problem in the previously studied Amoebot model on a triangular grid, when the configuration is connected but contains nodes the particles cannot move to (e.g., obstacles). We assume that particles agree on a common direction (i.e., the horizontal axis) but do not have chirality (i.e., they do not agree on the other two directions of the triangular grid). We begin by showing that an election algorithm with explicit termination is not possible in this case, but we provide an implicitly terminating algorithm that elects a unique leader without requiring any movement. These results are in contrast to those in the more common model with chirality but no agreement on directions, where explicit termination is always possible but the number of elected leaders depends on the symmetry of the initial configuration. Solving the problem under the assumption of one common direction allows for a unique leader to be elected in a stationary and deterministic way under a semi-synchronous scheduler, which until now was only possible for simply connected configurations under a sequential scheduler.

Censor-Hillel, Cohen, Gelles, and Sela (PODC 2022 & Distributed Computing 2023) studied fully-defective asynchronous networks, where communication channels may arbitrarily corrupt messages. The model is equivalent to content-oblivious computation, where nodes communicate solely via pulses. They showed that if the network is 2-edge-connected, then any algorithm for a noiseless setting can be simulated in the fully-defective setting; otherwise, no non-trivial computation is possible in the fully-defective setting. However, their simulation requires a predesignated leader, which they conjectured to be necessary for any non-trivial content-oblivious task. Recently, Frei, Gelles, Ghazy, and Nolin (DISC 2024) refuted this conjecture for the special case of oriented ring topology. They designed two asynchronous content-oblivious leader election algorithms with message complexity O(n ⋅ ID_{max}), where n is the number of nodes and ID_{max} is the maximum ID. The first algorithm stabilizes in unoriented rings without termination detection. The second algorithm quiescently terminates in oriented rings, thus enabling the execution of the simulation algorithm after leader election. In this work, we present two results: General 2-edge-connected topologies: First, we show an asynchronous content-oblivious leader election algorithm that quiescently terminates in any 2-edge-connected network with message complexity O(m ⋅ N ⋅ ID_{min}), where m is the number of edges, N is a known upper bound on the number of nodes, and ID_{min} is the smallest ID. Combined with the above simulation, this result shows that whenever a size bound N is known, any noiseless algorithm can be simulated in the fully-defective model without a preselected leader, fully refuting the conjecture. Unoriented rings: We then show that the knowledge of N can be dropped in unoriented ring topologies by presenting a quiescently terminating election algorithm with message complexity O(n ⋅ ID_{max}) that matches the previous bound. Consequently, this result constitutes a strict improvement over the previous state of the art and shows that, on rings, fully-defective and noiseless communication are computationally equivalent, with no additional assumptions.

In this paper, we study the leader election problem in oriented ring networks under content-oblivious asynchronous message-passing systems, where an adversary may arbitrarily corrupt message contents. Frei et al. (DISC 2024) recently presented a uniform terminating leader election algorithm for oriented rings in this setting, with message complexity O(nIDmax) on a ring of size n, where IDmax is the largest identifier in the system. In this paper, we investigate the message complexity of leader election in this model, showing that no uniform algorithm can solve the problem if each process is limited to sending a constant number of messages in one direction. Interestingly, this limitation hinges on the uniformity assumption. In the non-uniform setting – where processes know an upper bound U ≥ n on the ring size – we present an algorithm with message complexity O(nUIDmin), in which each process sends O(UIDmin) messages clockwise and only three messages counter-clockwise. Here, IDmin is the smallest identifier in the system. This dependence on the identifiers compares favorably with the dependence on IDmax of Frei et al. (DISC 2024). We also show a non-uniform algorithm where each process sends O(U log IDmin) messages in one direction and O(log IDmin) in the other. The factor log IDmin is optimal, matching the lower bound of Frei et al. (DISC 2024). Finally, in the anonymous setting, we propose a randomized algorithm where each process sends only O(log2 U) messages, with a success probability of 1 − U−c

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.

The problem of electing a unique leader is central to all distributed systems, including programmable matter systems where particles have constant size memory. In this paper, we present a silent self-stabilising, deterministic, stationary, election algorithm for particles having constant memory, assuming that the system is simply connected. Our algorithm is elegant and simple, and requires constant memory per particle. We prove that our algorithm always stabilises to a configuration with a unique leader, under a daemon satisfying some fairness guarantees (Gouda fairness [Gouda 2001]). We use the special geometric properties of programmable matter in 2D triangular grids to obtain the first self-stabilising algorithm for such systems. This result is surprising since it is known that silent self-stabilising algorithms for election in general distributed networks require $Ω(\log{n})$ bits of memory per node, even for ring topologies [Dolev et al. 1999].

A set $S$ of isometric paths of a graph $G$ is ``$v$-rooted'', where $v$ is a vertex of $G$, if $v$ is one of the endpoints of all the isometric paths in $S$. The isometric path complexity of a graph $G$, denoted by $ipco{G}$, is the minimum integer $k$ such that there exists a vertex $v\in V(G)$ satisfying the following property: the vertices of any single isometric path $P$ of $G$ can be covered by $k$ many $v$-rooted isometric paths. First, we provide an $O(n^2 m)$-time algorithm to compute the isometric path complexity of a graph with $n$ vertices and $m$ edges. Then we show that the isometric path complexity remains bounded for graphs in three seemingly unrelated graph classes, namely, hyperbolic graphs, (theta, prism, pyramid)-free graphs, and outerstring graphs. There is a direct algorithmic consequence of having small isometric path complexity. Specifically, we show that if the isometric path complexity of a graph $G$ is bounded by a constant, then there exists a polynomial-time constant-factor approximation algorithm for ISOMETRIC PATH COVER, whose objective is to cover all vertices of a graph with a minimum number of isometric paths. This applies to all the above graph classes.

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.

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.

We consider the problem of collectively delivering some package from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent has limited energy which constrains the distance it can move. Hence multiple agents need to collaborate to move the package, each agent handing over the package to the next agent to carry it forward. Given the positions of the agents in the graph and their respective budgets, the problem of finding a feasible movement schedule for the agents can be challenging. We consider two variants of the problem: in non-returning delivery, the agents can stop anywhere; whereas in returning delivery, each agent needs to return to its starting location, a variant which has not been studied before. We first provide a polynomial-time algorithm for returning delivery on trees, which is in contrast to the known (weak) NP-hardness of the non-returning version. In addition, we give resource-augmented algorithms for returning delivery in general graphs. Finally, we give tight lower bounds on the required resource augmentation for both variants of the problem. In this sense, our results close the gap left by previous research.

International audience

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 consider the exploration of a simple polygon P by a robot that moves from vertex to vertex along edges of the visibility graph of P . The visibility graph has a vertex for every vertex of P and an edge between two vertices if they see each other—that is, if the line segment connecting them lies inside P entirely. While located at a vertex, the robot is capable of ordering the vertices it sees in counterclockwise order as they appear on the boundary, and for every two such vertices, it can distinguish whether the angle between them is convex (⩽ π) or reflex ( > π). Other than that, distant vertices are indistinguishable to the robot. We assume that an upper bound on the number of vertices is known. We obtain the general result that a robot exploring any locally oriented, arc-labeled graph G can always determine the base graph of G . Roughly speaking, this is the smallest graph that cannot be distinguished by a robot from G by its observations alone, no matter how it moves. Combining this result with various other techniques allows the ability to show that a robot exploring a polygon P with the preceding capabilities is always capable of reconstructing the visibility graph of P . We also show that multiple identical, indistinguishable, and deterministic robots of this kind can always solve the weak rendezvous problem in which they need to position themselves such that they mutually see each other—for instance, such that they form a clique in the visibility graph.

For a set S of graphs, a perfect S -packing ( S -factor) of a graph G is a set of mutually vertex-disjoint subgraphs of G that each are isomorphic to a member of S and that together contain all vertices of G . If G allows a covering (locally bijective homomorphism) to a graph H , i.e., a vertex mapping f : V G → V H satisfying the property that f ( u ) f ( v ) belongs to E H whenever the edge u v belongs to E G such that for every u ∈ V G the restriction of f to the neighborhood of u is bijective, then G is an H -cover. For some fixed H let S ( H ) consist of all connected H -covers. Let K k , ℓ be the complete bipartite graph with partition classes of size k and ℓ , respectively. For all fixed k , ℓ ≥ 1 , we determine the computational complexity of the problem that tests whether a given bipartite graph has a perfect S ( K k , ℓ ) -packing. Our technique is partially based on exploring a close relationship to pseudo-coverings. A pseudo-covering from a graph G to a graph H is a homomorphism from G to H that becomes a covering to H when restricted to a spanning subgraph of G . We settle the computational complexity of the problem that asks whether a graph allows a pseudo-covering to K k , ℓ for all fixed k , ℓ ≥ 1 .

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'

We address the enumeration and the leader election problems over partially anonymous and multi-hop broadcast networks. We consider an asynchronous communication model where each process broadcasts a message and all its neighbours receive this message after arbitrary and unpredictable time. In this paper, we present necessary conditions that must be satisfied by any graph to solve these problems and we show that these conditions are sufficient by providing an enumeration algorithm on the one hand and a leader election algorithm on the other hand. For both problems, we highlight the importance of the initial knowledge. Considering the enumeration problem, each process only knows the size of the graph and, contrary to related works, the number of its neighbouring processes is unknown. Whereas for the election problem, we show that this combination of knowledge is not sufficient. Our algorithm assumes that each process initially knows a map of the network (without knowing its position in this map). From the complexity viewpoint, our algorithms offer polynomial complexities (memory at each process, number and size of exchanged messages).

Abstract We discuss 11 known basic models of distributed computing: four message‐passing models that differ by the (non)existence of port‐numbers and a hierarchy of seven local computations models. In each of these models, we study the computational complexity of the decision problems if the leader election and if the naming problem can be solved on a given network. It is already known that these two decision problems are solvable in polynomial time for two models and are co‐NP‐complete for another one. Here, we settle the computational complexity for both problems in the remaining eight models by showing that they are co‐NP‐complete. We do this by translating each problem into a graph labeling problem. By using this technique, we also obtain an alternative proof for the already known co‐NP‐completeness result. In the second part of our article, we completely classify the computational complexity of all the corresponding graph labeling problems, i.e., for every fixed integer $k\geq 1$ we determine the complexity of the problem that asks whether a given graph allows a certain graph labeling that uses at most k labels. We also explain the close relationship of these labelings to graph homomorphisms that satisfy some further (global or local) constraints. This yields a new class of “constrained” graph homomorphisms that include the already known locally constrained graph homomorphisms. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

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.

Given a set S of segments in the plane, the intersection graph of S is the graph with vertex set S in which two vertices are adjacent if and only if the corresponding two segments intersect. We prove a conjecture of Scheinerman (PhD Thesis, Princeton University, 1984) that every planar graph is the intersection graph of some segments in the plane.