Maria J. Serna

SODA Conference 2012 Conference Paper

Approximating fixation probabilities in the generalized Moran process

• Josep Díaz
• Leslie Ann Goldberg
• George B. Mertzios
• David Richerby
• Maria J. Serna
• Paul G. Spirakis

MFCS Conference 2007 Conference Paper

On the Complexity of Game Isomorphism

• Joaquim Gabarró
• Alina García
• Maria J. Serna

Abstract We consider the question of when two games are equivalent and the computational complexity of deciding such a property for strategic games. We introduce three types of isomorphisms depending on which structure of the game is preserved: strict, weak, and local. We show that the computational complexity of the game isomorphism problem depends on the level of succinctness of the description of the input games but it is independent of the way the isomorphism is defined. Utilities or preferences in games can be represented by Turing machines (general form) or tables (explicit form). When the games are given in general form, we show that the game isomorphism problem is equivalent to the circuit isomorphism problem. When the games are given in explicit form, we show that the game isomorphism problem is equivalent to the graph isomorphism problem.

MFCS Conference 2005 Conference Paper

Adversarial Queueing Model for Continuous Network Dynamics

• Maria J. Blesa
• Daniel Calzada
• Antonio Fernández 0001
• Luis López 0003
• Andrés L. Martínez
• Agustín Santos
• Maria J. Serna

Abstract In this paper we start the study of generalizing the Adversarial Queueing Theory aqt model towards a continuous scenario in which the usually assumed synchronicity of the evolution is not required anymore. We consider a model, named continuous AQT ( caqt ), in which packets can have arbitrary lengths, and the network links may have different speeds (or bandwidths) and propagation delays. We show that, in such a general model, having bounded queues implies bounded end-to-end packet delays and vice versa. From the network point of view, we show that networks with directed acyclic topologies are universally stable, i. e. , stable independently of the protocols and the traffic patterns used in it, and that this even holds for traffic patterns that make links to be fully loaded. Concerning packet scheduling protocols, we show that the well-known lis, sis, ftg and nfs protocols remain universally stable in our model. We also show that the caqt model is strictly stronger than the aqt model by presenting scheduling policies that are unstable under the former while they are universally stable under the latter.

MFCS Conference 2005 Conference Paper

Pure Nash Equilibria in Games with a Large Number of Actions

• Carme Àlvarez
• Joaquim Gabarró
• Maria J. Serna

Abstract We study the computational complexity of deciding the existence of a Pure Nash Equilibrium in multi-player strategic games. We address two fundamental questions: how can we represent a game? and how can we represent a game with polynomial pay-off functions? Our results show that the computational complexity of deciding the existence of a pure Nash equilibrium in a strategic game depends on two parameters: the number of players and the size of the sets of strategies. In particular we show that deciding the existence of a Nash equilibrium in a strategic game is NP -complete when the number of players is large and the number of strategies for each player is constant, while the problem is Σ \(^{p}_{\rm 2}\) -complete when the number of players is a constant and the size of the sets of strategies is exponential (with respect to the length of the strategies).

MFCS Conference 2003 Conference Paper

Adversarial Models for Priority-Based Networks

• Carme Àlvarez
• Maria J. Blesa
• Josep Díaz
• Antonio Fernández 0001
• Maria J. Serna

Abstract We propose several variations of the adversarial queueing model to cope with packets that can have different priorities, the priority and variable priority models, and link failures, the failure and reliable models. We address stability issues in the proposed adversarial models. We show that the set of universally stable networks in the adversarial model remains the same in the four introduced models. From the point of view of queueing policies we show that several queueing policies that are universally stable in the adversarial model remain so in the priority, failure and reliable models. However, we show that lis, a universally stable queueing policy in the adversarial model, is not universally stable in any of the other models, and that no greedy queueing policy is universally stable in the variable priority model. Finally we analyze the problem of deciding stability of a given network under a fixed protocol. We provide a characterization of the networks that are stable under fifo and lis in the failure model. This characterization allows us to show that deciding network stability under fifo and lis in the proposed models can be solved in polynomial time.

MFCS Conference 2001 Conference Paper

(H, C, K)-Coloring: Fast, Easy, and Hard Cases

• Josep Díaz
• Maria J. Serna
• Dimitrios M. Thilikos

Abstract We define a variant of the H -coloring problem by fixing the number of preimages of a subset C of the vertices of H, thus allowing parameterization. We provide sufficient conditions to guarantee that the problem can be solved in O(kn + f(k, H)) steps where f is a function depending only on the number k of fixed preimages and the graph H, and in O ( n k+c ) steps where c is a constant independent of k. Finally, we prove that whenever the non parameterized vertices induce in G a graph that is bipartite and loopless the problem is NP-complete.

TCS Journal 1997 Journal Article

Parallel algorithms for the minimum cut and the minimum length tree layout problems

• Josep Díaz
• Alan Gibbons
• Grammati E. Pantziou
• Maria J. Serna
• Paul G. Spirakis
• Jacobo Toran

The minimum cut and minimum length linear arrangement problems usually occur in solving wiring problems and have a lot in common with job sequencing questions. Both problems are NP-complete for general graphs and in P for trees. We present here two parallel algorithms for the CREW PRAM. The first solves the minimum length linear arrangement problem for trees and the second solves the minimum cut arrangement for trees. We prove that the first problem belongs to NC for trees, and the second problem is in NC for bounded degree trees. To the best of our knowledge, these are the first parallel algorithms for the minimum length and the minimum cut linear arrangement problems.

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 >