| Version |
Date |
Utilisateur |
ID du Champ |
Champ |
Difference |
| 4 |
07 Mar 2013 12:33 |
yannis.manoussakis |
184 |
Prerequisite |
| - | master basic notions on graph theory, complexity and algorithms |
+ | Master basic notions on graph theory, complexity and algorithms |
|
| 3 |
07 Mar 2013 12:33 |
yannis.manoussakis |
182 |
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 1: Try to understand the difficulty of these four fundamental graph problems. In particular, see for which families of graphs they remain NP-hard. |
|
| |
|
|
189 |
Collaborations |
| | - Marek Karpinski, Department of Computer Science,University of Bonn,Germany | | - Marek Karpinski, Department of Computer Science,University of Bonn,Germany |
| | and | | and |
| - | Narayanan Poty, Madras Institute of technology, India |
+ | - Narayanan Poty, Madras Institute of technology, India |
|
| 2 |
07 Mar 2013 12:32 |
yannis.manoussakis |
179 |
Subject |
| - | Topological and algorithmic study (NP-completeness, approximability, non-approximability) of edge-colored graphs and their applications. |
+ | Topological and algorithmic study (NP-completeness, approximability, non-approximability) of tropical structures in vertex-colored graphs and their applications to the Web. |
|
| |
|
|
180 |
Abstract |
| - | Recent years there is a great interest on problems in edge (vertex)-colored graphs motivated by both their theoretical interest and applications in various field such molecular biology, Social Sciences VLSI etc. Original problems here correspond to extract subgraphs (for ex. Hamiltonian and Eulerian paths/cycles, spanning trees, connectivity etc.) colored in a specified pattern. In the context, the most natural pattern is that of properly coloring, i.e. adjacent edges/vertices having different colors. Although a large body of algorithmic/mathematical work has already been done on the subject, in the most of these researches the number of colors is restricted to two or if the graphs are restricted to the complete ones. Here we propose to pay attention to complete or general graphs whose edges are colored within any number of colors. |
+ | 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. |
|
| |
|
|
181 |
Context |
| - | Concerning hamiltonicity, finding a properly edge-colored Hamiltonian cycle is trivially NP-complete for general colored graphs and for any number c of colors c>1. However when we restrict ourselves to 2-edge colored complete this problem becomes polynomial, but it remains open for a higher number of colors. A surprising result concerns the complexity of the proper connectivity, i.e. finding proper paths between two given vertices in an edge-colored graph. In fact, while finding one such path turns to a matching problem (thus polynomial), for more than 2 paths the problem becomes NP-Complete. The linkage problem is also NP-complete. Thus it is basic to establish approximation results for such problems. But these connectivity problems remain polynomial for complete or acyclic graphs. The question about proper spanning trees is NP-complete for graphs including the complete ones. But remains polynomial for graphs without proper cycles. Some non-approximability results are also known. |
+ | 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. |
|
| |
|
|
182 |
Work program |
| - | Step 1 : Study approximation algorithms for fundamental problems (mainly hamiltonicity) in edge colored complete graphs whose edges are colored with at least 3 colors. Recall that the complexity of this problem is unknown. Step 2 : Prove our hypothesis that the proper version of the k-linked problem is NP-complete, even for k fixed and dense graphs. If true, establish approximation and non-approximation results. In addition, determine specified families of graphs for which the problem is polynomial. Deal also with the special case edge-colored complete graphsStep 3 : The proper k-connectivity problem is already proved to be NP-Complete for k>2. The same holds for proper spanning trees. Establish approximation algorithms for these problems. |
+ | 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. |
|
| |
|
|
183 |
Objectives |
| - | The most of the obtained efficient results (cycles, paths, trees etc.) concern 2-edge complete graphs. In a first research axis, we wish to see if these efficient results remain polynomial for at least 3 colors. For instance, it is unknown if there is a polynomial algorithm for finding proper Hamiltonian cycles in complete graphs colored with at least 3 colors. While the problem is efficient for 2 colors. In a second axis we wish to study classical problems (spanning trees, linkages, connectivity etc.) with specified color patterns in general edge-colored graphs. The most of them, being expected to be NP-complete, we try to establish approximation or non-approximability results. Also find polynomial algorithms for specified classes of graphs. In another axis, we identify possible applications in biology etc. For instance, a classical open problem in algorithmic molecular biology consists to count the number of distinct proper Eulerian paths in 2-edge colored graphs. |
+ | 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. |
|
| |
|
|
190 |
Year |
|
| |
|
|
191 |
Status |
|
| 1 |
07 Mar 2013 12:24 |
yannis.manoussakis |
191 |
Status |
|