In this paper we study two natural models of random temporal graphs. In the first, the continuous model, each edge e is assigned l_e labels, each drawn uniformly at random from (0,1], where the numbers l_e are independent random variables following the same discrete probability distribution. In the second, the discrete model, the l_e labels of each edge e are chosen uniformly at random from a set {1,2,…,T}. In both models we study the existence of δ-temporal motifs. Here a δ-temporal motif consists of a pair (H,P), where H is a fixed static graph and P is a partial order over its edges. A temporal graph 𝒢 = (G,λ) contains (H,P) as a δ-temporal motif if 𝒢 has a simple temporal subgraph on the edges of H whose time labels are ordered according to P, and whose life duration is at most δ. We prove sharp existence thresholds for all δ-temporal motifs, and we identify a qualitatively different behavior from the analogous static thresholds in Erdős-Rényi random graphs. Applying the same techniques, we then characterize the growth of the largest δ-temporal clique in the continuous variant of our random temporal graphs model. Finally, we consider the doubling time of the reachability ball centered on a small set of vertices of the random temporal graph as a natural proxy for temporal expansion. We prove sharp upper and lower bounds for the maximum doubling time in the continuous model.

A periodic temporal graph, in its simplest form, is a graph in which every edge appears exactly once in the first Δ time steps, and then it reappears recurrently every Δ time step, where Δ is a given period length. From a network design perspective, a crucial task is to assign the time-labels on the edges in a way that optimizes some criterion. In this paper we introduce a very natural optimality criterion that captures how the temporal distances of all vertex pairs are “stretched”, compared to their distances in the underlying static graph. Given a static graph G, the task is to assign to each edge one time-label between 1 and Δ such that, in the resulting periodic temporal graph with period Δ, the duration of the fastest temporal path from any vertex u to any other vertex v is at most α times the distance between u and v in G. Here, the value of α measures how much the shortest paths are allowed to be stretched once we assign the periodic time-labels. Our results span three different directions: First, we provide a series of approximation and NP-hardness results. Second, we provide approximation and fixed-parameter algorithms. Among them, we provide a simple algorithm which guarantees an approximation strictly smaller than Δ. Third, we consider a parameterized local search extension of the problem where we are given the temporal labeling of the graph, but we are allowed to change the time-labels of at most k edges.

We present a comprehensive analysis of Round-Delayed Amnesiac Flooding (RDAF), a variant of Amnesiac Flooding that introduces round-based asynchrony through adversarial delays. We establish fundamental properties of RDAF, including termination characteristics for different graph types and decidability results under various adversarial models. Our key contributions include: (1) a formal model of RDAF incorporating round-based asynchrony, (2) a proof that flooding always terminates on acyclic graphs despite adversarial delays, (3) a construction showing non-termination is possible on any cyclic graph, (4) a demonstration that termination is undecidable with arbitrary computable adversaries, and (5) the introduction of Eventually Periodic Adversaries (EPA) under which termination becomes decidable. These results enhance our understanding of flooding in communication-delay settings and provide insights for designing robust distributed protocols.

Broadcast is a central problem in distributed computing. Recently, Hussak and Trehan [PODC'19/DC'23] proposed a stateless broadcasting protocol (Amnesiac Flooding), which was surprisingly proven to terminate in asymptotically optimal time (linear in the diameter of the network). However, it remains unclear: (i) Are there other stateless terminating broadcast algorithms with the desirable properties of Amnesiac Flooding, (ii) How robust is Amnesiac Flooding with respect to faults?

Broadcast is a central problem in distributed computing. Recently, Hussak and Trehan [PODC'19/DC'23] proposed a stateless broadcasting protocol (Amnesiac Flooding), which was surprisingly proven to terminate in asymptotically optimal time (linear in the diameter of the network). However, it remains unclear: (i) Are there other stateless terminating broadcast algorithms with the desirable properties of Amnesiac Flooding, (ii) How robust is Amnesiac Flooding with respect to faults? In this paper we make progress on both of these fronts. Under a reasonable restriction (obliviousness to message content) additional to the fault-free synchronous model, we prove that Amnesiac Flooding is the only strictly stateless deterministic protocol that can achieve terminating broadcast. We identify four natural properties of a terminating broadcast protocol that Amnesiac Flooding uniquely satisfies. In contrast, we prove that even minor relax-ations of any of these four criteria allow the construction of other terminating broadcast protocols. On the other hand, we prove that Amnesiac Flooding can become non-terminating or non-broadcasting, even if we allow just one node to drop a single message on a single edge in a single round. As a tool for proving this, we focus on the set of all configurations of transmissions between nodes in the network, and obtain a dichotomy characterizing the configurations, starting from which, Amnesiac Flooding terminates. Additionally, we charac-terise the structure of sets of Byzantine agents capable of forcing non-termination or non-broadcast of the protocol on arbitrary networks .

In a temporal network with discrete time-labels on its edges, information can only "flow" along sequences of edges with non-decreasing (resp.increasing) time-labels.In this paper we make a first attempt to understand how the direction of information flow on one edge can impact the direction of information flow on other edges.By naturally extending the classical notion of a transitive orientation in static graphs, we introduce the fundamental notion of a temporal transitive orientation, and we systematically investigate its algorithmic behavior.Our main result is a conceptually simple, yet technically quite involved, polynomial-time algorithm for recognizing whether a temporal graph G is transitively orientable.In wide contrast we prove that, surprisingly, it is NP-hard to recognize whether G is strictly transitively orientable.Additionally we introduce further related problems to temporal transitivity, notably among them the temporal transitive completion problem, for which we prove both algorithmic and hardness results.

We study a new algorithmic process of graph growth which starts from a single initial vertex and operates in discrete time-steps, called slots . In every slot, the graph grows via two operations (i) vertex generation and (ii) edge activation. The process completes at the last slot where a (possibly empty) subset of the edges of the graph are removed. Removed edges are called excess edges . The main problem investigated in this paper is: Given a target graph G , design an algorithm that outputs a process that grows G , called a growth schedule . Additionally, we aim to minimize the total number of slots k and of excess edges ℓ used by the process. We provide both positive and negative results, with our main focus being either schedules with sub-linear number of slots or with no excess edges.

The network-based study of financial systems has received considerable attention in recent years but has seldom explicitly incorporated the dynamic aspects of such systems. We consider this problem setting from the temporal point of view and introduce the Interval Debt Model (IDM) and some scheduling problems based on it, namely: Bankruptcy Minimization/Maximization, in which the aim is to produce a payment schedule with at most/at least a given number of bankruptcies; Perfect Scheduling, the special case of the minimization variant where the aim is to produce a schedule with no bankruptcies (that is, a perfect schedule); and Bailout Minimization, in which a financial authority must allocate a smallest possible bailout package to enable a perfect schedule. We show that each of these problems is NP-complete, in many cases even on very restricted input instances. On the positive side, we provide for Perfect Scheduling a polynomial-time algorithm on (rooted) out-trees although in contrast we prove NP-completeness on directed acyclic graphs, as well as on instances with a constant number of nodes (and hence also constant treewidth). When we allow non-integer payments, we show by a linear programming argument that the problem Bailout Minimization can be solved in polynomial time.

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 .

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.

A graph is temporally connected if a strict temporal path exists from every vertex u to every other vertex v. This paper studies temporal design problems for undirected temporally connected graphs. Given a connected undirected graph G, the goal is to determine the smallest total number of time-labels |λ| needed to ensure temporal connectivity, where |λ| denotes the sum, over all edges, of the size of the set of labels associated to an edge. The basic problem, called Minimum Labeling (ML) can be solved optimally in polynomial time. We introduce the Min. Aged Labeling (MAL) problem, which involves connecting the graph with an upper-bound on the maximum label, the Min. Steiner Labeling (MSL) problem, focusing on connecting specific important vertices, and the age-restricted version of MSL, Min. Aged Steiner Labeling (MASL). We show that MAL is NP-complete, MASL is W[1]- hard, and while MSL remains NP-hard, it is FPT with respect to the number of terminals.

Temporal graphs naturally model graphs whose underlying topology changes over time. Recently, the problems Temporal Vertex Cover (or TVC) and Sliding-Window Temporal Vertex Cover (or Delta-TVC for time-windows of a fixed-length Delta) have been established as natural extensions of the classic Vertex Cover problem on static graphs with connections to areas such as surveillance in sensor networks. In this paper we initiate a systematic study of the complexity of TVC and Delta-TVC on sparse graphs. Our main result shows that for every Delta geq 2, Delta-TVC is NP-hard even when the underlying topology is described by a path or a cycle. This resolves an open problem from literature and shows a surprising contrast between Delta-TVC and TVC for which we provide a polynomial-time algorithm in the same setting. To circumvent this hardness, we present a number of exact and approximation algorithms for temporal graphs whose underlying topologies are given by a path, that have bounded vertex degree in every time step, or that admit a small-sized temporal vertex cover.

A graph is temporally connected if there exists a strict temporal path, i.e. a path whose edges have strictly increasing labels, from every vertex $u$ to every other vertex $v$. In this paper we study temporal design problems for undirected temporally connected graphs. The basic setting of these optimization problems is as follows: given a connected undirected graph $G$, what is the smallest number $|λ|$ of time-labels that we need to add to the edges of $G$ such that the resulting temporal graph $(G,λ)$ is temporally connected? As it turns out, this basic problem, called MINIMUM LABELING (ML), can be optimally solved in polynomial time. However, exploiting the temporal dimension, the problem becomes more interesting and meaningful in its following variations, which we investigate in this paper. First we consider the problem MIN. AGED LABELING (MAL) of temporally connecting the graph when we are given an upper-bound on the allowed age (i.e. maximum label) of the obtained temporal graph $(G,λ)$. Second we consider the problem MIN. STEINER LABELING (MSL), where the aim is now to have a temporal path between any pair of "terminals" vertices which lie in a subset $R\subseteq V$. This relaxed problem resembles STEINER TREE in static graphs. However, due to the requirement of strictly increasing labels in a temporal path, STEINER TREE is not a special case of MSL. Finally we consider the age-restricted version of MSL, namely MIN. AGED STEINER LABELING (MASL). Our main results are threefold: we prove that (i) MAL becomes NP-complete on undirected graphs, while (ii) MASL becomes W[1]-hard with respect to the number $|R|$ of terminals. On the other hand we prove that (iii) although the age-unrestricted problem MSL is NP-hard, it is in FPT with respect to the number $|R|$ of terminals. That is, adding the age restriction, makes the above problems strictly harder.

We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalization lies in simultaneously considering several instances of the problem at once. In particular, we have n clients over a period of m days, where each client has a single job with its own processing time and deadline per day. Our goal is to provide a schedule for each of the m days, so that each client is guaranteed to have their job meet its deadline in at least k

We investigate the computational complexity of finding temporally disjoint paths or walks in temporal graphs. There, the edge set changes over discrete time steps and a temporal path (resp. walk) uses edges that appear at monotonically increasing time steps. Two paths (or walks) are temporally disjoint if they never use the same vertex at the same time; otherwise, they interfere. This reflects applications in robotics, traffic routing, or finding safe pathways in dynamically changing networks. On the one extreme, we show that on general graphs the problem is computationally hard. The "walk version" is W[1]-hard when parameterized by the number of routes. However, it is polynomial-time solvable for any constant number of walks. The "path version" remains NP-hard even if we want to find only two temporally disjoint paths. On the other extreme, restricting the input temporal graph to have a path as underlying graph, quite counterintuitively, we find NP-hardness in general but also identify natural tractable cases.

In a temporal network with discrete time-labels on its edges, entities and information can only "flow" along sequences of edges whose time-labels are non-decreasing (resp. increasing), i.e. along temporal (resp. strict temporal) paths. Nevertheless, in the model for temporal networks of [Kempe, Kleinberg, Kumar, JCSS, 2002], the individual time-labeled edges remain undirected: an edge e = {u,v} with time-label t specifies that "u communicates with v at time t". This is a symmetric relation between u and v, and it can be interpreted that the information can flow in either direction. In this paper we make a first attempt to understand how the direction of information flow on one edge can impact the direction of information flow on other edges. More specifically, naturally extending the classical notion of a transitive orientation in static graphs, we introduce the fundamental notion of a temporal transitive orientation and we systematically investigate its algorithmic behavior in various situations. An orientation of a temporal graph is called temporally transitive if, whenever u has a directed edge towards v with time-label t₁ and v has a directed edge towards w with time-label t₂ ≥ t₁, then u also has a directed edge towards w with some time-label t₃ ≥ t₂. If we just demand that this implication holds whenever t₂ > t₁, the orientation is called strictly temporally transitive, as it is based on the fact that there is a strict directed temporal path from u to w. Our main result is a conceptually simple, yet technically quite involved, polynomial-time algorithm for recognizing whether a given temporal graph 𝒢 is transitively orientable. In wide contrast we prove that, surprisingly, it is NP-hard to recognize whether 𝒢 is strictly transitively orientable. Additionally we introduce and investigate further related problems to temporal transitivity, notably among them the temporal transitive completion problem, for which we prove both algorithmic and hardness results.

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.

Abstract Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For m-edge and n-vertex graphs, it is well-known to be solvable in $$O(m\sqrt{n})$$ O ( m n ) time; however, for several applications this running time is still too slow. We investigate how linear-time (and almost linear-time) data reduction (used as preprocessing) can alleviate the situation. More specifically, we focus on linear-time kernelization. We start a deeper and systematic study both for general graphs and for bipartite graphs. Our data reduction algorithms easily comply (in form of preprocessing) with every solution strategy (exact, approximate, heuristic), thus making them attractive in various settings.

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.

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).

In the classical binary search in a path the aim is to detect an unknown target by asking as few queries as possible, where each query reveals the direction to the target. This binary search algorithm has been recently extended by Emamjomeh-Zadeh et al. (in: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC 2016, Cambridge, pp. 519–532, 2016) to the problem of detecting a target in an arbitrary graph. Similarly to the classical case in the path, the algorithm of Emamjomeh-Zadeh et al. maintains a candidates’ set for the target, while each query asks an appropriately chosen vertex—the “median”—which minimises a potential $$\varPhi $$ among the vertices of the candidates’ set. In this paper we address three open questions posed by Emamjomeh-Zadeh et al., namely (a) detecting a target when the query response is a direction to an approximately shortest path to the target, (b) detecting a target when querying a vertex that is an approximate median of the current candidates’ set (instead of an exact one), and (c) detecting multiple targets, for which to the best of our knowledge no progress has been made so far. We resolve questions (a) and (b) by providing appropriate upper and lower bounds, as well as a new potential $$\varGamma $$ that guarantees efficient target detection even by querying an approximate median each time. With respect to (c), we initiate a systematic study for detecting two targets in graphs and we identify sufficient conditions on the queries that allow for strong (linear) lower bounds and strong (polylogarithmic) upper bounds for the number of queries. All of our positive results can be derived using our new potential $$\varGamma $$ that allows querying approximate medians.

In this work we consider temporal networks, i.e. networks defined by a labeling $$\lambda $$ assigning to each edge of an underlying graphG a set of discrete time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at which the edge is available. We focus on path problems of temporal networks. In particular, we consider time-respecting paths, i.e. paths whose edges are assigned by $$\lambda $$ a strictly increasing sequence of labels. We begin by giving two efficient algorithms for computing shortest time-respecting paths on a temporal network. We then prove that there is a natural analogue of Menger’s theorem holding for arbitrary temporal networks. Finally, we propose two cost minimization parameters for temporal network design. One is the temporality of G, in which the goal is to minimize the maximum number of labels of an edge, and the other is the temporal cost of G, in which the goal is to minimize the total number of labels used. Optimization of these parameters is performed subject to some connectivity constraint. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graph families such as rings, directed acyclic graphs, and trees.

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph problems. For general $m$-edge and $n$-vertex graphs, it is well known to be solvable in $O(m\sqrt{n})$ time. We present a linear-time algorithm to find maximum-cardinality matchings on cocomparability graphs, a prominent subclass of perfect graphs that strictly contains interval graphs as well as permutation graphs. Our greedy algorithm is based on the recently discovered Lexicographic Depth First Search (LDFS).

Motivated by the fact that in several cases a matching in a graph is stable if and only if it is produced by a greedy algorithm, we study the problem of computing a maximum weight greedy matching on weighted graphs, termed GREEDYMATCHING. In wide contrast to the maximum weight matching problem, for which many efficient algorithms are known, we prove that GREEDYMATCHING is strongly NP-hard and APX-complete, and thus it does not admit a PTAS unless P=NP, even on graphs with maximum degree at most 3 and with at most three different integer edge weights. Furthermore we prove that GREEDYMATCHING is strongly NP-hard if the input graph is in addition bipartite. Moreover we consider three natural parameters of the problem, for which we establish a sharp threshold behavior between NP-hardness and computational tractability. On the positive side, we present a randomized approximation algorithm (RGMA) for GREEDYMATCHING on a special class of weighted graphs, called bushgraphs. We highlight an unexpected connection between RGMA and the approximation of maximum cardinality matching in unweighted graphs via randomized greedy algorithms. We show that, if the approximation ratio of RGMA is ρ, then for every ε > 0 the randomized MRG algorithm of (Aronson et al. 1995) gives a (ρ − ε)-approximation for the maximum cardinality matching. We conjecture that a tightbound for ρ is 2/3; we prove our conjecture true for four subclasses of bush graphs. Proving a tight bound for the approximation ratio of MRG on unweighted graphs (and thus also proving a tight value for ρ) is a long-standing open problem (Poloczek and Szegedy 2012). This unexpected relation of our RGMA algorithm with the MRG algorithm may provide new insights for solving this problem.

In the classical binary search in a path the aim is to detect an unknown target by asking as few queries as possible, where each query reveals the direction to the target. This binary search algorithm has been recently extended by [Emamjomeh-Zadeh et al., STOC, 2016] to the problem of detecting a target in an arbitrary graph. Similarly to the classical case in the path, the algorithm of Emamjomeh-Zadeh et al. maintains a candidates’ set for the target, while each query asks an appropriately chosen vertex– the "median"–which minimises a potential \Phi among the vertices of the candidates' set. In this paper we address three open questions posed by Emamjomeh-Zadeh et al., namely (a) detecting a target when the query response is a direction to an approximately shortest path to the target, (b) detecting a target when querying a vertex that is an approximate median of the current candidates' set (instead of an exact one), and (c) detecting multiple targets, for which to the best of our knowledge no progress has been made so far. We resolve questions (a) and (b) by providing appropriate upper and lower bounds, as well as a new potential Γ that guarantees efficient target detection even by querying an approximate median each time. With respect to (c), we initiate a systematic study for detecting two targets in graphs and we identify sufficient conditions on the queries that allow for strong (linear) lower bounds and strong (polylogarithmic) upper bounds for the number of queries. All of our positive results can be derived using our new potential \Gamma that allows querying approximate medians.

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For m-edge and n-vertex graphs, it is well-known to be solvable in O(m\sqrt{n}) time; however, for several applications this running time is still too slow. We investigate how linear-time (and almost linear-time) data reduction (used as preprocessing) can alleviate the situation. More specifically, we focus on linear-time kernelization. We start a deeper and systematic study both for general graphs and for bipartite graphs. Our data reduction algorithms easily comply (in form of preprocessing) with every solution strategy (exact, approximate, heuristic), thus making them attractive in various settings.

We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex u to vertex v is a path from u to v where successive path edges have strictly increasing labels. A graph is temporally connected iff there is a (u, v)-journey for any pair of vertices u, v, u ≠ v. We first give a simple polynomial-time algorithm to check whether a given temporal graph is temporally connected. We then consider the case in which a designer of temporal graphs can freely choose availability instances for all edges and aims for temporal connectivity with very small cost; the cost is the total number of availability instances used. We achieve this via a simple polynomial-time procedure which derives designs of cost linear in n. We also show that the above procedure is (almost) optimal when the underlying graph is a tree, by proving a lower bound on the cost for any tree. However, there are pragmatic cases where one is not free to design a temporally connected graph anew, but is instead given a temporal graph design with the claim that it is temporally connected, and wishes to make it more cost-efficient by removing labels without destroying temporal connectivity (redundant labels). Our main technical result is that computing the maximum number of redundant labels is APX-hard, i.e., there is no PTAS unless P = N P. On the positive side, we show that in dense graphs with random edge availabilities, there is asymptotically almost surely a very large number of redundant labels. A temporal design may, however, be minimal, i.e., no redundant labels exist. We show the existence of minimal temporal designs with at least nlogn labels.

We study the design of fixed-parameter algorithms for problems already known to be solvable in polynomial time. The main motivation is to get more efficient algorithms for problems with unattractive polynomial running times. Here, we focus on a fundamental graph problem: Longest Path , that is, given an undirected graph, find a maximum-length path in G . Longest Path is NP-hard in general but known to be solvable in O ( n 4 ) time on n -vertex interval graphs. We show how to solve Longest Path on Interval Graphs , parameterized by vertex deletion number k to proper interval graphs, in O ( k 9 n ) time. Notably, Longest Path is trivially solvable in linear time on proper interval graphs, and the parameter value k can be approximated up to a factor of 4 in linear time. From a more general perspective, we believe that using parameterized complexity analysis may enable a refined understanding of efficiency aspects for polynomial-time solvable problems similarly to what classical parameterized complexity analysis does for NP-hard problems.

Finding a vertex subset in a graph that satisfies a certain property is one of the most-studied topics in algorithmic graph theory. The focus herein is often on minimizing or maximizing the size of the solution, that is, the size of the desired vertex set. In several applications, however, we also want to limit the "exposure" of the solution to the rest of the graph. This is the case, for example, when the solution represents persons that ought to deal with sensitive information or a segregated community. In this work, we thus explore the (parameterized) complexity of finding such secluded vertex subsets for a wide variety of properties that they shall fulfill. More precisely, we study the constraint that the (open or closed) neighborhood of the solution shall be bounded by a parameter and the influence of this constraint on the complexity of minimizing separators, feedback vertex sets, F-free vertex deletion sets, dominating sets, and the maximization of independent sets.

In this paper we initiate the study of populations of agents with very limited capabilities that are globally able to compute order statistics of their arithmetic input values via pair-wise meetings. To this extent, we introduce the Arithmetic Population Protocol (APP) model, embarking from the well known Population Protocol (PP) model and inspired by two recent papers in which states are treated as integer numbers. In the APP model, every agent has a state from a set Q of states, as well as a fixed number of registers (independent of the size of the population), each of which can store an element from a totally ordered set S of samples. Whenever two agents interact with each other, they update their states and the values stored in their registers according to a joint transition function. This transition function is also restricted; it only allows (a) comparisons and (b) copy / paste operations for the sample values that are stored in the registers of the two interacting agents. Agents can only meet in pairs via a fair scheduler and are required to eventually converge to the same output value of the function that the protocol globally and stably computes. We present two different APPs for stably computing the median of the input values, initially stored on the agents of the population. Our first APP, in which every agent has 3 registers and no states, stably computes (with probability 1) the median under any fair scheduler in any strongly connected directed (or connected undirected) interaction graph. Under the probabilistic scheduler, we show that our protocol stably computes the median in O(n^6) number of interactions in a connected undirected interaction graph of n agents. Our second APP, in which every agent has 2 registers and O(n^2 log{n}) states, computes to the correct median of the input with high probability in O(n^3 log{n}) interactions, assuming the probabilistic scheduler and the complete interaction graph. Finally we present a third APP which, for any k, stably computes the k-th smallest element of the input of the population under any fair scheduler and in any strongly connected directed (or connected undirected) interaction graph. In this APP every agent has 2 registers and n states. Upon convergence every agent has a different state; all these states provide a total ordering of the agents with respect to their input values.

The $$3$$ -coloring problem is well known to be NP-complete. It is also well known that it remains NP-complete when the input is restricted to graphs with diameter $$4$$ . Moreover, assuming the Exponential Time Hypothesis (ETH), $$3$$ -coloring cannot be solved in time $$2^{o(n)}$$ on graphs with $$n$$ vertices and diameter at most $$4$$ . In spite of extensive studies of the $$3$$ -coloring problem with respect to several basic parameters, the complexity status of this problem on graphs with small diameter, i.e. with diameter at most $$2$$ , or at most $$3$$ , has been an open problem. In this paper we investigate graphs with small diameter. For graphs with diameter at most $$2$$ , we provide the first subexponential algorithm for $$3$$ -coloring, with complexity $$2^{O(\sqrt{n\log n})}$$ . Furthermore we extend the notion of an articulation vertex to that of an articulation neighborhood, and we provide a polynomial algorithm for $$3$$ -coloring on graphs with diameter $$2$$ that have at least one articulation neighborhood. For graphs with diameter at most $$3$$ , we establish the complexity of $$3$$ -coloring by proving for every $${\varepsilon \in [0,1)}$$ that $$3$$ -coloring is NP-complete on triangle-free graphs of diameter $$3$$ and radius $$2$$ with $$n$$ vertices and minimum degree $$\delta =\varTheta (n^{\varepsilon })$$ . Moreover, assuming ETH, we use three different amplification techniques of our hardness results, in order to obtain for every $${\varepsilon \in [0,1)}$$ subexponential asymptotic lower bounds for the complexity of $$3$$ -coloring on triangle-free graphs with diameter $$3$$ and minimum degree $${\delta =\varTheta (n^{\varepsilon })}$$ . Finally, we provide a $$3$$ -coloring algorithm with running time $${ 2^{O\left( \min \{\delta \varDelta ,\ \frac{n}{\delta }\log \delta \}\right) }}$$ for arbitrary graphs with diameter $$3$$ , where $$n$$ is the number of vertices and $$ \delta $$ (resp. $$\varDelta $$ ) is the minimum (resp. maximum) degree of the input graph. To the best of our knowledge, this is the first subexponential algorithm for graphs with $${\delta =\omega (1)}$$ and for graphs with $${\delta =O(1)}$$ and $$\varDelta =o(n)$$ . Due to the above lower bounds of the complexity of $$3$$ -coloring, the running time of this algorithm is asymptotically almost tight when the minimum degree of the input graph is $$\delta =\varTheta (n^{\varepsilon })$$ , where $${\varepsilon \in [\frac{1}{2},1)}$$ , as its time complexity is $${2^{O\left( \frac{n}{\delta } \log \delta \right) } = 2^{O\left( n^{1-\varepsilon } \log n\right) }}$$ and the corresponding lower bound states that there is no $$2^{o\left( n^{1-\varepsilon }\right) }$$ -time algorithm.

Tolerance graphs have been extensively studied since their introduction, due to their interesting structure and their numerous applications, as they generalize both interval and permutation graphs in a natural way. It has been conjectured by Golumbic, Monma, and Trotter in 1984 that the intersection of tolerance and cocomparability graphs coincides with bounded tolerance graphs. Since cocomparability graphs can be efficiently recognized, a positive answer to this conjecture in the general case would enable us to efficiently distinguish between tolerance and bounded tolerance graphs, although it is NP-complete to recognize each of these classes of graphs separately. This longstanding conjecture has been proved under some– rather strong – structural assumptions on the input graph; in particular, it has been proved for complements of trees, and later extended to complements of bipartite graphs, and these are the only known results so far. Furthermore, it is known that the intersection of tolerance and cocomparability graphs is contained in the class of trapezoid graphs. Our main result in this article is that the above conjecture is true for every graph G that admits a tolerance representation with exactly one unbounded vertex; note that this assumption concerns only the given tolerance representation R of G , rather than any structural property of G . Moreover, our results imply as a corollary that the conjecture of Golumbic, Monma, and Trotter is true for every graph G = ( V , E ) that has no three independent vertices a , b , c ∈ V such that N ( a ) ⊂ N ( b ) ⊂ N ( c ) , where N ( v ) denotes the set of neighbors of a vertex v ∈ V ; this is satisfied in particular when G is the complement of a triangle-free graph (which also implies the above-mentioned correctness for complements of bipartite graphs). Our proofs are constructive, in the sense that, given a tolerance representation R of a graph G , we transform R into a bounded tolerance representation R ∗ of G . Furthermore, we conjecture that any minimal tolerance graph G that is not a bounded tolerance graph, has a tolerance representation with exactly one unbounded vertex. Our results imply the non-trivial result that, in order to prove the conjecture of Golumbic, Monma, and Trotter, it suffices to prove our conjecture.

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain amount of overlap without being in conflict. In one of the most natural generalizations of tolerance graphs with direct applications in the comparison of DNA sequences from different organisms, namely multitolerance graphs, two tolerances are allowed for each interval: one on the left side and the other on the right side. Several efficient algorithms for optimization problems that are NP-hard in general graphs have been designed for tolerance and multitolerance graphs. In spite of this progress, the complexity status of some fundamental algorithmic problems on tolerance and multitolerance graphs, such as the dominating set problem, remained unresolved until now---three decades after the introduction of tolerance graphs. In this paper we introduce two new geometric representations for tolerance and multitolerance graphs, given by points and line segments in the plane. Apart from being important on their own, these new representations prove to be a powerful tool for deriving both hardness results and polynomial time algorithms. Using them, we surprisingly prove that the dominating set problem can be solved in polynomial time on tolerance graphs and that it is APX-hard on multitolerance graphs, thus solving a longstanding open problem. This problem is the first one that has been discovered with a different complexity status in these two graph classes.

In this work we consider temporal networks, the links of which are available only at random times (randomly available temporal networks). Our networks are {\em ephemeral}: their links appear sporadically, only at certain times, within a given maximum time (lifetime of the net). More specifically, our temporal networks notion concerns networks, whose edges (arcs) are assigned one or more random discrete-time labels drawn from a set of natural numbers. The labels of an edge indicate the discrete moments in time at which the edge is available. In such networks, information (e.g., messages) have to follow temporal paths, i.e., paths, the edges of which are assigned a strictly increasing sequence of labels. We first examine a very hostile network: a clique, each edge of which is known to be available only one random time in the time period {1,2, ..., n} (n is the number of vertices). How fast can a vertex send a message to all other vertices in such a network? To answer this, we define the notion of the Temporal Diameter for the random temporal clique and prove that it is Θ(log n) with high probability and in expectation. In fact, we show that information dissemination is very fast with high probability even in this hostile network with regard to availability. This result is similar to the results for the random phone-call model. Our model, though, is weaker. Our availability assumptions are different and randomness is provided only by the input. We show here that the temporal diameter of the clique is crucially affected by the clique's lifetime, a, e.g., when a is asymptotically larger than the number of vertices, n, then the temporal diameter must be Ω(a/nlog n ). We, then, consider the least number, r, of random points in time at which an edge is available, in order to guarantee at least a temporal path between any pair of vertices of the network (notice that the clique is the only network for which just one instance of availability per edge, even non-random, suffices for this). We show that r is Ω(log n) even for some networks of diameter 2. Finally, we compare this cost to an (optimal) deterministic allocation of labels of availability that guarantees a temporal path between any pair of vertices. For this reason, we introduce the notion of the Price of Randomness and we show an upper bound for general networks.

Intersection graphs of geometric objects have been extensively studied, both due to their interesting structure and their numerous applications; prominent examples include interval graphs and permutation graphs. In this paper we study a natural graph class that generalizes both interval and permutation graphs, namely simple-triangle graphs. Simple-triangle graphs – also known as PI graphs (for Point-Interval) – are the intersection graphs of triangles that are defined by a point on a line L 1 and an interval on a parallel line L 2. They lie naturally between permutation and trapezoid graphs, which are the intersection graphs of line segments between L 1 and L 2 and of trapezoids between L 1 and L 2, respectively. Although various efficient recognition algorithms for permutation and trapezoid graphs are well known to exist, the recognition of simple-triangle graphs has remained an open problem since their introduction by Corneil and Kamula three decades ago. In this paper we resolve this problem by proving that simple-triangle graphs can be recognized in polynomial time. As a consequence, our algorithm also solves a longstanding open problem in the area of partial orders, namely the recognition of linear-interval orders, i.e. of partial orders P = P 1 ∩ P 2, where P 1 is a linear order and P 2 is an interval order. This is one of the first results on recognizing partial orders P that are the intersection of orders from two different classes $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ . In contrast, partial orders P which are the intersection of orders from the same class $\mathcal{P}$ have been extensively investigated, and in most cases the complexity status of these recognition problems has been established.

We consider the following fundamental scheduling problem in which the input consists of n jobs to be scheduled on a set of identical machines of bounded capacity g (which is the maximal number of jobs that can be processed simultaneously by a single machine). Each job is associated with a start time and a completion time, it is supposed to be processed from the start time to the completion time (and in one of our extensions it has to be scheduled also in a continuous number of days, this corresponds to a two-dimensional version of the problem). We consider two versions of the problem. In the scheduling minimization version the goal is to minimize the total busy time of machines used to schedule all jobs. In the resource allocation maximization version the goal is to maximize the number of jobs that are scheduled for processing under a budget constraint given in terms of busy time. This is the first study of the maximization version of the problem. The minimization problem is known to be NP-Hard, thus the maximization problem is also NP-Hard. We consider various special cases, identify cases where an optimal solution can be computed in polynomial time, and mainly provide constant factor approximation algorithms for both minimization and maximization problems. Some of our results improve upon the best known results for this job scheduling problem. Our study has applications in power consumption, cloud computing and optimizing switching cost of optical networks.

We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (Nature, 433:312–316, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an individual is chosen at random with probability proportional to its assigned “fitness” value. It reproduces, placing a copy of itself on a neighbouring vertex chosen uniformly at random, replacing the individual that was there. The initial population consists of a single mutant of fitness r > 0 placed uniformly at random, with every other vertex occupied by an individual of fitness 1. The main quantities of interest are the probabilities that the descendants of the initial mutant come to occupy the whole graph (fixation) and that they die out (extinction); almost surely, these are the only possibilities. In general, exact computation of these quantities by standard Markov chain techniques requires solving a system of linear equations of size exponential in the order of the graph so is not feasible. We show that, with high probability, the number of steps needed to reach fixation or extinction is bounded by a polynomial in the number of vertices in the graph. This bound allows us to construct fully polynomial randomized approximation schemes (FPRAS) for the probability of fixation (when r ≥ 1) and of extinction (for all r > 0).

Given a graph $G$, the longest path problem asks to compute a simple path of $G$ with the largest number of vertices. This problem is the most natural optimization version of the well-known and well-studied Hamiltonian path problem, and thus it is NP-hard on general graphs. However, in contrast to the Hamiltonian path problem, there are only a few restricted graph families, such as trees, and some small graph classes where polynomial algorithms for the longest path problem have been found. Recently it has been shown that this problem can be solved in polynomial time on interval graphs by applying dynamic programming to a characterizing ordering of the vertices of the given graph [K. Ioannidou, G. B. Mertzios, and S. D. Nikolopoulos, Algorithmica, 61 (2011), pp. 320--341], thus answering an open question. In the present paper, we provide the first polynomial algorithm for the longest path problem on a much greater class, namely on cocomparability graphs. Our algorithm uses a similar, but essentially simpler, dynamic programming approach, which is applied to a lexicographic depth first search (LDFS) characterizing ordering of the vertices of a cocomparability graph. Therefore, our results provide evidence that this general dynamic programming approach can be used in a more general setting, leading to efficient algorithms for the longest path problem on greater classes of graphs. LDFS has recently been introduced in [D. G. Corneil and R. M. Krueger, SIAM J. Discrete Math., 22 (2008), pp. 1259--1276]. Since then, a similar phenomenon of extending an existing interval graph algorithm to cocomparability graphs by using an LDFS preprocessing step has also been observed for the minimum path cover problem [D. G. Corneil, B. Dalton, and M. Habib, submitted]. Therefore, more interestingly, our results also provide evidence that cocomparability graphs present an interval graph structure when they are considered using an LDFS ordering of their vertices, which may lead to other new and more efficient combinatorial algorithms.

The placement of regenerators in optical networks has become an active area of research during the last few years. Given a set of lightpaths in a network$G$and a positive integer$d$, regenerators must be placed in such a way that in any lightpath there are no more than$d$hops without meeting a regenerator. The cost function we consider is given by the total number of regenerators placed at the nodes, which we believe to be a more accurate estimation of the real cost of the network than the number of locations considered in the work of Flammini(IEEE/ACM Trans. Netw., vol. 19, no. 2, pp. 498–511, Apr. 2011). Furthermore, in our model we assume that we are given a finite set of$p$possible traffic patterns (each given by a set of lightpaths), and our objective is to place the minimum number of regenerators at the nodes so that each of the traffic patterns is satisfied. While this problem can be easily solved when$d=1$or$p=1$, we prove that for any fixed$d,p \geq 2$, it does not admit a PTAS, even if$G$has maximum degree at most 3 and the lightpaths have length$ {\cal O}(d)$. We complement this hardness result with a constant-factor approximation algorithm with ratio$\ln (d \cdot p)$. We then study the case where$G$is a path, proving that the problem is polynomial-time solvable for two particular families of instances. Finally, we generalize our model in two natural directions, which allows us to capture the model of Flamminias a particular case, and we settle some questions that were left open therein.

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs has attracted many research efforts, mainly due to its interesting structure and its numerous applications, especially in DNA sequence analysis and resource allocation, among others. In one of the most natural generalizations of tolerance graphs, namely multitolerance graphs, two tolerances are allowed for each interval – one from the left and one from the right side of the interval. Then, in its interior part, every interval tolerates the intersection with others by an amount that is a convex combination of its two border-tolerances. In the comparison of DNA sequences between different organisms, the natural interpretation of this model lies on the fact that, in some applications, we may want to treat several parts of the genomic sequences differently. That is, we may want to be more tolerant at some parts of the sequences than at others. These two tolerances for every interval – together with their convex hull – define an infinite number of the so called tolerance-intervals, which make the multitolerance model inconvenient to cope with. In this article we introduce the first non-trivial intersection model for multitolerance graphs, given by objects in the 3-dimensional space called trapezoepipeds. Apart from being important on its own, this new intersection model proves to be a powerful tool for designing efficient algorithms. Given a multitolerance graph with n vertices and m edges, we present algorithms that compute a minimum coloring and a maximum clique in optimal O(n log n) time, and a maximum weight independent set in O(m + n log n) time. Moreover, our results imply an optimal O(n log n) time algorithm for the maximum weight independent set problem on tolerance graphs, thus closing the complexity gap for this problem. Additionally, by exploiting more the new 3D-intersection model, we completely classify multitolerance graphs in the hierarchy of perfect graphs.

Trapezoid graphs are the intersection graphs of trapezoids, where every trapezoid has a pair of opposite sides lying on two parallel lines L_{1} and L_{2} of the plane. Strictly between permutation and trapezoid graphs lie the simple-triangle graphs -- also known as PI graphs (for Point-Interval) -- where the objects are triangles with one point of the triangle on L_1 and the other two points (i.e. interval) of the triangle on L_2, and the triangle graphs -- also known as PI^* graphs -- where again the objects are triangles, but now there is no restriction on which line contains one point of the triangle and which line contains the other two. The complexity status of both triangle and simple-triangle recognition problems (namely, the problems of deciding whether a given graph is a triangle or a simple-triangle graph, respectively) have been the most fundamental open problems on these classes of graphs since their introduction two decades ago. Moreover, since triangle and simple-triangle graphs lie naturally between permutation and trapezoid graphs, and since they share a very similar structure with them, it was expected that the recognition of triangle and simple-triangle graphs is polynomial, as it is also the case for permutation and trapezoid graphs. In this article we surprisingly prove that the recognition of triangle graphs is NP-complete, even in the case where the input graph is known to be a trapezoid graph.

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its numerous applications (in bioinformatics, constraint-based temporal reasoning, resource allocation, and scheduling problems, among others). Several efficient algorithms for optimization problems that are NP-hard in general graphs have been designed for tolerance graphs. In spite of this, the recognition of tolerance graphs—namely, the problem of deciding whether a given graph is a tolerance graph—as well as the recognition of their main subclass of bounded tolerance graphs, have been the most fundamental open problems on this class of graphs (cf. the book on tolerance graphs [M. C. Golumbic and A. N. Trenk, Tolerance Graphs, Cambridge Stud. Adv. Math. 89, Cambridge University Press, Cambridge, UK, 2004]) since their introduction in 1982 [M. C. Golumbic and C. L. Monma, Proceedings of the 13th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer., 35 (1982), pp. 321–331]. In this article we prove that both recognition problems are NP-complete, even in the case where the input graph is a trapezoid graph. The presented results are surprising because, on the one hand, most subclasses of perfect graphs admit polynomial recognition algorithms and, on the other hand, bounded tolerance graphs were believed to be efficiently recognizable as they are a natural special case of trapezoid graphs (which can be recognized in polynomial time) and share a very similar structure with them. For our reduction we extend the notion of an acyclic orientation of permutation and trapezoid graphs. Our main tool is a new algorithm that uses vertex splitting to transform a given trapezoid graph into a permutation graph, while preserving this new acyclic orientation property. This method of vertex splitting is of independent interest; very recently, it was also proved a powerful tool in the design of efficient recognition algorithms for other classes of graphs [G. B. Mertzios and D. G. Corneil, Discrete Appl. Math., 159 (2011), pp. 1131–1147].

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its numerous applications. Several efficient algorithms for optimization problems that are NP-hard on general graphs have been designed for tolerance graphs. In spite of this, the recognition of tolerance graphs --~namely, the problem of deciding whether a given graph is a tolerance graph~-- as well as the recognition of their main subclass of bounded tolerance graphs, have been the most fundamental open problems on this class of graphs (cf.~the book on tolerance graphs~\cite{GolTol04}) since their introduction in 1982~\cite{GoMo82}. In this article we prove that both recognition problems are NP-complete, even in the case where the input graph is a trapezoid graph. The presented results are surprising because, on the one hand, most subclasses of perfect graphs admit polynomial recognition algorithms and, on the other hand, bounded tolerance graphs were believed to be efficiently recognizable as they are a natural special case of trapezoid graphs (which can be recognized in polynomial time) and share a very similar structure with them. For our reduction we extend the notion of an \emph{acyclic orientation} of permutation and trapezoid graphs. Our main tool is a new algorithm that uses \emph{vertex splitting} to transform a given trapezoid graph into a permutation graph, while preserving this new acyclic orientation property. This method of vertex splitting is of independent interest; very recently, it has been proved a powerful tool also in the design of efficient recognition algorithms for other classes of graphs~\cite{MC-Trapezoid}.

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs, which generalizes in a natural way both interval and permutation graphs, has attracted many research efforts since their introduction in [M. C. Golumbic and C. L. Monma, Congr. Numer., 35 (1982), pp. 321–331], as it finds many important applications in constraint-based temporal reasoning, resource allocation, and scheduling problems, among others. In this article we propose the first non-trivial intersection model for general tolerance graphs, given by three-dimensional parallelepipeds, which extends the widely known intersection model of parallelograms in the plane that characterizes the class of bounded tolerance graphs. Apart from being important on its own, this new representation also enables us to improve the time complexity of three problems on tolerance graphs. Namely, we present optimal $\mathcal{O}(n\log n)$ algorithms for computing a minimum coloring and a maximum clique and an $\mathcal{O}(n^{2})$ algorithm for computing a maximum weight independent set in a tolerance graph with n vertices, thus improving the best known running times $\mathcal{O}(n^{2})$ and $\mathcal{O}(n^{3})$ for these problems, respectively.