Topological and algorithmic study (NP-completeness, approximability, non-approximability) of tropical structures in vertex-colored graphs and their applications to the Web.
Possible collaborations with :
- Shinya Fujita, Maebashi Institute of Technology, Japan
- Marek Karpinski, Department of Computer Science,University of Bonn,Germany
and
- Narayanan Poty, Madras Institute of technology, India
Abstract
Recent years there is a great interest on problems in vertex-colored graphs motivated by both their theoretical interest and applications in various field such molecular biology, Social Sciences, the Web graph etc. For instance the web graph may be considered as a vertex-colored graph where each color corresponds to the domain (mathematics, physics, chemistry etc) of the content of the page. Original problems here correspond to extract subgraphs (for ex. dominating sets, vertex covers, independent sets, connected components etc.) colored in a specified tropical patterns i.e. each color appears at least ones in the sub-graph under consideration. This is quite new subject, and there are no published results. Here we propose to start studding four basic graph problems, namely, the minimum tropical dominating set, tropical vertex cover, tropical independent set and minimum tropical components for (classic and random) vertex-colored graphs.
Context
Concerning minimum tropical dominating sets, tropical vertex covers and tropical independent sets, the corresponding decision problem is trivially NP-complete for general vertex-colored graphs and for any number c of colors c>1. This follows directly from the fact that the classical (non colored) version of all these problems is well known to be NP-hard. These tropical questions even remain NP-hard when we restrict ourselves to very specific families of vertex-colored graphs (trees, paths etc) and with a number of colors which is a function of the number of vertices. A surprising result concerns the NP-hardness of the tropical dominating set in the case where the graph is restricted to simple path. Concerning the minimum connected component, although its non-colored version is polynomial, the tropical version is NP-hard even in the case of trees. Thus it is basic to establish approximation (or non approximation) results for the above fundamental graph theory problems.
Objectives
In a first research axis, we wish to see if these four fundamental problems (dominating set, vertex cover, independent set and connected component) are polynomial or remain NP-hard for very specific families of graphs (dense, planar, perfect or cubic graphs). In a second axis we wish to establish approximation results within a constant factor (if possible) or prove non-approximability results for general vertex-colored graphs. We are expecting to obtain some better approximation results for specific families of graphs, especially trees or dense graphs. In a third step we will establish some structural results involving sufficient conditions on degrees, number of edges etc and then prove that these results are the best possible. As a last step, we wish to study these problems in the case of random graphs, as they may be used to model the web graph.
Work program
Step 1: Try to understand the difficulty of these four fundamental graph problems. In particular, see for which families of graphs they remain NP-hard.
Step 2 : Study approximation algorithms. Recall that, up to now, no approximation (or non approximation) results are unknown.
Step 3: Prove that there are “good” approximations (i.e., within a constant factor) for trees and a non fixed number of colors. If not true, establish non-approximation results. In addition, determine specified families of graphs for which the problem is polynomial, as for example, dense graphs.
Step 4 : Establish sufficient conditions involving several parameters of graphs (degrees, number of edges, connectivity etc.) guarantying the existence of tropical dominating sets, vertex covers, independent sets and connected components, with bounded number of vertices .
Step 5: Study the above problems in the case of vertex-colored random graphs as these graphs may be used to model the web graph.
Extra information
Prerequisite
Master basic notions on graph theory, complexity and algorithms
Détails
Expected funding
Institutional funding
Status of funding
Expected
Candidates
Utilisateur
yannis.manoussakis
Créé
Lundi 01 mars 2010 11:26:30 CET
dernière modif.
Jeudi 07 mars 2013 12:33:44 CET
Fichiers joints
filename
créé
hits
filesize
Aucun fichier joint à cette fiche
Connexion
Ecole Doctorale Informatique Paris-Sud
Directrice
Nicole Bidoit Assistante
Stéphanie Druetta Conseiller aux thèses
Dominique Gouyou-Beauchamps
ED 427 - Université Paris-Sud
UFR Sciences Orsay
Bat 650 - aile nord - 417
Tel : 01 69 15 63 19
Fax : 01 69 15 63 87
courriel: ed-info à lri.fr