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.