The Temporal Graph Exploration problem (TEXP) takes as input a temporal graph, i.e., a sequence of graphs \((G_i)_{i\in\mathbb N}\) on the same vertex set, and asks for a walk of shortest length visiting all vertices, where the \(i\)-th step uses an edge from \(G_i\) or stays put. If each such \(G_i\) is connected, then an exploration of length \(n^2\) exists, and this is known to be the best possible up to a constant. More fine-grained lower and upper bounds have been obtained for restricted temporal graph classes, however, for several fundamental classes, a large gap persists between known bounds, and it remains unclear which properties of a temporal graph make it inherently difficult to explore.

A graph class is monotone if it is closed under taking subgraphs. A monotone class defined by finitely many obstructions has bounded treewidth if and only if one of the obstructions is a tripod, i.e. a disjoint union of subdivided claws and paths. This dichotomy also characterizes exactly those monotone graph classes for which many NP-hard graph problems admit polynomial-time algorithms. These dichotomies do not extend to the universe of all hereditary classes. This leads to the question of whether we can extend known dichotomies for monotone classes to larger families of hereditary classes. We answer this question affirmatively by considering the family of hereditary graph classes closed under self-intersection. This family is known to be located strictly between the monotone and hereditary classes. We prove a new structural characterization of graphs in self-intersection-closed classes excluding a tripod. In contrast to monotone classes excluding a tripod, these classes do not necessarily have bounded treewidth; in fact, they do not even need to be sparse. We use our characterization to give a complete dichotomy for Maximum Independent Set, and its weighted variant, on self-intersection-closed classes defined by finitely many obstructions: these problems are in P if the class excludes a tripod and NP-hard otherwise. Our dichotomy generalizes several known results on Maximum Independent Set in the literature. We also apply our characterization to obtain a dichotomy for Maximum Induced Matching on self-intersection-closed classes of bipartite graphs defined by finitely many obstructions, and for Satisfiability and Counting Satisfiability on self-intersection-closed classes of (bipartite) incidence graphs defined by finitely many obstructions. Finally, we use our characterization to obtain a dichotomy for boundedness of clique-width for self-intersection-closed classes of bipartite graphs defined by finitely many obstructions.

Abstract Lettericity is a graph parameter responsible for many attractive structural properties. In particular, graphs of bounded lettericity have bounded linear clique-width and they are well-quasi-ordered by induced subgraphs. The latter property implies that any hereditary class of graphs of bounded lettericity can be described by finitely many forbidden induced subgraphs. This, in turn, implies, in a non-constructive way, polynomial-time recognition of such classes. However, no constructive algorithms and no specific bounds on the size of forbidden graphs are available up to date. In the present paper, we develop an algorithm that recognizes n -vertex graphs of lettericity at most k in time $$f(k) \cdot n^3$$ and show that any minimal graph of lettericity more than k has at most $$2^{O(k^2\log k)}$$ vertices.

Abstract. A temporal graph is a graph whose edges appear only at certain points in time. Recently, the second and the last three authors proposed a natural temporal analog of the Erdős–Rényi random graph model. The proposed model is obtained by randomly permuting the edges of an Erdős–Rényi random graph and interpreting this permutation as an ordering of presence times. It was shown that the connectivity threshold in the Erdős–Rényi model fans out into multiple phase transitions for several distinct notions of reachability in the temporal setting. In the present paper, we identify a sharp threshold for the emergence of a giant temporally connected component. We show that at [Formula: see text] the size of the largest temporally connected component increases from [Formula: see text] to [Formula: see text]. This threshold holds for both open and closed connected components, i.e., components that allow (respectively, forbid) their connecting paths to use external nodes.

A graph class admits an implicit representation if, for every positive integer $n$, its $n$-vertex graphs have a $O(\log n)$-bit (adjacency) labeling scheme, i.e., their vertices can be labeled by binary strings of length $O(\log n)$ such that the presence of an edge between any pair of vertices can be deduced solely from their labels. The famous Implicit Graph Conjecture posited that every hereditary (i.e., closed under taking induced subgraphs) factorial (i.e., containing $2^{O(n \log n)}$ $n$-vertex graphs) class admits an implicit representation. The conjecture was recently refuted [Hatami and Hatami, FOCS '22], and does not even hold among monotone (i.e., closed under taking subgraphs) factorial classes [Bonnet et al., ICALP '24]. However, monotone small (i.e., containing at most $n! c^n$ many $n$-vertex graphs for some constant $c$) classes do admit implicit representations. This motivates the Small Implicit Graph Conjecture: Every hereditary small class admits an $O(\log n)$-bit labeling scheme. We provide evidence supporting the Small Implicit Graph Conjecture. First, we show that every small weakly sparse (i.e., excluding some fixed bipartite complete graph as a subgraph) class has an implicit representation. This is a consequence of the following fact of independent interest proved in the paper: Every weakly sparse small class has bounded expansion (hence, in particular, bounded degeneracy). Second, we show that every hereditary small class admits an $O(\log^3 n)$-bit labeling scheme, which provides a substantial improvement of the best-known polynomial upper bound of $n^{1-\varepsilon}$ on the size of adjacency labeling schemes for such classes. This is a consequence of another fact of independent interest proved in the paper: Every small class has neighborhood complexity $O(n \log n)$.

In this paper we introduce a new operation for Linear Programming (LP), called LP complementation , which resembles many properties of LP duality. Given a maximisation (resp. minimisation) LP P , we define its complement Q as a specific minimisation (resp. maximisation) LP which has the same objective function as P . Our central result is the LP complementation theorem, that relates the optimal value of P and the optimal value of its complement by . The LP complementation operation can be applied if and only if P has an optimum value greater than 1. To illustrate this, we first apply LP complementation to hypergraphs . For any hypergraph H , we review the four classical LPs, namely covering K ( H ) , packing P ( H ) , matching M ( H ) , and transversal T ( H ) . For every hypergraph H = ( V , E ) , we call the complement of H . For each of the above four LPs, we relate the optimal values of the LP for the dual hypergraph to that of the complement hypergraph (e.g. ). We then apply LP complementation to fractional graph theory . We prove that the LP for the fractional in-dominating number of a digraph D is the complement of the LP for the fractional total out-dominating number of the digraph complement of D . Furthermore we apply the hypergraph complementation theorem to matroids. We establish that the fractional matching number of a matroid coincide with its edge toughness. As our last application of LP complementation, we introduce the natural problem Vertex Cover with Budget (VCB) : for a graph G = ( V , E ) and a positive integer b , what is the maximum number t b of vertex covers S 1 , … , S t b of G , such that every vertex v ∈ V appears in at most b vertex covers? The integer b can be viewed as a “budget” that we can spend on each vertex and, given this budget, we aim to cover all edges for as long as possible. We relate VCB with the LP Q G for the fractional chromatic number χ f of a graph G . More specifically, we prove that, as b → ∞ , the optimum for VCB satisfies t b ∼ t f ⋅ b , where t f is the optimal solution to the complement LP of Q G . Finally, our results imply that, for any finite budget b , it is NP-hard to decide whether t b ≥ b + c for any 1 ≤ c ≤ b − 1 .

A class of graphs admits an adjacency labeling scheme of size $b(n)$, if the vertices in each of its $n$-vertex graphs can be assigned binary strings (called labels) of length $b(n)$ so that the adjacency of two vertices can be determined solely from their labels. We give tight bounds on the size of adjacency labels for every family of monotone (i.e., subgraph-closed) classes with a well-behaved growth function between $2^{O(n \log n)}$ and $2^{O(n^{2-δ})}$ for any $δ> 0$. Specifically, we show that for any function $f: \mathbb N \to \mathbb R$ satisfying $\log n \leqslant f(n) \leqslant n^{1-δ}$ for any fixed $δ> 0$, and some~sub-multiplicativity condition, there are monotone graph classes with growth $2^{O(nf(n))}$ that do not admit adjacency labels of size at most $f(n) \log n$. On the other hand, any such class does admit adjacency labels of size $O(f(n)\log n)$. Surprisingly this tight bound is a $Θ(\log n)$ factor away from the information-theoretic bound of $Ω(f(n))$. The special case when $f = \log$ implies that the recently-refuted Implicit Graph Conjecture [Hatami and Hatami, FOCS 2022] also fails within monotone classes. We further show that the Implicit Graph Conjecture holds for all monotone \emph{small} classes. In other words, any monotone class with growth rate at most $n!\,c^n$ for some constant $c>0$, admits adjacency labels of information-theoretic order optimal size. In fact, we show a more general result that is of independent interest: any monotone small class of graphs has bounded degeneracy.We conjecture that the Implicit Graph Conjecture holds for all hereditary small classes.

We introduce a dense counterpart of graph degeneracy, which extends the recently-proposed invariant symmetric difference. We say that a graph has sd-degeneracy (for symmetric-difference degeneracy) at most d if it admits an elimination order of its vertices where a vertex u can be removed whenever it has a d-twin, i.e., another vertex v such that at most d vertices outside {u,v} are neighbors of exactly one of u, v. The family of graph classes of bounded sd-degeneracy is a superset of that of graph classes of bounded degeneracy or of bounded flip-width, and more generally, of bounded symmetric difference. Unlike most graph parameters, sd-degeneracy is not hereditary: it may be strictly smaller on a graph than on some of its induced subgraphs. In particular, every n-vertex graph is an induced subgraph of some O(n²)-vertex graph of sd-degeneracy 1. In spite of this and the breadth of classes of bounded sd-degeneracy, we devise Õ(√n)-bit adjacency labeling schemes for them, which are optimal up to the hidden polylogarithmic factor. This is attained on some even more general classes, consisting of graphs G whose vertices bijectively map to the leaves of a tree T, where transversal edges and anti-edges added to T define the edge set of G. We call such graph representations signed tree models as they extend the so-called tree models (or twin-decompositions) developed in the context of twin-width, by adding transversal anti-edges. While computing the degeneracy of a graph takes linear time, we show that determining its symmetric difference is para-co-NP-complete. This may seem surprising as symmetric difference can serve as a short-sighted first approximation of twin-width, whose computation is para-NP-complete. Indeed, we show that deciding if the symmetric difference of an input graph is at most 8 is co-NP-complete. We also show that deciding if the sd-degeneracy is at most 6 is NP-complete, contrasting with the symmetric difference.

We show that for any natural number s, there is a constant γ and a subgraph-closed class having, for any natural n, at most γn graphs on n vertices up to isomorphism, but no adjacency labeling scheme with labels of size at most s log n. In other words, for every s, there is a small -even tiny - monotone class without universal graphs of size ns. Prior to this result, it was not excluded that every small class has an almost linear universal graph, or equivalently a labeling scheme with labels of size (1 + o(1))log n. The existence of such a labeling scheme, a scaled-down version of the recently disproved Implicit Graph Conjecture, was repeatedly raised [Gavoille and Labourel, ESA ‘07; Dujmović et al., JACM ‘21; Bonamy et al., SIDMA ‘22; Bonnet et al., Comb. Theory ‘22]. Furthermore, our small monotone classes have unbounded twin-width, thus simultaneously disprove the already-refuted Small conjecture; but this time with a self-contained proof, not relying on elaborate group-theoretic constructions.

We prove a characterization of the structural conditions on matrices of sign-rank 3 and unit disk graphs (UDGs) which permit constant-cost public-coin randomized communication protocols. Therefore, under these conditions, these graphs also admit implicit representations.

Abstract In this paper we consider the following problem: Given a Hamiltonian graph G, and a Hamiltonian cycle C of G, can we compute a second Hamiltonian cycle $$C^{\prime } \ne C$$ C ′ ≠ C of G, and if yes, how quickly? If the input graph G satisfies certain conditions (e.g. if every vertex of G is odd, or if the minimum degree is large enough), it is known that such a second Hamiltonian cycle always exists. Despite substantial efforts, no subexponential-time algorithm is known for this problem. In this paper we relax the problem of computing a second Hamiltonian cycle in two ways. First, we consider approximating the length of a second longest cycle on n-vertex graphs with minimum degree $$\delta $$ δ and maximum degree $$\Delta $$ Δ . We provide a linear-time algorithm for computing a cycle $$C^{\prime } \ne C$$ C ′ ≠ C of length at least $$n-4\alpha (\sqrt{n}+2\alpha )+8$$ n - 4 α ( n + 2 α ) + 8 , where $$\alpha = \frac{\Delta -2}{\delta -2}$$ α = Δ - 2 δ - 2 . This results provides a constructive proof of a recent result by Girão, Kittipassorn, and Narayanan in the regime of $$\frac{\Delta }{\delta } = o(\sqrt{n})$$ Δ δ = o ( n ) . Our second relaxation of the problem is probabilistic. We propose a randomized algorithm which computes a second Hamiltonian cycle with high probability, given that the input graph G has a large enough minimum degree. More specifically, we prove that for every $$0 0 < p ≤ 0.02 , if the minimum degree of G is at least $$\frac{8}{p} \log \sqrt{8}n + 4$$ 8 p log 8 n + 4 , then a second Hamiltonian cycle can be computed with probability at least $$1 - \frac{1}{n}\left( \frac{50}{p^4} + 1 \right) $$ 1 - 1 n 50 p 4 + 1 in $$poly(n) \cdot 2^{4pn}$$ p o l y ( n ) · 2 4 p n time. This result implies that, when the minimum degree $$\delta $$ δ is sufficiently large, we can compute with high probability a second Hamiltonian cycle faster than any known deterministic algorithm. In particular, when $$\delta = \omega (\log n)$$ δ = ω ( log n ) , our probabilistic algorithm works in $$2^{o(n)}$$ 2 o

The domatic number of a graph is the maximum number of vertex disjoint dominating sets that partition the vertex set of the graph. In this paper we consider the fractional variant of this notion. Graphs with fractional domatic number 1 are exactly the graphs that contain an isolated vertex. Furthermore, it is known that all other graphs have fractional domatic number at least 2. In this note we characterize graphs with fractional domatic number 2. More specifically, we show that a graph without isolated vertices has fractional domatic number 2 if and only if it has a vertex of degree 1 or a connected component isomorphic to a 4-cycle. We conjecture that if the fractional domatic number is more than 2, then it is at least 7/3.

Abstract. We show that for any natural number [Formula: see text], there is a constant [Formula: see text] and a subgraph-closed class having, for any natural [Formula: see text], at most [Formula: see text] graphs on [Formula: see text] vertices up to isomorphism, but no adjacency labeling scheme with labels of size at most [Formula: see text]. In other words, for every [Formula: see text], there is a small—even tiny—monotone class without universal graphs of size [Formula: see text]. Prior to this result, it was not excluded that every small class has an almost linear universal graph, or equivalently a labeling scheme with labels of size [Formula: see text]. The existence of such a labeling scheme, a scaled-down version of the recently disproved Implicit Graph Conjecture, was repeatedly raised [Gavoille and Labourel, Proceedings of the 15 th Annual European Symposium on Algorithms, Lecture Notes in Comput. Sci. 4698, Springer, 2007, pp. 582–593; Dujmović et al., J. ACM, 68 (2021), pp. 1–33; Bonamy, Gavoille, and Pilipczuk, SIAM J. Discrete Math., 36 (2022), pp. 2082–2099; Bonnet et al., Comb. Theory, 2 (2022)]. Furthermore, our small monotone classes have unbounded twin-width and thus simultaneously disprove the already-refuted Small conjecture, but this time with a self-contained proof, not relying on elaborate group-theoretic constructions. As our main ingredient, we show that with high probability an Erdős–Rényi random graph [Formula: see text] with [Formula: see text] has, for every [Formula: see text], at most [Formula: see text] subgraphs on [Formula: see text] vertices, up to isomorphism. As a barrier to our general method of producing even more complex tiny classes, we show that when [Formula: see text], the latter no longer holds. More concretely, we provide an explicit lower bound on the number of unlabeled [Formula: see text]-vertex induced subgraphs of [Formula: see text] when [Formula: see text]. We thereby obtain a threshold for the property of having exponentially many unlabeled induced subgraphs: if [Formula: see text] with [Formula: see text], then with high probability even the number of all unlabeled (not necessarily induced) subgraphs is [Formula: see text], whereas if [Formula: see text] for sufficiently large [Formula: see text], then with high probability the number of unlabeled induced subgraphs is [Formula: see text]. This result supplements the study of counting unlabeled induced subgraphs that was initiated by Erdős and Rényi with a question on the number of unlabeled induced subgraphs of Ramsey graphs, eventually answered by Shelah.

Abstract. A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this paper, we consider a simple model of random temporal graph, obtained from an Erdős–Rényi random graph, [Formula: see text], by considering a random permutation [Formula: see text] of the edges and interpreting the ranks in [Formula: see text] as presence times. We give a thorough study of the temporal connectivity of such graphs and derive implications for the existence of several kinds of sparse spanners. It turns out that temporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that at [Formula: see text], any fixed pair of vertices can asymptotically almost surely (a.a.s.) reach each other; at [Formula: see text], at least one vertex (and, in fact, any fixed vertex) can a.a.s. reach all others; and at [Formula: see text], all the vertices can a.a.s. reach each other; i.e., the graph is temporally connected. Furthermore, the graph admits a temporal spanner of size [Formula: see text] as soon as it becomes temporally connected, which is nearly optimal, as [Formula: see text] is a lower bound. This result is quite significant because temporal graphs do not admit spanners of size [Formula: see text] in general [Kempe, Kleinberg, and Kumar, J. Comput. System Sci., 64 (2002), pp. 820–842]. In fact, they do not even always admit spanners of size [Formula: see text] [Axiotis and Fotakis, On the size and the approximability of minimum temporally connected subgraphs, 2016, pp. 149:1–149:14]. Thus, our result implies that the obstructions found in these works—and more generally any non-negligible obstruction—are statistically insignificant: nearly optimal spanners always exist in random temporal graphs. All the above thresholds are sharp. Carrying the study of temporal spanners a step further, we show that pivotal spanners—i.e., spanners of size [Formula: see text] composed of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently)—exist a.a.s. at [Formula: see text], this threshold being also sharp. Finally, we show that optimal spanners (of size [Formula: see text]) also exist a.a.s. at [Formula: see text]. Whether this value is a sharp threshold is open; we conjecture that it is. For completeness, we compare the above results to existing results in related areas, including edge-ordered graphs, gossip theory, and population protocols, showing that our results can be interpreted in these settings as well and that in some cases they improve known results therein. Finally, we discuss an intriguing connection between our results and Janson’s celebrated results on percolation in weighted graphs.

Abstract. Given two [Formula: see text]-vertex graphs [Formula: see text] and [Formula: see text] of bounded treewidth, is there an [Formula: see text]-vertex graph [Formula: see text] of bounded treewidth having subgraphs isomorphic to [Formula: see text] and [Formula: see text]? Our main result is a negative answer to this question, in a strong sense: we show that the answer is no even if [Formula: see text] is a binary tree and [Formula: see text] is a ternary tree. We also provide an extensive study of cases where such “gluing” is possible. In particular, we prove that if [Formula: see text] has treewidth [Formula: see text] and [Formula: see text] has pathwidth [Formula: see text], then there is an [Formula: see text]-vertex graph of treewidth at most [Formula: see text] containing both [Formula: see text] and [Formula: see text] as subgraphs.

Abstract. For any hereditary graph class [Formula: see text], we construct optimal adjacency labeling schemes for the classes of subgraphs and induced subgraphs of Cartesian products of graphs in [Formula: see text]. As a consequence, we show that if [Formula: see text] admits efficient adjacency labels (or, equivalently, small induced-universal graphs) meeting the information-theoretic minimum, then so do the classes of subgraphs and induced subgraphs of Cartesian products of graphs in [Formula: see text]. Our proof uses ideas from randomized communication complexity, hashing, and additive combinatorics and improves upon recent results of Chepoi, Labourel, and Ratel [ J. Graph Theory, 93 (2020), pp. 64–87].

For any hereditary graph class $F$, we construct optimal adjacency labeling schemes for the classes of subgraphs and induced subgraphs of Cartesian products of graphs in $F$. As a consequence, we show that, if $F$ admits efficient adjacency labels (or, equivalently, small induced-universal graphs) meeting the information-theoretic minimum, then the classes of subgraphs and induced subgraphs of Cartesian products of graphs in $F$ do too. Our proof uses ideas from randomized communication complexity, hashing, and additive combinatorics, and improves upon recent results of Chepoi, Labourel, and Ratel [Journal of Graph Theory, 2020].

Abstract We present a succinct data structure for permutation graphs, and their superclass of circular permutation graphs, i.e., data structures using optimal space up to lower order terms. Unlike concurrent work on circle graphs (Acan et al. in Theor Comput Sci, https://doi.org/10.1016/j.tcs.2022.06.022 , 2022), our data structure also supports distance and shortest-path queries, as well as adjacency and neighborhood queries, all in optimal time. We present in particular the first succinct exact distance oracle for (circular) permutation graphs. A second succinct data structure also supports degree queries in time independent of the neighborhood’s size at the expense of an $$O(\log n/\log \log n)$$ O ( log n / log log n ) -factor overhead in all running times. Furthermore, we develop a succinct data structure for the class of bipartite permutation graphs. We demonstrate how to run algorithms directly over our succinct representations for several problems on permutation graphs: Clique, Coloring, Independent Set, Hamiltonian Cycle, All-Pair Shortest Paths, and others. Finally, we initiate the study of semi-distributed graph representations; a concept that smoothly interpolates between distributed (labeling schemes) and centralized (standard data structures). We show how to turn some of our data structures into semi-distributed representations by storing only $$O(n)$$ O ( n ) bits of additional global information, circumventing the lower bound on distance labeling schemes for permutation graphs.

The most basic lower-bound question in randomized communication complexity is: Does a given problem have constant cost, or non-constant cost? We observe that this question has a deep connection to implicit graph representations in structural graph theory. Specifically, constant-cost communication problems correspond to hereditary graph families that admit constant-size adjacency sketches, or equivalently constant-size probabilistic universal graphs (PUGs), and these graph families are a subset of families that admit adjacency labeling schemes of size O(logn), which are the subject of the well-studied implicit graph question (IGQ).

A set S of Boolean points is a specifying set for a threshold function f if the only threshold function consistent with f on S is f itself. The minimal cardinality of a specifying set for f is the specification number of f and it is never smaller than n+1 for a function with n relevant variables. In the present paper, we develop an inductive approach to describing the set of Boolean threshold functions with minimum specification number by means of operations that allow us to extend functions of n variables in this set to functions of n+1 variables.

We uncover a connection between two seemingly unrelated notions: lettericity, from structural graph theory, and geometric griddability, from the world of permutation patterns. Both of these notions capture important structural properties of their respective classes of objects. We prove that these notions are equivalent in the sense that a permutation class is geometrically griddable if and only if the corresponding class of inversion graphs has bounded lettericity.

We give deterministic distributed (1+ϵ)-approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in O(1ϵlog⁡n) rounds, and our independent set algorithm has a runtime of O(1ϵlog⁡(1ϵ)log⁎⁡n) rounds. For coloring, existing lower bounds imply that the dependencies on 1ϵ and log⁡n are best possible. For independent set, we prove that Ω(1ϵ) rounds are necessary. Both our algorithms make use of a tree decomposition of the input chordal graph. They iteratively peel off interval subgraphs, which are identified via the tree decomposition of the input graph, thereby partitioning the vertex set into O(log⁡n) layers. For coloring, each interval graph is colored independently, which results in various coloring conflicts between the layers. These conflicts are then resolved in a separate phase, using the particular structure of our partitioning. For independent set, only the first O(log⁡1ϵ) layers are required as they already contain a large enough independent set. We develop a (1+ϵ)-approximation maximum independent set algorithm for interval graphs, which we then apply to those layers. While tree decompositions have only played a minor role in distributed computing, our work demonstrates their potential for designing efficient distributed algorithms.

A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this paper, we consider a simple model of random temporal graph, obtained from an Erdös-Rényi random graph G ~ Gn,p by considering a random permutation π of the edges and interpreting the ranks in π as presence times. We give a thorough study of the temporal connectivity of such graphs and derive implications for the existence of several kinds of sparse spanners. It turns out that temporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that, at p = log$n$/n, any fixed pair of vertices can a.a.s. reach each other; at 2 log$n$/n, at least one vertex (and in fact, any fixed vertex) can a.a.s. reach all others; and at 3 log$n$/n, all the vertices can a.a.s. reach each other, i.e., the graph is temporally connected. Furthermore, the graph admits a temporal spanner of size 2n + o(n) as soon as it becomes temporally connected, which is nearly optimal as 2n - 4 is a lower bound. This result is quite significant because temporal graphs do not admit spanners of size O(n) in general (Kempe, Kleinberg, Kumar, STOC 2000). In fact, they do not even always admit spanners of size o($n$2) (Axiotis, Fotakis, ICALP 2016). Thus, our result implies that the obstructions found in these works, and more generally, any non-negligible obstruction is statistically insignificant: nearly optimal spanners always exist in random temporal graphs. All the above thresholds are sharp. Carrying the study of temporal spanners a step further, we show that pivotal spanners-i.e., spanners of size 2n - 2 made of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently)-exist a.a.s. at 4 log$n$/ n, this threshold being also sharp. Finally, we show that optimal spanners (of size 2n - 4) also exist a.a.s. at p = 4 log$n$/n, Whether this value is a sharp threshold is open, we conjecture that it is. For completeness, we compare the above results to existing results in related areas, including edge-ordered graphs, gossip theory, and population protocols, showing that our results can be interpreted in these settings as well, and that in some cases, they improve known results therein. Finally, we discuss an intriguing connection between our results and Janson's celebrated results on percolation in weighted graphs.

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information spread over social networks and biological diseases spreading over contact networks. Often, the networks over which these processes spread are dynamic in nature, and can be modelled with temporal graphs. Here, we study the problem of deleting edges from a given temporal graph in order to reduce the number of vertices (temporally) reachable from a given starting point. This could be used to control the spread of a disease, rumour, etc. in a temporal graph. In particular, our aim is to find a temporal subgraph in which a process starting at any single vertex can be transferred to only a limited number of other vertices using a temporally-feasible path. We introduce a natural edge-deletion problem for temporal graphs and provide positive and negative results on its computational complexity and approximability.

In this paper we consider the following total functional problem: Given a cubic Hamiltonian graph $G$ and a Hamiltonian cycle $C_0$ of $G$, how can we compute a second Hamiltonian cycle $C_1 \neq C_0$ of $G$? Cedric Smith proved in 1946, using a non-constructive parity argument, that such a second Hamiltonian cycle always exists. Our main result is an algorithm which computes the second Hamiltonian cycle in time $O(n \cdot 2^{(0.3-\varepsilon)n})$ time, for some positive constant $\varepsilon>0$, and in polynomial space, thus improving the state of the art running time for solving this problem. Our algorithm is based on a fundamental structural property of Thomason's lollipop algorithm, which we prove here for the first time. In the direction of approximating the length of a second cycle in a Hamiltonian graph $G$ with a given Hamiltonian cycle $C_0$ (where we may not have guarantees on the existence of a second Hamiltonian cycle), we provide a linear-time algorithm computing a second cycle with length at least $n - 4α(\sqrt{n}+2α)+8$, where $α= \frac{Δ-2}{δ-2}$ and $δ,Δ$ are the minimum and the maximum degree of the graph, respectively. This approximation result also improves the state of the art.

Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G, a temporal graph is represented by assigning a set of integer time-labels to every edge e of G, indicating the discrete time steps at which e is active. We introduce and study the complexity of a natural temporal extension of the classical graph problem Maximum Matching, taking into account the dynamic nature of temporal graphs. In our problem, Maximum Temporal Matching, we are looking for the largest possible number of time-labeled edges (simply time-edges) (e,t) such that no vertex is matched more than once within any time window of Δ consecutive time slots, where Δ ∈ ℕ is given. The requirement that a vertex cannot be matched twice in any Δ-window models some necessary "recovery" period that needs to pass for an entity (vertex) after being paired up for some activity with another entity. We prove strong computational hardness results for Maximum Temporal Matching, even for elementary cases. To cope with this computational hardness, we mainly focus on fixed-parameter algorithms with respect to natural parameters, as well as on polynomial-time approximation algorithms.

Temporal graphs abstractly model real-life inherently dynamic networks. Given a graph G, a temporal graph with G as the underlying graph is a sequence of subgraphs (snapshots) Gt of G, where t≥1. In this paper we study stochastic temporal graphs, i.e. stochastic processes G whose random variables are the snapshots of a temporal graph on G. A natural feature observed in various real-life scenarios is a memory effect in the appearance probabilities of particular edges; i.e. the probability an edge e∈E appears at time step t depends on its appearance (or absence) at the previous k steps. We study the hierarchy of models of memory-k, k≥0, in an edge-centric network evolution setting: every edge of G has its own independent probability distribution for its appearance over time. We thoroughly investigate the complexity of two naturally related, but fundamentally different, temporal path problems, called Minimum Arrival and Best Policy.

Modern, inherently dynamic systems are usually characterized by a network structure which is subject to discrete changes over time. Given a static underlying graph, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs focused on temporal paths and other “path-related” temporal notions, only few attempts have been made to investigate “non-path” temporal problems. In this paper we introduce and study two natural temporal extensions of the classical problem VERTEX COVER. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. We provide strong hardness results, complemented by approximation and exact algorithms. Some of our algorithms are polynomial-time, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH) and other plausible complexity assumptions.

Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class is hereditary if it can be characterized by a (not necessarily finite) set ${\cal H}$ of forbidden induced subgraphs. We study the boundedness of clique-width of hereditary graph classes closed under complementation. First, we extend the known classification for the $|{\cal H}|=1$ case by classifying the boundedness of clique-width for every set ${\cal H}$ of self-complementary graphs. We then completely settle the $|{\cal H}|=2$ case. In particular, we determine one new class of $(H,\overline{H})$-free graphs of bounded clique-width (as a side effect, this leaves only five classes of $(H_1,H_2)$-free graphs, for which it is not known whether their clique-width is bounded). Once we have obtained the classification of the $|{\cal H}|=2$ case, we research the effect of forbidding self-complementary graphs on the boundedness of clique-width. Surprisingly, we show that for every set ${\cal F}$ of self-complementary graphs on at least five vertices, the classification of the boundedness of clique-width for $(\{H,\overline{H}\}\cup {\cal F})$-free graphs coincides with the one for the $|{\cal H}|=2$ case if and only if ${\cal F}$ does not include the bull.

Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which often stand in stark contrast to practice where data is inherently dynamic and subject to discrete changes over time. A temporal graph is a graph whose edges are assigned a set of integer time labels, indicating at which discrete time steps the edge is active. In this paper we present a natural temporal extension of the classical graph coloring problem. Given a temporal graph and a natural number ∆, we ask for a coloring sequence for each vertex such that (i) in every sliding time window of ∆ consecutive time steps, in which an edge is active, this edge is properly colored (i.e. its endpoints are assigned two different colors) at least once during that time window, and (ii) the total number of different colors is minimized. This sliding window temporal coloring problem abstractly captures many realistic graph coloring scenarios in which the underlying network changes over time, such as dynamically assigning communication channels to moving agents. We present a thorough investigation of the computational complexity of this temporal coloring problem. More specifically, we prove strong computational hardness results, complemented by efficient exact and approximation algorithms. Some of our algorithms are linear-time fixed-parameter tractable with respect to appropriate parameters, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH).

We give deterministic distributed (1+epsilon)-approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in O( (1 / epsilon) log n) rounds, and our independent set algorithm has a runtime of O( (1/epsilon) log(1/epsilon)log^* n) rounds. For coloring, existing lower bounds imply that the dependencies on 1/epsilon and log n are best possible. For independent set, we prove that Omega(1/epsilon) rounds are necessary. Both our algorithms make use of the tree decomposition of the input chordal graph. They iteratively peel off interval subgraphs, which are identified via the tree decomposition of the input graph, thereby partitioning the vertex set into O(log n) layers. For coloring, each interval graph is colored independently, which results in various coloring conflicts between the layers. These conflicts are then resolved in a separate phase, using the particular structure of our partitioning. For independent set, only the first O(log (1/epsilon)) layers are required as they already contain a large enough independent set. We develop a (1+epsilon)-approximation maximum independent set algorithm for interval graphs, which we then apply to those layers. This work raises the question as to how useful tree decompositions are for distributed computing.

Let vc(G), fvs(G) and oct(G) denote, respectively, the size of a minimum vertex cover, minimum feedback vertex set and minimum odd cycle transversal in a graph G. One can ask, when looking for these sets in a graph, how much bigger might they be if we require that they are independent; that is, what is the price of independence? If G has a vertex cover, feedback vertex set or odd cycle transversal that is an independent set, then we let, respectively, ivc(G), ifvs(G) or ioct(G) denote the minimum size of such a set. We investigate for which graphs H the values of ivc(G), ifvs(G) and ioct(G) are bounded in terms of vc(G), fvs(G) and oct(G), respectively, when the graph G belongs to the class of H-free graphs. We find complete classifications for vertex cover and feedback vertex set and an almost complete classification for odd cycle transversal (subject to three non-equivalent open cases).

We give deterministic distributed (1+ε)-approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in O( 1/ε logn) rounds, and our independent set algorithm has a runtime of O( 1 ε log( 1/ε ) log? n) rounds. For coloring, existing lower bounds imply that the dependencies on 1/ε and logn are best possible. For independent set, we prove that Ω( 1/ε ) rounds are necessary.

An extremal point of a positive threshold Boolean function $f$ is either a maximal zero or a minimal one. It is known that if $f$ depends on all its variables, then the set of its extremal points completely specifies $f$ within the universe of threshold functions. However, in some cases, $f$ can be specified by a smaller set. The minimum number of points in such a set is the specification number of $f$. Hu (1965) showed that the specification number of a threshold function of $n$ variables is at least $n+1$. Anthony et al. (1995) proved that this bound is attained for nested functions and conjectured that for all other threshold functions the specification number is strictly greater than $n+1$. In the present paper, we resolve this conjecture negatively by exhibiting threshold Boolean functions of $n$ variables, which are non-nested and for which the specification number is $n+1$. On the other hand, we show that the set of extremal points satisfies the statement of the conjecture, i.e.~a positive threshold Boolean function depending on all its $n$ variables has $n+1$ extremal points if and only if it is nested. To prove this, we reveal an underlying structure of the set of extremal points.

Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class is hereditary if it can be characterized by a (not necessarily finite) set H of forbidden induced subgraphs. We initiate a systematic study into the boundedness of clique-width of hereditary graph classes closed under complementation. First, we extend the known classification for the |H|=1 case by classifying the boundedness of clique-width for every set H of self-complementary graphs. We then completely settle the |H|=2 case. In particular, we determine one new class of (H1, complement of H1)-free graphs of bounded clique-width (as a side effect, this leaves only six classes of (H1, H2)-free graphs, for which it is not known whether their clique-width is bounded). Once we have obtained the classification of the |H|=2 case, we research the effect of forbidding self-complementary graphs on the boundedness of clique-width. Surprisingly, we show that for a set F of self-complementary graphs on at least five vertices, the classification of the boundedness of clique-width for ({H1, complement of H1} + F)-free graphs coincides with the one for the |H|=2 case if and only if F does not include the bull (the only non-empty self-complementary graphs on fewer than five vertices are P_1 and P_4, and P_4-free graphs have clique-width at most 2). Finally, we discuss the consequences of our results for COLOURING.