Search

The $k$-CombDMR problem is that of determining whether an $n \times n$ distance matrix can be realised by $n$ vertices in some undirected graph with $n + k$ vertices. This problem has a simple solution in the case $k=0$. In this paper we show that this problem is polynomial time solvable for $k=1$ and $k=2$. Moreover, we provide algorithms to construct such graph realisations by solving appropriate 2-SAT instances. In the case where $k \geq 3$, this problem is NP-complete. We show this by a reduction of the $k$-colourability problem to the $k$-CombDMR problem. Finally, we discuss the simpler polynomial time solvable problem of tree realisability for a given distance matrix., Comment: 27 pages, 5 figures

We consider random simple temporal graphs in which every edge of the complete graph $K_n$ appears once within the time interval [0,1] independently and uniformly at random. Our main result is a sharp threshold on the size of any maximum $\delta$-clique (namely a clique with edges appearing at most $\delta$ apart within [0,1]) in random instances of this model, for any constant~$\delta$. In particular, using the probabilistic method, we prove that the size of a maximum $\delta$-clique is approximately $\frac{2\log{n}}{\log{\frac{1}{\delta}}}$ with high probability (whp). What seems surprising is that, even though the random simple temporal graph contains $\Theta(n^2)$ overlapping $\delta$-windows, which (when viewed separately) correspond to different random instances of the Erdos-Renyi random graphs model, the size of the maximum $\delta$-clique in the former model and the maximum clique size of the latter are approximately the same. Furthermore, we show that the minimum interval containing a $\delta$-clique is $\delta-o(\delta)$ whp. We use this result to show that any polynomial time algorithm for $\delta$-TEMPORAL CLIQUE is unlikely to have very large probability of success.

In this paper, we study the complexity of the \textit{periodic temporal graph realization} problem with respect to upper bounds on the fastest path durations among its vertices. This constraint with respect to upper bounds appears naturally in transportation network design applications where, for example, a road network is given, and the goal is to appropriately schedule periodic travel routes, while not exceeding some desired upper bounds on the travel times. This approach is in contrast to verification applications of the graph realization problems, where exact values for the distances (respectively, fastest travel times) are given, following some kind of precise measurement. In our work, we focus only on underlying tree topologies, which are fundamental in many transportation network applications. As it turns out, the periodic upper-bounded temporal tree realization problem (TTR) has a very different computational complexity behavior than both (i) the classic graph realization problem with respect to shortest path distances in static graphs and (ii) the periodic temporal graph realization problem with exact given fastest travel times (which was recently introduced). First, we prove that, surprisingly, TTR is NP-hard, even for a constant period $\Delta$ and when the input tree $G$ satisfies at least one of the following conditions: (a) $G$ has a constant diameter, or (b) $G$ has constant maximum degree. In contrast, when we are given exact values of the fastest travel delays, the problem is known to be solvable in polynomial time. Second, we prove that TTR is fixed-parameter tractable (FPT) with respect to the number of leaves in the input tree $G$, via a novel combination of techniques for totally unimodular matrices and mixed integer linear programming.

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., Comment: 30 pages, 17 figures

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.

In this paper we initiate the study of the temporal graph realization problem with respect to the fastest path durations among its vertices, while we focus on periodic temporal graphs. Given an $n \times n$ matrix $D$ and a $\Delta \in \mathbb{N}$, the goal is to construct a $\Delta$-periodic temporal graph with $n$ vertices such that the duration of a fastest path from $v_i$ to $v_j$ is equal to $D_{i,j}$, or to decide that such a temporal graph does not exist. The variations of the problem on static graphs have been well studied and understood since the 1960's (e.g. [Erd\H{o}s and Gallai, 1960], [Hakimi and Yau, 1965]). As it turns out, the periodic temporal graph realization problem has a very different computational complexity behavior than its static (i.e. non-temporal) counterpart. First, we show that the problem is NP-hard in general, but polynomial-time solvable if the so-called underlying graph is a tree. Building upon those results, we investigate its parameterized computational complexity with respect to structural parameters of the underlying static graph which measure the ``tree-likeness''. We prove a tight classification between such parameters that allow fixed-parameter tractability (FPT) and those which imply W[1]-hardness. We show that our problem is W[1]-hard when parameterized by the feedback vertex number (and therefore also any smaller parameter such as treewidth, degeneracy, and cliquewidth) of the underlying graph, while we show that it is in FPT when parameterized by the feedback edge number (and therefore also any larger parameter such as maximum leaf number) of the underlying graph., Comment: 57 pages, 10 figures

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 problem VERTEX COVER 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., Comment: Changes to section 4.2.2

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 $|\lambda|$ of time-labels that we need to add to the edges of $G$ such that the resulting temporal graph $(G,\lambda)$ 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,\lambda)$. 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., Comment: 45 pages, 36 figures

We study a new algorithmic process of graph growth which starts from a single initial vertex and operates in discrete time-steps, called \emph{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 will be removed. Removed edges are called \emph{excess edges}. The main problem investigated in this paper is: Given a target graph $G$, we are asked to design an algorithm that outputs such a process growing $G$, called a \emph{growth schedule}. Additionally, the algorithm should try to minimize the total number of slots $k$ and of excess edges $\ell$ used by the process. We provide both positive and negative results for different values of $k$ and $\ell$, with our main focus being either schedules with sub-linear number of slots or with zero excess edges., Comment: 30 pages

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 et al., 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, we introduce the 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_1$ and $v$ has a directed edge towards $w$ with time-label $t_2\geq t_1$, then $u$ also has a directed edge towards $w$ with some time-label $t_3\geq t_2$. If we just demand that this implication holds whenever $t_2 > t_1$, the orientation is called strictly temporally transitive. Our main result is a conceptually simple, yet technically quite involved, polynomial-time algorithm for recognizing whether a given temporal graph $\mathcal{G}$ is transitively orientable. In wide contrast we prove that, surprisingly, it is NP-hard to recognize whether $\mathcal{G}$ 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.

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 \le m$ days. This corresponds to an equitable schedule where each client is guaranteed a minimal level of service throughout the period of $m$ days. We provide a thorough analysis of the computational complexity of three main variants of this problem, identifying both efficient algorithms and worst-case intractability results.

This paper studies the maximum cardinality matching problem in stochastically evolving graphs. We formally define the arrival-departure model with stochastic departures. There, a graph is sampled from a specific probability distribution and it is revealed as a series of snapshots. Our goal is to study algorithms that create a large matching in the sampled graphs. We define the price of stochasticity for this problem which intuitively captures the loss of any algorithm in the worst case in the size of the matching due to the uncertainty of the model. Furthermore, we prove the existence of a deterministic optimal algorithm for the problem. In our second set of results we show that we can efficiently approximate the expected size of a maximum cardinality matching by deriving a fully randomized approximation scheme (FPRAS) for it. The FPRAS is the backbone of a probabilistic algorithm that is optimal when the model is defined over two timesteps. Our last result is an upper bound of $\frac{2}{3}$ on the price of stochasticity. This means that there is no algorithm that can match more than $\frac{2}{3}$ of the edges of an optimal matching in hindsight., Comment: 12 pages, 3 figures

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\alpha (\sqrt{n}+2\alpha)+8$, where $\alpha = \frac{\Delta-2}{\delta-2}$ and $\delta,\Delta$ are the minimum and the maximum degree of the graph, respectively. This approximation result also improves the state of the art., Comment: 28 pages, 4 algorithms, 5 figures

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 with the same objective function as $P$. Our central result is the LP complementation theorem, that establishes the following relationship between the optimal value $\text{Opt}(P)$ of $P$ and the optimal value $\text{Opt}(Q)$ of its complement: $\frac{1}{\text{Opt}(P)}+\frac{1}{\text{Opt}(Q)}=1$. The LP complementation operation can be applied if and only if $\text{Opt}(P) > 1$. We then apply LP complementation to hypergraphs. For every hypergraph $H=(V,E)$, its dual is $H^*$ and we call $\overline{H}=(V,\{V\setminus e : e\in E\})$ the complement of $H$. For the covering LP $K(H)$ we obtain $\frac{1}{ \text{Opt}( K(H^*) ) }+\frac{1}{\text{Opt}( K(\overline{H}) ) } = 1$ (and similarly for packing, matching and transversal LPs). We then consider \emph{fractional graph theory}. We prove that the LP for the \Define{fractional in-dominating number} of a digraph $D$ is the complement of the LP for the \Define{fractional total out-dominating number} of the digraph complement of $D$. We also establish that the fractional matching number of a matroid coincides with its edge toughness. Finally, we introduce the problem \text{Vertex Cover with Budget (VCB)}: for a graph $G$ and a positive integer $b$, what is the maximum number $t_b$ of vertex covers $S_1, \dots, S_{t_b}$ of $G$, such that every vertex appears in at most $b$ vertex covers? We relate \text{VCB} with the LP $Q_G$ for the fractional chromatic number of $G$: as $b \to \infty$, $t_b \sim t_f \cdot b$, where $t_f$ is the optimal value of the complement LP of $Q_G$.

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 $\Delta$ consecutive time slots, where $\Delta \in \mathbb{N}$ is given. The requirement that a vertex cannot be matched twice in any $\Delta$-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 are used to abstractly model real-life networks that are inherently dynamic in nature. Given a static underlying graph $G=(V,E)$, a temporal graph on $G$ is a sequence of snapshots $G_t$, one for each time step $t\geq 1$. In this paper we study stochastic temporal graphs, i.e. stochastic processes $\mathcal{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\in E$ appears at time step $t$ depends on its appearance (or absence) at the previous $k$ steps. In this paper we study the hierarchy of models memory-$k$, addressing this memory effect in an edge-centric network evolution: every edge of $G$ has its own independent probability distribution for its appearance over time. Clearly, for every $k\geq 1$, memory-$(k-1)$ is a special case of memory-$k$. We make a clear distinction between the values $k=0$ ("no memory") and $k\geq 1$ ("some memory"), as in some cases these models exhibit a fundamentally different computational behavior, as our results indicate. For every $k\geq 0$ we investigate the complexity of two naturally related, but fundamentally different, temporal path (journey) problems: MINIMUM ARRIVAL and BEST POLICY. In the first problem we are looking for the expected arrival time of a foremost journey between two designated vertices $s,y$. In the second one we are looking for the arrival time of the best policy for actually choosing a particular $s$-$y$ journey. We present a detailed investigation of the computational landscape of both problems for the different values of memory $k$. Among other results we prove that, surprisingly, MINIMUM ARRIVAL is strictly harder than BEST POLICY; in fact, for $k=0$, MINIMUM ARRIVAL is #P-hard while BEST POLICY is solvable in $O(n^2)$ time., Comment: 22 pages, 2 figures, 4 algorithms

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 $\Delta$, we ask for a coloring sequence for each vertex such that (i) in every sliding time window of $\Delta$ 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).

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 modeled 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 study the problem of exploring a temporal graph (i.e. a graph that changes over time), in the fundamental case where the underlying static graph is a star. The aim of the exploration problem in a temporal star is to find a temporal walk which starts at the center of the star, visits all leafs, and eventually returns back to the center. We initiate a systematic study of the computational complexity of this problem, depending on the number k of time-labels that every edge is allowed to have; that is, on the number k of time points where every edge can be present in the graph. To do so, we distinguish between the decision version StarExp(k) asking whether a complete exploration of the instance exists, and the maximization version MaxStarExp(k) of the problem, asking for an exploration schedule of the greatest possible number of edges in the star. We present here a collection of results establishing the computational complexity of these two problems. On the one hand, we show that both MaxStarExp(2) and StarExp(3) can be efficiently solved in O(n log n) time on a temporal star with n vertices. On the other hand, we show that, for every k >= 6, StarExp(k) is NP-complete and MaxStarExp(k) is APX-hard, and thus it does not admit a PTAS, unless P = NP. The latter result is complemented by a polynomial-time 2-approximation algorithm for MaxStarExp(k), for every k, thus proving that MaxStarExp(k) is APX-complete. Finally, we give a partial characterization of the classes of temporal stars with random labels which are, asymptotically almost surely, yes-instances and no-instances for StarExp(k) respectively.

We consider the problem of computing the size of each $r$-neighbourhood for every vertex of a graph. Specifically, we ask whether the size of the closed second neighbourhood can be computed in subquadratic time. Adapting the SETH reductions by Abboud et al. (2016) that exclude subquadratic algorithms to compute the radius of a graph, we find that a subquadratic algorithm would violate the SETH. On the other hand, a linear fpt-time algorithm by Demaine et al. (2014) parameterized by a certain `sparseness parameter' of the graph is known, where the dependence on the parameter is exponential. We show here that a better dependence is unlikely: for any~$\delta < 2$, no algorithm running in time $O(2^{o({\rm vc}(G))} \, n^{\delta})$, where~${\rm vc}(G)$ is the vertex cover number, is possible unless the SETH fails. We supplement these lower bounds with algorithms that solve the problem in time~$O(2^{{\rm vc}(G)/2} {\rm vc}(G)^2 \cdot n)$ and $O(2^w w \cdot n)$.

Modern, inherently dynamic systems are usually characterized by a network structure, i.e. an underlying graph topology, which is subject to discrete changes over time. Given a static underlying graph $G$, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge of $G$, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs has focused on the notion of a temporal path and other "path-related" temporal notions, only few attempts have been made to investigate "non-path" temporal graph problems. In this paper, motivated by applications in sensor and in transportation networks, we introduce and study two natural temporal extensions of the classical problem Vertex Cover. In both cases we wish to minimize the total number of "vertex appearances" that are needed to "cover" the whole temporal graph. In our first problem, Temporal Vertex Cover, the aim is to cover every edge at least once during the lifetime of the temporal graph, where an edge can be covered by one of its endpoints, only at a time step when it is active. In our second, more pragmatic variation Sliding Window Temporal Vertex Cover, we are also given a natural number $\Delta$, and our aim is to cover every edge at least once at every $\Delta$ consecutive time steps. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. In particular, we provide strong hardness results, complemented by various 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.

A vertex $x$ in a tournament $T$ is called a king if for every vertex $y$ of $T$ there is a directed path from $x$ to $y$ of length at most 2. It is not hard to show that every vertex of maximum out-degree in a tournament is a king. However, tournaments may have kings which are not vertices of maximum out-degree. A binary inquiry asks for the orientation of the edge between a pair of vertices and receives the answer. The cost of finding a king in an unknown tournament is the number of binary inquiries required to detect a king. For the cost of finding a king in a tournament, in the worst case, Shen, Sheng and Wu (SIAM J. Comput., 2003) proved a lower and upper bounds of $\Omega(n^{4/3})$ and $O(n^{3/2})$, respectively. In contrast to their result, we prove that the cost of finding a vertex of maximum out-degree is ${n \choose 2} -O(n)$ in the worst case.

Kernelization is an important tool in parameterized algorithmics. Given an input instance accompanied by a parameter, the goal is to compute in polynomial time an equivalent instance of the same problem such that the size of the reduced instance only depends on the parameter and not on the size of the original instance. In this paper, we provide a first conceptual study on limits of kernelization for several polynomial-time solvable problems. For instance, we consider the problem of finding a triangle with negative sum of edge weights parameterized by the maximum degree of the input graph. We prove that a linear-time computable strict kernel of truly subcubic size for this problem violates the popular APSP-conjecture., Comment: An extended abstract appeared in Proceedings of the 14th Conference on Computability in Europe (CiE 2018)

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 develop a linear-time algorithm to find maximum-cardinality matchings on cocomparability graphs, a prominent subclass of perfect graphs that contains interval graphs as well as permutation graphs. Our algorithm is based on the recently discovered Lexicographic Depth First Search (LDFS)., Comment: 16 pages, 4 figures. to appear at SIDMA arXiv admin note: text overlap with arXiv:1609.08879

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 $\Gamma$ 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.

Hyperbolicity measures, in terms of (distance) metrics, how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen intensive research over the last years. Unfortunately, the best known algorithms for computing the hyperbolicity number of a graph (the smaller, the more tree-like) have running time $O(n^4)$, where $n$ is the number of graph vertices. Exploiting the framework of parameterized complexity analysis, we explore possibilities for "linear-time FPT" algorithms to compute hyperbolicity. For instance, we show that hyperbolicity can be computed in time $O(2^{O(k)} + n +m)$ ($m$ being the number of graph edges) while at the same time, unless the SETH fails, there is no $2^{o(k)}n^2$-time algorithm.

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 (almost) 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., Comment: Available as 'Online First' in Algorithmica

This work studies the parameterized complexity of finding secluded solutions to classical combinatorial optimization problems on graphs such as finding minimum s-t separators, feedback vertex sets, dominating sets, maximum independent sets, and vertex deletion problems for hereditary graph properties: Herein, one searches not only to minimize or maximize the size of the solution, but also to minimize the size of its neighborhood. This restriction has applications in secure routing and community detection., Comment: Compared to the previous version, this version additionally shows that Small Secluded s-t-Separator is fixed-parameter tractable parameterized by the combination of the solution size and the open neighborhood size (Theorem 3.5). To appear in Discrete Optimization

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 two natural parameters of the problem, for which we establish a sharp threshold behavior between NP-hardness and tractability. On the positive side, we present a randomized approximation algorithm (RGMA) for GreedyMatching on a special class of weighted graphs, called bush graphs. 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 $\rho$, then for every $\epsilon>0$ the randomized MRG algorithm of [Aronson et al., Rand. Struct. Alg. 1995] gives a $(\rho-\epsilon)$-approximation for the maximum cardinality matching. We conjecture that a tight bound for $\rho$ is $\frac{2}{3}$; we prove our conjecture true for two 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 $\rho$) is a long-standing open problem [Poloczek and Szegedy; FOCS 2012]. This unexpected relation of our RGMA algorithm with the MRG algorithm may provide new insights for solving this problem., Comment: 21 pages, 6 figures

We investigate the parameterized complexity of the graph editing problem called Editing to a Graph with a Given Degree Sequence, where the aim is to obtain a graph with a given degree sequence \sigma by at most k vertex or edge deletions and edge additions. We show that the problem is W[1]-hard when parameterized by k for any combination of the allowed editing operations. From the positive side, we show that the problem can be solved in time 2^{O(k(\Delta+k)^2)}n^2 log n for n-vertex graphs, where \Delta=max \sigma, i.e., the problem is FPT when parameterized by k+\Delta. We also show that Editing to a Graph with a Given Degree Sequence has a polynomial kernel when parameterized by k+\Delta if only edge additions are allowed, and there is no polynomial kernel unless NP\subseteq coNP/poly for all other combinations of allowed editing operations., Comment: arXiv admin note: text overlap with arXiv:1311.4768

We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets of an interval or a permutation graph. In these problems, one asks to find a subset of vertices, normally called a \emph{solution} set, using which all vertices of the graph are distinguished. The identification can be done by considering the neighborhood within the solution set, or by employing the distances to the solution vertices. Normally the goal is to minimize the size of the solution set then. Here we study the case of interval graphs, unit interval graphs, (bipartite) permutation graphs and cographs. For these classes of graphs we give tight lower bounds for the size of such solution sets depending on the order of the input graph. While such lower bounds for the general class of graphs are in logarithmic order, the improved bounds in these special classes are of the order of either quadratic root or linear in terms of number of vertices. Moreover, the results for cographs lead to linear-time algorithms to solve the considered problems on inputs that are cographs., Comment: formerly part of arXiv:1405.2424

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., Comment: 34 pages, 1 figure, 1 algorithm, 4 reduction rules

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\not= 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 \emph{freely choose} availability instances for all edges and aims for temporal connectivity with very small \emph{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 \emph{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=NP$. 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 \emph{minimal}, i.e., no redundant labels exist. We show the existence of minimal temporal designs with at least $n \log{n}$ labels.

In this work we consider \emph{temporal networks}, i.e. networks defined by a \emph{labeling} $\lambda$ assigning to each edge of an \emph{underlying graph} $G$ a set of \emph{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 \emph{path problems} of temporal networks. In particular, we consider \emph{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 \emph{natural analogue of Menger's theorem} holding for arbitrary temporal networks. Finally, we propose two \emph{cost minimization parameters} for temporal network design. One is the \emph{temporality} of $G$, in which the goal is to minimize the maximum number of labels of an edge, and the other is the \emph{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 \emph{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.

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 from the left and one from 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 article 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, solving thus a longstanding open problem. This problem is the first one that has been discovered with a different complexity status in these two graph classes.

We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets (denoted IDENTIFYING CODE, (OPEN) LOCATING-DOMINATING SET and METRIC DIMENSION) of an interval or a permutation graph. In these problems, one asks to distinguish all vertices of a graph by a subset of the vertices, using either the neighbourhood within the solution set or the distances to the solution vertices. Using a general reduction for this class of problems, we prove that the decision problems associated to these four notions are NP-complete, even for interval graphs of diameter $2$ and permutation graphs of diameter $2$. While IDENTIFYING CODE and (OPEN) LOCATING-DOMINATING SET are trivially fixed-parameter-tractable when parameterized by solution size, it is known that in the same setting METRIC DIMENSION is $W[2]$-hard. We show that for interval graphs, this parameterization of METRIC DIMENSION is fixed-parameter-tractable., Comment: 22 pages, 9 figures. Some theorems have been restated and errors have been corrected

An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: L, \Gamma, LE{} and \eeG. A $k$-bend path is a simple path in the plane, whose direction changes $k$ times from horizontal to vertical. If a graph admits an intersection representation in which every vertex is represented by an L, an L{} or \Gamma, a $k$-bend path, or a segment, then this graph is called an $\{L\}$-graph, $\{L,\Gamma\}$-graph, $B_k$-VPG-graph or SEG-graph, respectively. Motivated by a theorem of Middendorf and Pfeiffer [Discrete Mathematics, 108(1):365--372, 1992], stating that every $\{L,\Gamma\}$-graph is a SEG-graph, we investigate several known subclasses of SEG-graphs and show that they are $\{L\}$-graphs, or $B_k$-VPG-graphs for some small constant $k$. We show that all planar $3$-trees, all line graphs of planar graphs, and all full subdivisions of planar graphs are $\{L\}$-graphs. Furthermore we show that all complements of planar graphs are $B_{17}$-VPG-graphs and all complements of full subdivisions are $B_2$-VPG-graphs. Here a full subdivision is a graph in which each edge is subdivided at least once., Comment: 15 pages, 8 figures, (improved Thm. 4)

We study here the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types. The vertices may have a few additional possible states and can interact in pairs only if they share an edge. Any (population) protocol is required to stabilize in the initial majority. We first present and analyze a protocol with 4 states per vertex that always computes the initial majority value, under any fair scheduler. As we prove, this protocol is optimal, in the sense that there is no population protocol that always computes majority with fewer than 4 states per vertex. However this does not rule out the existence of a protocol with 3 states per vertex that is correct with high probability. To this end, we examine a very natural majority protocol with 3 states per vertex, introduced in [Angluin et al. 2008] where its performance has been analyzed for the clique graph. We study the performance of this protocol in arbitrary networks. We prove that, when the two initial states are put uniformly at random on the vertices, this protocol converges to the initial majority with probability higher than the probability of converging to the initial minority. In contrast, we present an infinite family of graphs, on which the protocol can fail whp, even when the difference between the initial majority and the initial minority is $n - \Theta(\ln{n})$. We also present another infinite family of graphs in which the protocol of Angluin et al. takes an expected exponential time to converge. These two negative results build upon a very positive result concerning the robustness of the protocol on the clique. Surprisingly, the resistance of the clique to failure causes the failure in general graphs. Our techniques use new domination and coupling arguments for suitably defined processes whose dynamics capture the antagonism between the states involved.