Arrow Research search

Author name cluster

Paul G. Spirakis

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

56 papers
2 author rows

Possible papers

56

TCS Journal 2026 Journal Article

Round-delayed amnesiac flooding

  • Oluwatobi Alafin
  • George B. Mertzios
  • Paul G. Spirakis

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.

Details DOI

TCS Journal 2025 Journal Article

Temporal graph realization from fastest paths

  • Nina Klobas
  • George B. Mertzios
  • Hendrik Molter
  • Paul G. Spirakis

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 × n matrix D and a Δ ∈ N, the goal is to construct a Δ-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 1960s (e. g. [Erdő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.

Details DOI

MFCS Conference 2025 Conference Paper

Temporal Graph Realization with Bounded Stretch

  • George B. Mertzios
  • Hendrik Molter
  • Nils Morawietz
  • Paul G. Spirakis

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 steps, where Δ is a given period length. This model offers a natural abstraction of transportation networks where each transportation link connects two destinations periodically. 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 physical distances, i. e. their distances in the underlying static (non-temporal) 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 polynomial-time algorithm (the radius-algorithm) which always guarantees an approximation strictly smaller than Δ, and which also computes the optimum stretch in some cases. 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; for this problem we prove that it is W[2]-hard but admits an XP algorithm with respect to k.

Details

TCS Journal 2025 Journal Article

The contest game for crowdsourcing reviews

  • Vittorio Bilò
  • Marios Mavronicolas
  • Paul G. Spirakis

We consider a contest game with discrete strategies, modelling a contest where reviews for a proposal are crowdsourced from n players. Player i has a skill s i, strategically chooses a quality q ∈ { 1, 2, …, Q } for her review and pays an effort f q ≥ 0, strictly increasing with q. Under voluntary participation, a player may opt to not write a review, paying zero effort; mandatory participation excludes this option. For her effort, she is awarded a payment per her payment function, which is either player-invariant, like, e. g. , the popular proportional allocation, or player-specific; it is oblivious when it does not depend on the loads on other qualities. The utility to player i is the difference between her payment and her cost, calculated by a skill-effort function Λ ( s i, f q ). Skills may vary for arbitrary players; when players are anonymous, s i = 1 for each player i. In a pure Nash equilibrium, no player could increase her utility by unilaterally switching to another quality. We show the following results about the (in)existence and the computation of a pure Nash equilibrium: • A contest game with arbitrary players and player-invariant and oblivious payments is an unweighted congestion game with player-specific constants on parallel links [42]; so it has a generalized ordinal potential, the Finite Improvement Property (FIP) and a pure Nash equilibrium, which can be computed in PLS. However, under the assumption that the payment function is monotonically nonincreasing, a pure Nash equilibrium can be computed efficiently by resorting to [44, Theorem 2]. In contrast, a pure Nash equilibrium might not exist for (i) anonymous players and player-invariant but not oblivious payments, (ii) arbitrary players and proportionally allocated payments, and (iii) anonymous players and player-specific and oblivious payments; in the latter case, it is NP -hard to decide existence even if players are anonymous. These counterexamples prove the tightness of our existence result and suggest that the decision and search problems for a pure Nash equilibrium are computationally hard. • Under some mild assumptions on the efforts, the contest game with anonymous players and proportional allocation has at least one Nash equilibrium. For arbitrary players, we identify a simple condition involving both skills and efforts that suffices for the existence of a pure Nash equilibrium in the special case where the skill-effort function has the product form Λ ( s i, f q ) = s i f q. In both cases the pure Nash equilibrium is simple and computable in constant time. • Under the assumption that costs are player-consistent, there is a polynomial-time Θ ( n Q ) algorithm to decide the existence and compute a pure Nash equilibrium for constant Q, for the case of arbitrary players and player-invariant payments; so the computational problem is XP -tractable with respect to the parameter Q. Player-consistent costs means that all players are incurred the same relative costs for a given pair of qualities. The computed equilibrium is contiguous by design: players with higher skills are contiguously assigned to lower qualities. Our results indicate that the decision and search problems for pure Nash equilibria are likely to be computationally hard even in the simplest case, but can be made easy even in the hardest case by adopting simple assumptions on efforts, payments or costs, no matter whether participation is mandatory or voluntary.

Details DOI

MFCS Conference 2023 Conference Paper

Sliding into the Future: Investigating Sliding Windows in Temporal Graphs (Invited Talk)

  • Nina Klobas
  • George B. Mertzios
  • Paul G. Spirakis

Graphs are fundamental tools for modelling relations among objects in various scientific fields. However, traditional static graphs have limitations when it comes to capturing the dynamic nature of real-world systems. To overcome this limitation, temporal graphs have been introduced as a framework to model graphs that change over time. In temporal graphs the edges among vertices appear and disappear at specific time steps, reflecting the temporal dynamics of the observed system, which allows us to analyse time dependent patterns and processes. In this paper we focus on the research related to sliding time windows in temporal graphs. Sliding time windows offer a way to analyse specific time intervals within the lifespan of a temporal graph. By sliding the window along the timeline, we can examine the graph’s characteristics and properties within different time periods. This paper provides an overview of the research on sliding time windows in temporal graphs. Although progress has been made in this field, there are still many interesting questions and challenges to be explored. We discuss some of the open problems and highlight their potential for future research.

Details

TCS Journal 2023 Journal Article

Threshold-based network structural dynamics

  • Evangelos Kipouridis
  • Paul G. Spirakis
  • Kostas Tsichlas

The interest in dynamic processes on networks is steadily rising in recent years. In this paper, we consider the ( α, β ) -Threshold Network Dynamics ( ( α, β ) -Dynamics), where α ≤ β, in which only structural dynamics (edge dynamics of the network) are allowed, guided by local threshold rules executed by each node. In particular, in each discrete round t, each active pair of nodes u and v, computes a value E ( u, v ) (the potential of the pair) as a function of the local structure of the network at round t around the two nodes. If E ( u, v ) < α then the link (if it exists) between u and v is removed; if α ≤ E ( u, v ) < β then an existing link among u and v is maintained; if β ≤ E ( u, v ) then a link between u and v is established if not already present. New nodes cannot be inserted as a result of the protocol, and existing nodes cannot be removed. The microscopic structure of ( α, β ) -Dynamics appears to be simple, so that we are able to rigorously argue about it, but still flexible, so that we are able to design meaningful microscopic local rules that give rise to interesting macroscopic behaviors. Our goals are the following: a) to investigate the properties of the ( α, β ) -Threshold Network Dynamics and b) to show that ( α, β ) -Dynamics is expressive enough to solve complex problems on networks. Our contribution in these directions is twofold. We rigorously exhibit the claim about the expressiveness of ( α, β ) -Dynamics, both by designing a simple protocol that provably computes the k-core of the network as well as by showing that ( α, β ) -Dynamics are in fact Turing-Complete. Second and most important, we construct general tools for proving stabilization that work for a subclass of ( α, β ) -Dynamics and prove speed of convergence in a restricted setting.

Details DOI

MFCS Conference 2022 Conference Paper

The Complexity of Computing Optimum Labelings for Temporal Connectivity

  • Nina Klobas
  • George B. Mertzios
  • Hendrik Molter
  • Paul G. Spirakis

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 "important" vertices which lie in a subset R ⊆ V, which we call the terminals. This relaxed problem resembles the problem Steiner Tree in static (i. e. , non-temporal) 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 remains 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 (unless P=NP or W[1]=FPT).

Details

AAAI Conference 2022 Conference Paper

The Complexity of Temporal Vertex Cover in Small-Degree Graphs

  • Thekla Hamm
  • Nina Klobas
  • George B. Mertzios
  • Paul G. Spirakis

Temporal graphs naturally model graphs whose underlying topology changes over time. Recently, the problems TEM- PORAL VERTEX COVER (or TVC) and SLIDING-WINDOW TEMPORAL VERTEX COVER (or ∆-TVC for time-windows of a fixed-length ∆) 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 ∆-TVC on sparse graphs. Our main result shows that for every ∆ ≥ 2, ∆-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 ∆-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.

PDF Details

MFCS Conference 2021 Conference Paper

The Complexity of Transitively Orienting Temporal Graphs

  • George B. Mertzios
  • Hendrik Molter
  • Malte Renken
  • Paul G. Spirakis
  • Philipp Zschoche

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.

Details

AAMAS Conference 2021 Conference Paper

Walrasian Equilibria in Markets with Small Demands

  • Argyrios Deligkas
  • Themistoklis Melissourgos
  • Paul G. Spirakis

We study the complexity of finding a Walrasian equilibrium in markets where the agents have 𝑘-demand valuations. These valuations are an extension of unit-demand valuations where a bundle’s value is the maximum of its 𝑘-subsets’ values. For unit-demand agents, where the existence of a Walrasian equilibrium is guaranteed, we show that the problem is in quasi-NC. For 𝑘 = 2, we show that it is NP-hard to decide if a Walrasian equilibrium exists even if the valuations are submodular, while for 𝑘 = 3 the hardness carries over to budget-additive valuations. In addition, we give a polynomial-time algorithm for markets with 2-demand single-minded valuations, or unit-demand valuations.

PDF

MFCS Conference 2020 Conference Paper

Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle

  • Argyrios Deligkas
  • George B. Mertzios
  • Paul G. Spirakis
  • Viktor Zamaraev

In this paper we consider the following total functional problem: Given a cubic Hamiltonian graph G and a Hamiltonian cycle C₀ of G, how can we compute a second Hamiltonian cycle C₁ ≠ C₀ of G? Cedric Smith and William Tutte proved in 1946, using a non-constructive parity argument, that such a second Hamiltonian cycle always exists. Our main result is a deterministic algorithm which computes the second Hamiltonian cycle in O(n⋅2^0. 299862744n) = O(1. 23103ⁿ) time and in linear space, thus improving the state of the art running time of O*(2^0. 3n) = O(1. 2312ⁿ) for solving this problem (among deterministic algorithms running in polynomial space). Whenever the input graph G does not contain any induced cycle C₆ on 6 vertices, the running time becomes O(n⋅ 2^0. 2971925n) = O(1. 22876ⁿ). 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 (not necessarily cubic) Hamiltonian graph G with a given Hamiltonian cycle C₀ (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α (√n+2α)+8, where α = (Δ-2)/(δ-2) and δ, Δ are the minimum and the maximum degree of the graph, respectively. This approximation result also improves the state of the art.

Details

MFCS Conference 2017 Conference Paper

Binary Search in Graphs Revisited

  • Argyrios Deligkas
  • George B. Mertzios
  • Paul G. Spirakis

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.

Details

MFCS Conference 2016 Conference Paper

Stably Computing Order Statistics with Arithmetic Population Protocols

  • George B. Mertzios
  • Sotiris E. Nikoletseas
  • Christoforos L. Raptopoulos
  • Paul G. Spirakis

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.

Details

MFCS Conference 2012 Conference Paper

Maximum Cliques in Graphs with Small Intersection Number and Random Intersection Graphs

  • Sotiris E. Nikoletseas
  • Christoforos L. Raptopoulos
  • Paul G. Spirakis

Abstract In this paper, we relate the problem of finding a maximum clique to the intersection number of the input graph (i. e. the minimum number of cliques needed to edge cover the graph). In particular, we consider the maximum clique problem for graphs with small intersection number and random intersection graphs (a model in which each one of m labels is chosen independently with probability p by each one of n vertices, and there are edges between any vertices with overlaps in the labels chosen). We first present a simple algorithm which, on input G finds a maximum clique in \(O(2^{2^m + O(m)} + n^2 \min\{2^m, n\})\) time steps, where m is an upper bound on the intersection number and n is the number of vertices. Consequently, when m ≤ ln ln n the running time of this algorithm is polynomial. We then consider random instances of the random intersection graphs model as input graphs. As our main contribution, we prove that, when the number of labels is not too large ( m = n α, 0 < α < 1), we can use the label choices of the vertices to find a maximum clique in polynomial time whp. The proof of correctness for this algorithm relies on our Single Label Clique Theorem, which roughly states that whp a “large enough” clique cannot be formed by more than one label. This theorem generalizes and strengthens other related results in the state of the art, but also broadens the range of values considered (see e. g. [22] and [4]). As an important consequence of our Single Label Clique Theorem, we prove that the problem of inferring the complete information of label choices for each vertex from the resulting random intersection graph (i. e. the label representation of the graph ) is solvable whp; namely, the maximum likelihood estimation method will provide a unique solution (up to permutations of the labels). Finding efficient algorithms for constructing such a label representation is left as an interesting open problem for future research.

Details

MFCS Conference 2010 Conference Paper

All Symmetric Predicates in NSPACE ( n 2 ) Are Stably Computable by the Mediated Population Protocol Model

  • Ioannis Chatzigiannakis
  • Othon Michail
  • Stavros Nikolaou
  • Andreas Pavlogiannis
  • Paul G. Spirakis

Abstract This work focuses on the computational power of the Mediated Population Protocol model on complete communication graphs and initially identical edges ( SMPP ). In particular, we investigate the class MPS of all predicates that are stably computable by the SMPP model. It is already known that MPS is in the symmetric subclass of NSPACE ( n 2 ). Here we prove that this inclusion holds with equality, thus, providing the following exact characterization for MPS: A predicate is in MPS iff it is symmetric and is in NSPACE ( n 2 ).

Details

MFCS Conference 2009 Conference Paper

Colouring Non-sparse Random Intersection Graphs

  • Sotiris E. Nikoletseas
  • Christoforos L. Raptopoulos
  • Paul G. Spirakis

Abstract An intersection graph of n vertices assumes that each vertex is equipped with a subset of a global label set. Two vertices share an edge when their label sets intersect. Random Intersection Graphs (RIGs) (as defined in [18, 32]) consider label sets formed by the following experiment: each vertex, independently and uniformly, examines all the labels ( m in total) one by one. Each examination is independent and the vertex succeeds to put the label in her set with probability p. Such graphs nicely capture interactions in networks due to sharing of resources among nodes. We study here the problem of efficiently coloring (and of finding upper bounds to the chromatic number) of RIGs. We concentrate in a range of parameters not examined in the literature, namely: (a) m = n α for α less than 1 (in this range, RIGs differ substantially from the Erdös-Renyi random graphs) and (b) the selection probability p is quite high (e. g. at least \(\frac{\ln^2{n}}{m}\) in our algorithm) and disallows direct greedy colouring methods. We manage to get the following results: For the case mp ≤ β ln n, for any constant β < 1 − α, we prove that np colours are enough to colour most of the vertices of the graph with high probability (whp). This means that even for quite dense graphs, using the same number of colours as those needed to properly colour the clique induced by any label suffices to colour almost all of the vertices of the graph. Note also that this range of values of m, p is quite wider than the one studied in [4]. We propose and analyze an algorithm CliqueColour for finding a proper colouring of a random instance of \({\cal G}_{n, m, p}\), for any mp ≥ ln 2 n. The algorithm uses information of the label sets assigned to the vertices of G n, m, p and runs in \(O\left(\frac{n^2mp^2}{\ln{n}} \right)\) time, which is polynomial in n and m. We also show by a reduction to the uniform random intersection graphs model that the number of colours required by the algorithm are of the correct order of magnitude with the actual chromatic number of G n, m, p. We finally compare the problem of finding a proper colouring for G n, m, p to that of colouring hypergraphs so that no edge is monochromatic. We show how one can find in polynomial time a k -colouring of the vertices of G n, m, p, for any integer k, such that no clique induced by only one label in G n, m, p is monochromatic. Our techniques are novel and try to exploit as much as possible the hidden structure of random intersection graphs in this interesting range.

Details

TCS Journal 2009 Journal Article

Preface

  • Paul G. Spirakis
  • Marios Mavronicolas
  • Spyros C. Kontogiannis
Details DOI

MFCS Conference 2009 Invited Paper

Recent Advances in Population Protocols

  • Ioannis Chatzigiannakis
  • Othon Michail
  • Paul G. Spirakis

Abstract The population protocol model (PP) proposed by Angluin et al. [2] describes sensor networks consisting of passively mobile finite-state agents. The agents sense their environment and communicate in pairs to carry out some computation on the sensed values. The mediated population protocol model (MPP) [13] extended the PP model by communication links equipped with a constant size buffer. The MPP model was proved in [13] to be stronger than the PP model. However, its most important contribution is that it provides us with the ability to devise optimizing protocols, approximation protocols and protocols that decide properties of the communication graph on which they run. The latter case, suggests a simplified model, the GDM model, that was formally defined and studied in [11]. GDM is a special case of MPP that captures MPP’s ability to decide properties of the communication graph. Here we survey recent advances in the area initiated by the proposal of the PP model and at the same time we provide new protocols, novel ideas and results.

Details

MFCS Conference 2007 Conference Paper

Expander Properties and the Cover Time of Random Intersection Graphs

  • Sotiris E. Nikoletseas
  • Christoforos L. Raptopoulos
  • Paul G. Spirakis

Abstract We investigate important combinatorial and algorithmic properties of G n, m, p random intersection graphs. In particular, we prove that with high probability (a) random intersection graphs are expanders, (b) random walks on such graphs are “rapidly mixing” (in particular they mix in logarithmic time) and (c) the cover time of random walks on such graphs is optimal (i. e. it is Θ ( n log n )). All results are proved for p very close to the connectivity threshold and for the interesting, non-trivial range where random intersection graphs differ from classical G n, p random graphs.

Details

MFCS Conference 2007 Conference Paper

Selfish Load Balancing Under Partial Knowledge

  • Elias Koutsoupias
  • Panagiota N. Panagopoulou
  • Paul G. Spirakis

Abstract We consider n selfish agents or players, each having a load, who want to place their loads to one of two bins. The agents have an incomplete picture of the world: They know some loads exactly and only a probability distribution for the rest. We study Nash equilibria for this model, we compute the Price of Anarchy for some cases and show that sometimes extra information adversely affects the Divergence Ratio (a kind of subjective Price of Anarchy).

Details

MFCS Conference 2007 Conference Paper

Well Supported Approximate Equilibria in Bimatrix Games: A Graph Theoretic Approach

  • Spyros C. Kontogiannis
  • Paul G. Spirakis

Abstract We study the existence and tractability of a notion of approximate equilibria in bimatrix games, called well supported approximate Nash Equilibria (SuppNE in short). We prove existence of ε -SuppNE for any constant ε ∈(0, 1), with only logarithmic support sizes for both players. Also we propose a polynomial-time construction of SuppNE, both for win lose and for arbitrary (normalized) bimatrix games. The quality of these SuppNE depends on the girth of the Nash Dynamics graph in the win lose game, or a (rounded. off) win lose image of the original normalized game. Our constructions are very successful in sparse win lose games (ie, having a constant number of (0, 1)-elements in the bimatrix) with large girth in the Nash Dynamics graph. The same holds also for normalized games whose win lose image is sparse with large girth. Finally we prove the simplicity of constructing SuppNE both in random normalized games and in random win lose games. In the former case we prove that the uniform full mix is an o(1)-SuppNE, while in the case of win lose games, we show that (with high probability) there is either a PNE or a 0. 5-SuppNE with support sizes only 2.

Details

MFCS Conference 2006 Conference Paper

The Price of Defense

  • Marios Mavronicolas
  • Loizos Michael
  • Vicky G. Papadopoulou
  • Anna Philippou
  • Paul G. Spirakis

Abstract We consider a strategic game with two classes of confronting randomized players on a graph G ( V, E ): ν attackers, each choosing vertices and wishing to minimize the probability of being caught, and a defender, who chooses edges and gains the expected number of attackers it catches. The Price of Defense is the worst-case ratio, over all Nash equilibria, of the optimal gain of the defender over its gain at a Nash equilibrium. We provide a comprehensive collection of trade-offs between the Price of Defense and the computational efficiency of Nash equilibria. – Through reduction to a Two-Players, Constant-Sum Game, we prove that a Nash equilibrium can be computed in polynomial time. The reduction does not provide any apparent guarantees on the Price of Defense. – To obtain such, we analyze several structured Nash equilibria: – In a Matching Nash equilibrium, the support of the defender is an Edge Cover. We prove that they can be computed in polynomial time, and they incur a Price of Defense of α ( G ), the Independence Number of G. – In a Perfect Matching Nash equilibrium, the support of the defender is a Perfect Matching. We prove that they can be computed in polynomial time, and they incur a Price of Defense of \(\frac{|V|}{2}\). – In a Defender Uniform Nash equilibrium, the defender chooses uniformly each edge in its support. We prove that they incur a Price of Defense falling between those for Matching and Perfect Matching Nash Equilibria; however, it is \({\cal NP}\) -complete to decide their existence. – In an Attacker Symmetric and Uniform Nash equilibrium, all attackers have a common support on which each uses a uniform distribution. We prove that they can be computed in polynomial time and incur a Price of Defense of either \(\frac{|V|}{2}\) or α ( G ).

Details

MFCS Conference 2003 Conference Paper

Which Is the Worst-Case Nash Equilibrium?

  • Thomas Lücking 0001
  • Marios Mavronicolas
  • Burkhard Monien
  • Manuel Rode
  • Paul G. Spirakis
  • Imrich Vrto

Abstract A Nash equilibrium of a routing network represents a stable state of the network where no user finds it beneficial to unilaterally deviate from its routing strategy. In this work, we investigate the structure of such equilibria within the context of a certain game that models selfish routing for a set of n users each shipping its traffic over a network consisting of m parallel links. In particular, we are interested in identifying the worst-case Nash equilibrium – the one that maximizes social cost. Worst-case Nash equilibria were first introduced and studied in the pioneering work of Koutsoupias and Papadimitriou [9]. More specifically, we continue the study of the Conjecture of the Fully Mixed Nash Equilibrium, henceforth abbreviated as FMNE Conjecture, which asserts that the fully mixed Nash equilibrium, when existing, is the worst-case Nash equilibrium. (In the fully mixed Nash equilibrium, the mixed strategy of each user assigns (strictly) positive probability to every link.) We report substantial progress towards identifying the validity, methodologies to establish, and limitations of, the FMNE Conjecture.

Details

MFCS Conference 2002 Conference Paper

On Radiocoloring Hierarchically Specified Planar Graphs: PSPACE-Completeness and Approximations

  • Maria I. Andreou
  • Dimitris Fotakis 0001
  • Sotiris E. Nikoletseas
  • Vicky G. Papadopoulou
  • Paul G. Spirakis

Abstract Hierarchical specifications of graphs have been widely used in many important applications, such as VLSI design, parallel programming and software engineering. A well known hierarchical specification model, considered in this work, is that of Lengauer [ 9, 10 ] referred to as L-specifications. In this paper we discuss a restriction on the L-specifications resulting to graphs which we call Well-Separated (WS). This class is characterized by a polynomial time (to the size of the specification of the graph) testable combinatorial property. In this work we study the Radiocoloring Problem (RCP) on WS L-specified hierarchical planar graphs. The optimization version of RCP studied here, consists in assigning colors to the vertices of a graph, such that any two vertices of distance at most two get different colors. The objective here is to minimize the number of colors used. This problem is equivalent to the problem of vertex coloring the square of a graph G, G 2, where G 2 has the same vertex set as G and there is an edge between any two vertices of G 2 if their distance in G is at most 2. We first show that RCP is \( \mathcal{P}\mathcal{S}\mathcal{P}\mathcal{A}\mathcal{C}\mathcal{E} \) -complete for WS L-specified hierarchical planar graphs. Second, we present a polynomial time 3-approximation algorithm as well as a more efficient 4-approximation algorithm for RCP on graphs of this class. We note that, the best currently known approximation ratio for the RCP on ordinary (non-hierarchical) planar graphs of general degree is 2 ([ 6, 1 ]). Note also that the only known results on any kind of coloring problems have been shown for another special kind of hierarchical graphs (unit disk graphs) achieving a 6-approximation solution [ 13 ].

Details

MFCS Conference 2000 Conference Paper

NP-Completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs

  • Dimitris Fotakis 0001
  • Sotiris E. Nikoletseas
  • Vicky G. Papadopoulou
  • Paul G. Spirakis

Abstract The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters exploiting frequency reuse while keeping signal interference to acceptable levels. The FAP is usually modelled by variations of the graph coloring problem. The Radiocoloring (RC) of a graph G( V, E ) is an assignment function Φ: V → IN such that ¦Φ( u )-Φ( v )≥ 2, when u; v are neighbors in G, and ¦Φ( u )-Φ( v )≥1 when the minimum distance of u; v in G is two. The discrete number and the range of frequencies used are called order and span, respectively. The optimization versions of the Radiocoloring Problem (RCP) are to minimize the span or the order. In this paper we prove that the min span RCP is NP-complete for planar graphs. Next, we provide an O( nΔ ) time algorithm (¦V¦ = n ) which obtains a radiocoloring of a planar graph G that approximates the minimum order within a ratio which tends to 2 (where Δ the maximum degree of G ). Finally, we provide a fully polynomial randomized approximation scheme (fpras) for the number of valid radiocolorings of a planar graph G with λ colors, in the case λ ≥ 4λ + 50.

Details

MFCS Conference 1996 Conference Paper

(poly(log log n), poly(log log n))-Restricted Verifiers are Unlikely to Exist for Languages in NP

  • Dimitris Fotakis 0001
  • Paul G. Spirakis

Abstract The aim of this paper is to present a proof of the equivalence of the equalities \(\mathcal{N}\mathcal{P} = \mathcal{P}\mathcal{C}\mathcal{P}\) (log log n, 1) and \(\mathcal{P} = \mathcal{N}\mathcal{P}\). The proof is based on producing long pseudo-random bit strings through random walks on expander graphs. This technique also implies that for any language in \(\mathcal{N}\mathcal{P}\) there exists a restricted verifier using log n + c, c is a constant, random bits. Furthermore, we prove that the equality of classes \(\mathcal{N}\mathcal{P}\) and \(\mathcal{P}\mathcal{C}\mathcal{P}\) (poly(log log n ), poly(log log n )) implies the inclusion of \(\mathcal{N}\mathcal{P}\) in \(\mathcal{D}\mathcal{T}\mathcal{I}\mathcal{M}\mathcal{E}\) ( n poly(log log n ) ). Also, some technical details of the proof of \(\mathcal{N}\mathcal{P} = \mathcal{P}\mathcal{C}\mathcal{P}\) (log n, 1) are used for showing that a certain class of (poly(log log n ), poly(log log n ))-restricted verifiers does not exist for languages in \(\mathcal{N}\mathcal{P}\) unless \(\mathcal{P} = \mathcal{N}\mathcal{P}\).

Details

MFCS Conference 1994 Conference Paper

Hammock-on-Ears Decomposition: A Technique for the Efficient Parallel Solution of Shortest Paths and Other Problems

  • Dimitris J. Kavvadias
  • Grammati E. Pantziou
  • Paul G. Spirakis
  • Christos D. Zaroliagis

Abstract We show how to decompose efficiently in parallel any graph into a number, \(\tilde \gamma\), of outerplanar subgraphs (called hammocks ) satisfying certain separator properties. We achieve this decomposition in O (log n log log n ) time using O(n + m) CREW PRAM processors, for an n -vertex, m -edge graph. This decomposition provides a general framework for solving graph problems efficiently in parallel. Its value is demonstrated by using it to improve previous bounds for shortest paths and related problems in the class of sparse graphs (which includes planar and bounded genus graphs).

Details

FOCS Conference 1994 Conference Paper

Tail Bounds for Occupancy and the Satisfiability Threshold Conjecture

  • Anil Kamath
  • Rajeev Motwani 0001
  • Krishna V. Palem
  • Paul G. Spirakis

The classical occupancy problem is concerned with studying the number of empty bins resulting from a random allocation of m balls to n bins. We provide a series of tail bounds on the distribution of the number of empty bins. These tail bounds should find application in randomized algorithms and probabilistic analysis. Our motivating application is the following well-known conjecture on threshold phenomenon for the satisfiability problem. Consider random 3-SAT formulas with cn clauses over n variables, where each clause is chosen uniformly and independently from the space of all clauses of size 3. It has been conjectured that there is a sharp threshold for satisfiability at c*/spl ap/4. 2. We provide the first non-trivial upper bound on the value of c*, showing that for c>4. 758 a random 3-SAT formula is unsatisfiable with high probability. This result is based on a structural property, possibly of independent interest, whose proof needs several applications of the occupancy tail bounds. >

Details

MFCS Conference 1991 Conference Paper

The Complexity of The Reliable Connectivity Problem

  • Dimitris Kavadias
  • Lefteris M. Kirousis
  • Paul G. Spirakis

Abstract Let G =( V, E ) be a graph together with two distinguished nodes s and t, and suppose that to every node v ∈ V, a nonnegative integer f ( v )≤degree( v ) is assigned. Suppose, moreover, that each node v can cause at most f ( v ) of its incident edges to “fail” (these f ( v ) edges can be arbitrarily chosen). The Reliable Connectivity Problem is to test whether node s remains connected with t with a path of non-failed edges for all possible choices of the failed edges. We first show that the complement of the Reliable Connectivity Problem is NP-complete and that this remains true even if G is restricted to the class of directed and acyclic graphs. However, we show that the problem is in P for directed and acyclic graphs if we assume that the edges caused to fail by each node v are chosen only from the edges incoming to v. Concerning the parallel complexity of this version of the problem, it turns out that it is P-complete. Moreover, approximating the maximum d such that for any choice of failed edges there is a directed path of non-failed edges that starts from s and has length d turns out to be P-complete as well, for any given degree of relative accuracy of the approximation. On the contrary, given that every node v will cause at least f ( v ) incoming edges to fail, the question whether there is a choice of failed edges such that s remains connected with t via non-failed edges turns out to be in NC, even for general graphs.

Details

FOCS Conference 1989 Conference Paper

The Parallel Complexity of the Subgraph Connectivity Problem

  • Lefteris M. Kirousis
  • Maria J. Serna
  • Paul G. Spirakis

It is shown that the problem of testing whether a graph G contains a vertex- (edge-) connected induced subgraph of cardinality k is P-complete for any fixed k>or=3. Moreover, it is shown that approximating within a factor c>1/2 the maximum d for which there is a d-vertex-(d-edge-) connected induced subgraph of G is not in NC, unless P=NC. In contrast, it is known that the problem of finding the Tutte (triconnected) components of G is in NC. On the positive side, it is shown by proving extremal-graph results, that the maximum d for which there is a d-edge-connected induced subgraph of G can be approximated in NC within any factor c >

Details

MFCS Conference 1986 Conference Paper

The Parallel Complexity of Deadlock Detection

  • Paul G. Spirakis

Abstract When serially reusable multiunit resources are shared among many processes, each of which has exclucive control over some resource units, it is possible for deadlocks to happen. The work of Holt, [ Holt, 71b], stated the problem of deadlock detection as a directed multigraph problem. In this paper we examine the possibility of existence of fast parallel algorithms for deadlock detection. Although many graph problems have efficient parallel solutions (in parallel polylogarithic time, by using only a polynomial number of processors), we present strong evidence that this is not the case for the general deadlock detection problem. We show that the problem is complete in P under log-space reductions and thus probably not efficiently parallelizable. Fortunately, when the problem is restricted (e. g. single-unit requests of processes or single-unit resources), then it falls in NC. We present efficient parallel algorithms for the restricted versions of the deadlock detection problem.

Details