Geodesic
Structure of conflict graphs in constraint alignment problems and algorithms
Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4.

Voir la notice de l'article provenant de la source Episciences

We consider the constrained graph alignment problem which has applications in biological network analysis. Given two input graphs $G_1=(V_1,E_1), G_2=(V_2,E_2)$, a pair of vertex mappings induces an {\it edge conservation} if the vertex pairs are adjacent in their respective graphs. %In general terms The goal is to provide a one-to-one mapping between the vertices of the input graphs in order to maximize edge conservation. However the allowed mappings are restricted since each vertex from $V_1$ (resp. $V_2$) is allowed to be mapped to at most $m_1$ (resp. $m_2$) specified vertices in $V_2$ (resp. $V_1$). Most of results in this paper deal with the case $m_2=1$ which attracted most attention in the related literature. We formulate the problem as a maximum independent set problem in a related {\em conflict graph} and investigate structural properties of this graph in terms of forbidden subgraphs. We are interested, in particular, in excluding certain wheals, fans, cliques or claws (all terms are defined in the paper), which corresponds in excluding certain cycles, paths, cliques or independent sets in the neighborhood of each vertex. Then, we investigate algorithmic consequences of some of these properties, which illustrates the potential of this approach and raises new horizons for further works. In particular this approach allows us to reinterpret a known polynomial case in terms of conflict graph and to improve known approximation and fixed-parameter tractability results through efficiently solving the maximum independent set problem in conflict graphs. Some of our new approximation results involve approximation ratios that are function of the optimal value, in particular its square root; this kind of results cannot be achieved for maximum independent set in general graphs. 
@article{DMTCS_2019_21_4_a9,
     author = {Alkan, Ferhat and B{\i}y{\i}ko\u{g}lu, T\"urker and Demange, Marc and Erten, Cesim},
     title = {Structure of conflict graphs in constraint alignment problems and algorithms},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2019},
     doi = {10.23638/DMTCS-21-4-10},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-10/}
}
TY  - JOUR
AU  - Alkan, Ferhat
AU  - Bıyıkoğlu, Türker
AU  - Demange, Marc
AU  - Erten, Cesim
TI  - Structure of conflict graphs in constraint alignment problems and algorithms
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-10/
DO  - 10.23638/DMTCS-21-4-10
LA  - en
ID  - DMTCS_2019_21_4_a9
ER  - 
%0 Journal Article
%A Alkan, Ferhat
%A Bıyıkoğlu, Türker
%A Demange, Marc
%A Erten, Cesim
%T Structure of conflict graphs in constraint alignment problems and algorithms
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-10/
%R 10.23638/DMTCS-21-4-10
%G en
%F DMTCS_2019_21_4_a9
Alkan, Ferhat; Bıyıkoğlu, Türker; Demange, Marc; Erten, Cesim. Structure of conflict graphs in constraint alignment problems and algorithms. Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4. doi : 10.23638/DMTCS-21-4-10. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-10/

Cité par Sources :