1st research subject (Phd or Postdoc): Algorithmic study of edge-colored graphs and their applications in DNA structures.

 

Recent years there is a great interest  on problems in colored graphs motivated by both their theoretical interest and applications in various fields. In particular, problems arising in molecular biology  are often formulated   using colored graphs, i.e. graphs with colored edges and/or vertices [6]. Given such a graph, original problems correspond to  extracting  subgraphs  such as Hamiltonian and Eulerian paths or cycles colored in a specified pattern. The most natural pattern in such a  context is that of properly coloring, i.e. adjacent edges/vertices having  different colors. Properly colored paths and cycles have  applications in various other fields, as in VLSI for compacting a programmable logical array. Also in social sciences where a color represents a relation between two individuals and  the notion of properly edge colored paths and cycles is  related to the balance  of a graph. Although a large body of work has already been done, in the most of these researches the number of colors is restricted to two. For instance, while it is well known how to find efficiency a properly edge  colored hamiltonian cycle in a 2-edge colored complete graph, it is a long standing question how to find such cycles in complete graphs whose edges are colored by any number of colors [4].  Here we propose to pay attention to complete or general graphs whose edges are colored within any number of colors.

 

Some interesting open problems :

 

Problem 1 [2,4]. Given a c-edge-colored complete graph, c>2, is there any algorithm for finding a properly edge  colored hamiltonian cycle in this graph?

 

Problem 2 [2,4]. Given a c-edge colored complete graph G, c>1, is there any algorithm for finding a properly edge-colored hamiltonian path between two given vertices in G?

 

Problem 3 [5]. Given a c-edge colored graph G, c>1, is there any polynomial algorithm for finding the maximum number of properly edge -colored  edge-disjoint paths between two given vertices in G?

 

Problem 4 [6]. Given a c-edge colored graph G, c>1, is there any algorithm calculating the number of distinct properly edge -colored Eulerian trails in G?

 

 

References

1. L.D. Andersen, Long alternating cycles in properly edge colored complete graphs, Mathematica Scandinavia (1989) 5-14.

2. E. Bampis Y. Manoussakis, et Y. Milis  On the parallel complexity of the alternating hamiltonian cycle problem,  RAIRO on Operations Research 33(4) (1999) 421-437. 

3. M Bankfalvi et Z. Bankfalvi, Alternating hamiltonian circuit in two-colored complete graphs, Theory of graphs, Proceedingsof Colloque Tihany (1968)  11-18

4. A. Benkouar, Y. Manoussakis, V. Paschos, R.Saad  On the complexity of Hamiltonian and Eulerian problems in edge-colored complete graphs,  RAIRO Journal On Operations Research Vol. 30 No 4 (1996) 417-438.

5. Y. Manoussakis, Alternating paths in edge-colored complete graphs,  Discrete Applied Mathematics, 56 (1995) 297-309. 

6. P. Pevzner, Computational Molecular Biology: An Algorithmic Approach, The MIT Press, 2000.

 

 

 

2nd research subject (Phd or Postdoc): Algorthmic study of a non cooperatif security game based on graph models

 

Algorithmic game theory  is an emanation of probabilities and algorithms. It represents an algorthmic resolution of problems related  to the games defined  on given mathematical models (matrix, graph etc.).  It is John Von Neumann who is the father of the theory of the games, by demonstrating in 1928 its cornerstone minimax theorem and by writing in 1944 with O.Morgenstern a book entitled « The theory of the games and the economic behavior ».

 

The main traditional approaches in the domain, concern centralized systems in which the agents cooperate to reach  a common goal. With the arrival of Internet, it seemed necessary to study a new behavior of agents often with contradictory interactions. For instance, a normal user of Internet and a sender of spam are two agents with opposite objectives: the 1st wishes to minimize the number of spams he receives, whereas the 2eme wishes to maximize the number of spams to be sent. The concepts used to model such systems without centralized control, are those of Nash equlibrimum and the Price of anarchy [5].

Among all the possible states of a given game , Nash equlibrimum is defined as a state in which no agent should rather change his strategy. Clearly, more than one  states can represent a Nash equlibrimum. Consequently the obtained solution is not always unique and can lead to more or less good performances. The price of anarchy mesures the quality of the obtained solution.

 

In this study we consider a security game on a network modelised by a graph  G [1]. Such a game involves two kind of players, a set of attackers (viruses, spams etc. ) and a protector player (security software etc.). Attackers use a probability distribution to choose nodes to infect. The protector, again via probality distribution, chooses independently a part of the network (e.g. a subgraph H of G) to protect.  In such a scenario, attackers wish to maximise the number of infected nodes of the network, while, in contrast, the protector wishes to maximise the expected number of cleaned attackers. For this non cooperatif game, Nash equlibria and social costs were studied in the case where the part of the network supervised by the protector is an edge, a path or a set of edges [1-4].

 

Here we propose to generalise the results obtained in [1-4], by considering any subgraph H in given families of graphs  (perfect graphs, bipartite graphs, planar graphs etc).

 

 

References

 

1. M. Mavronicolas, V. Papadopoulou, A. Philippou and P. Spirakis, "A Graph-Theoretic Network Security Game", Proceedings of the First Workshop on Internet and Network Economics (WINE 2005), LNS Springer-Verlag, Hong Kong, December 2005, to appear.

2. M. Mavronicolas, P. Panagopoulou,  and P. Spirakis,  "Cost Sharing Mechanisms for Fair Pricing of Network Usage", Proceedings of the Dagstuhl Seminar on Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar Series 05361), September 2005, to appear

 3. M. Mavronicolas, V. Papadopoulou, A. Philippou and P. Spirakis, "A Network Game with Attacker and Protector Entities", Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), Lecture Notes in Computer Science Springer-Verlag, Sanya, Hainan, China, December 2005, to appear.

 4. R. Elsδsser, M. Gairing, T. Lόcking M. Mavronicolas and B. Monien "A Simple Graph-Theoretic Model for Selfish Restricted Scheduling", Proceedings of the First Workshop on Internet and Network Economics (WINE 2005), LNCS, Springer-Verlag, Hong Kong, December 2005, to appear

5. MJ. Osborne and A. Rubinstein, A course in Game Theory, MIT Press, 1994.