Inria Associated Team CANOE

CANOE

Combinatorial Algorithms for Networking prOblEms

Programme INRIA “Equipes Associées” 2023-2025

Inria Project-Team : COATI Foreign Partner: Universidade Federal do Ceará
Inria d’Université Côte d’Azur
Thème INRIA : Com B		 Country: Brazil
French coordinator Brazilian coordinator
Name, surname Nicolas Nisse Júlio Araújo
Title Chargé de Recherche HC Inria (Research officer) Professor
Institution Project-team COATI, common team
Inria d’Université Côte d’Azur – I3S (CNRS UMR 7271, University Côte d’Azur)		 ParGO Research Group, Department of Mathematics, Federal University of Ceará, Fortaleza, Brazil
Address
INRIA Sophia-Antipolis Méditerranée
2004, route des Lucioles — B.P. 93
06902 Sophia-Antipolis Cedex
France
Departamento de Matemática – bloco 914. Av. Humberto Monte, s/n, Campus do Pici. CEP 60440-900. Fortaleza, CE – Brazil.
URL http://www-sop.inria.fr/members/Nicolas.Nisse/ https://sites.google.com/view/julio-araujo/home

Activity reports

Participants

Documents

Visits in 2023

  • Brazil to France
    • Ana Shirley Silva: 18-29 September
    • Claudia Linhares Sales: 3-13rd December
    • Ana Karolinna Maia: 11-22nd December
    • Nicolas de Almeida Martins: Nov. 2023- August 2024.
  • France to Brazil
    • Nicolas Nisse: 3-29th November
    • Lucas Picasarri-Arrieta: 3-29th November
  • 2nd Fortaleza Workshop on Combinatorics (ForWorC) has been organized by the Brazilian partner (6-10th November 2023).
    Most of Brazilian members as well as N. Nisse and L. Picasarri-Arrieta attended it.
    J. Araujo and N. Nisse were also speakers during the workshop.

    • Nicolas Nisse. Deciding the Erdős-Pósa property in 3-connected digraphs. 6th Nov. 2023
    • Júlio Araújo. On graph convexity parameters in oriented graphs. 8th Nov. 2023

Publications of the Project

Scientific programme and objectives

Context

A graph is a mathematical structure that allows modeling networks in many contexts, from route networks, telecommunication networks, biological networks, neural networks to social networks. There are graph problems arising in each of these domains that are classified as computationally difficult, where the objective is to obtain an efficient algorithm for any graph presented as input. However, studying algorithms for a problem restricted to special graphs can shed light on the problem. This approach consists in assuming that the graph has some special structural property and exploiting this property in the algorithm. Such a structural property defines a class of graphs, for example, trees or planar graphs. The aim is to build an efficient algorithm for a class of graphs, and then explore the ideas used to solve larger and larger classes of graphs or with fewer structural constraints. While a lot of work has been dedicated to the study of structural properties of graphs [CM93,RSST97,RS04,CFK+15,FDHT16], very few results are known concerning directed graphs [Neu82,GHK+16] or hypergraphs [ALNP19] which better model real life networks. For instance, road networks are intrinsically directed and so are many social networks (e.g., Twitter), co-authorship networks correspond to hypergraphs (where each publication corresponds to an hyperedge gathering the co-authors), etc. This project aims at tackling chalenging theoretical open problems in digraphs and/or hypergraphs. The purpose of this project is also to pursue and extend our fruitful collaboration with the ParGO team from Universidade Federal do Ceara (Fortaleza).

Objectives

  • The main goal of this Associate Team is to obtain further progresses in the understanding of structural properties of directed graphs and hypergraphs, in order to use them in the design of efficient algorithms for applications in various networks (e.g., routing, frequency assignment, tasks scheduling in telecommunication networks) and also to better predict their evolution (large scale social networks). We will mainly investigate three complementary research directions. A classical way to design efficient graph algorithms is to use the divide-and-conquer paradigm by decomposing the graphs into smaller instances [CM93,Bod98]. However, no good decompositions are known for directed graphs [GHK+16]. One first direction of
    this project is to investigate possible definitions of such directed graph decompositions and their computations.
  • Graph coloring is a classical graph problem that consists in partitioning the vertex set into few stable sets. The numerous applications (frequency assignment, tasks scheduling and plani cation, etc.) of this problem lead to many variants depending on additional constraints. Many challenging questions remain open in directed graphs (for instance, the analogous of the famous four colors theorem in planar graphs is not known [Neu82]). We will investigate this family of problems in directed graphs.
  • Social networks have mainly been modeled by graphs [ER59,WS98,AB02] while relationships between individuals are often not only binary (edges), but multiple (hyperedges). We are interested in real large social networks such as co-publication network (freely available, e.g., on dblp) and their evolution over time. We aim at designing random models to generate (via simulations) evolving hypergraphs and compare them (and the evolution of their structural properties) with real social networks. The originality of the proposal is to focus on structures (directed graphs, (dynamic) hypergraphs) that have been much less studied than (static) graphs. One challenge here is that we will face very difficult questions (e.g., longstanding open questions) that will require to introduce new or adapt existing theoretical tools (decompositions, temporal graphs, etc.).

Work-program

During the last decades, amazing progresses have been done both in the understanding of structural properties of graphs and in the algorithmic impact that such structures bring (e.g., the famous Graph Minor Theory [RS04], the parameterized complexity framework [CFK+15]). A cornerstone of these fundamental results is the notion of tree-decomposition of graphs [CM93,Bod98]. Roughly, a tree-decomposition of a graph G is a recursive decomposition, in a tree-like structure, of G along its separators. The classical measure of a tree-decomposition is the size of the separators (a.k.a. the treewidth of a graph). Many NP-hard problems can be solved efficiently when restricted to graphs of bounded treewidth [CM93,FDHT16]. However, computing good tree-decompositions remains a challenging question and few is known about directed graphs.

  • The directed treewidth has been proposed as a generalization of treewidth to directed graphs [JRST01,KK15,GHK+16]. Such decompositions are computationally hard to obtain. We want to use integer programming, branch and bound and separation algorithms for computing tree-decompositions [FHL08]. An alternative approach will be to consider other decompositions’ measures (e.g., the diameter of the separators [DG07,DN22]).

Among graph problems, the one that has received the most attention is without doubt the Graph Colouring Problem that asks whether the vertex-set of a graph G can be partitioned in at most k stable sets. For instance, the famous 4-colour Theorem states that any planar graph can be partitioned into four stable sets [RSST97]. However, the case of directed graphs have received much less attention. During the first year, we will focus on the following questions.

  • Orientation of graphs are closely related to digraph colouring. One question is, given a graph, to compute an orientation and a weight of its edges such that any two adjacent vertices have distinct weighted in-degrees (their colours). Trees have been investigating [AGG+20] and we aim at considering larger graph classes [AHL+]. A more general question is to understand, for a given graph G, what are the properties of its possible orientations depending on the structural properties of G.
  • A way to generalize graph proper colouring to digraphs is to say that a k-proper dicolouring of a graph G is a partition of its vertex-set to k acyclic parts [Neu82]. One longstanding open problem is to (dis)prove that any planar digraph can be partitioned into 2 acyclic digraphs. We want to address such a question by studying all proper dicolourings of a digraph through its dicolouring recon guration graph [CHJ09,BB18,BHN+].

The structural properties of social networks impact their behaviour, e.g., the way information (or virus) spreads across them or how communities emerge. We are mainly concerned by two kinds of questions that both rely on the evolution of such networks: the evolution of the communities in the co-authorship networks (we will focus on this question during the first year) and the impact of different lockdown policies on the spread of viruses in large scale social network. We aim at studying them using the recent advances in temporal graphs [MS22] and compare our results with real life networks (either using real data, or via simulations).

  • We will study the evolution of communities in the scientific co-publication network(s). One question behind this study is to better understand the impact of pluri-diciplinary grants on the scientific collaborations. As an example, we will investigate various preferential attachment models [AB02,GNTS22+] and study the evolution of communities and of degrees (number of publications/collaborations) of the nodes (researchers).

As the breadth of the objectives described suggests, the methodology for this project will require a holistic approach, integrating interdependent activities. In addition to the usual activities of the project teams (bibliography, design and analysis of algorithms, computer simulations, organization of seminars, participation to national and international conferences, etc.), we will organize an annual workshop for a better integration of researchers and students from both participating institutions and organize semi-annual activities with high school students for the popularization of science (consolidating the strong involvement of the COATI team in the TERRA NUMERICA project. In particular, we plan to develop new activities to explain the problematics behind the social networks to a large public.)

References

  • [AGG+20] Jiangdong Ai, Stefanie Gerke, Gregory Gutin, Yongtang Shi, and Zhenyu Taoqiu. Proper orientation number of triangle-free bridgeless outerplanar graphs. Journal of Graph Theory, 95(2):256–266, 2020.
  • [AB02] Réka Albert et Albert-László Barabási, Statistical mechanics of complex networks, Reviews of Modern Physics, vol. 74 (1), 2002, p. 47–97
  • [AHL+] Júlio Araújo, Frédéric Havet, Claudia Linhares Sales, Nicolas Nisse, and Karol Suchan. Semi-proper orientations of chordal graphs. In progress.
  • [ALNP19] Chen Avin, Zvi Lotker, Yinon Nahum, David Peleg:
    Random preferential attachment hypergraph. ASONAM 2019: 398-405
  • [BFGR17] Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan:
    Metric Dimension of Bounded Tree-length Graphs. SIAM J. Discret. Math. 31(2): 1217-1243 (2017)
  • [BB18] Marthe Bonamy, Nicolas Bousquet:
    Recoloring graphs via tree decompositions. Eur. J. Comb. 69: 200-213 (2018)
  • [Bod98] Hans L. Bodlaender:
    A Partial k-Arboretum of Graphs with Bounded Treewidth. Theor. Comput. Sci. 209(1-2): 1-45 (1998)
  • [BHN+] Nicolas Bousquet, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta, Amadeus Reinald. Digraph redicolouring. In preparation.
  • [CHJ09] Luis Cereceda, Jan van den Heuvel, Matthew Johnson:
    Mixing 3-colourings in bipartite graphs. Eur. J. Comb. 30(7): 1593-1606 (2009)
  • [CM93] Bruno Courcelle, Mohamed Mosbah:
    Monadic Second-Order Evaluations on Tree-Decomposable Graphs. Theor. Comput. Sci. 109(1\&2): 49-82 (1993)
  • [CFK+15] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
    Parameterized Algorithms. Springer 2015, ISBN 978-3-319-21274-6, pp. 3-555
  • [DN22] Thomas Dissaux, Nicolas Nisse: Pathlength of Outerplanar graphs. To appear in 15th Latin American Theoretical Informatics Symp. (LATIN), Springer, LNCS, 2022.
  • [DG07] Yon Dourisboure, Cyril Gavoille:
    Tree-decompositions with bags of small diameter. Discret. Math. 307(16): 2008-2029 (2007)
  • [ER59] Paul Erdös et Alfred Rényi, On random graphs I, Publicationes Mathematicae, vol. 6, 1959, p. 290-297
  • [FDHT16] Fedor V. Fomin, Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos:
    Bidimensionality. Encyclopedia of Algorithms 2016: 203-207
  • [FHL08] Uriel Feige, M. Hajiaghayi, J. R. Lee: Improved Approximation Algorithms for Minimum Weight Vertex Separators. SIAM J. Comput. 38(2): 629-657, 2008.
  • [GHK+16] Robert Ganian, Petr Hlinen\’y, Joachim Kneis, Daniel Meister, Jan Obdrz\’alek, Peter Rossmanith, Somnath Sikdar:
    Are there any good digraph width measures? J. Comb. Theory, Ser. B 116: 250-286 (2016)
  • [GNTS22+] Frédéric Giroire, Nicolas Nisse, Thibaud Trolliet, Malgorzata Sulkowska:
    Preferential attachment hypergraph with high modularity. accepted to Network Science (2022+)
  • [JRST01] Thor Johnson, Neil Robertson, Paul D. Seymour, and Robin Thomas. Directed tree-width. J. Comb. Theory, Ser. B, 82(1):138–154, 2001.
  • [KK15] Ken-ichi Kawarabayashi and Stephan Kreutzer. The directed grid theorem. In Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC, pages 655–664. ACM, 2015.
  • [KL06] R. Krauthgamer and J. R. Lee. Algorithms on negatively curved spaces. In 47th Annual IEEE Symp. on Foundations of Computer Science (FOCS 2006), pages 119– 132, 2006.
  • [MS22] Andrea Marino, Ana Silva:
    Coloring temporal graphs. J. Comput. Syst. Sci. 123: 171-185 (2022)
  • [Neu82] Victor Neumann-Lara:
    The dichromatic number of a digraph. J. Comb. Theory, Ser. B 33(3): 265-270 (1982)
  • [RSST97] Neil Robertson, Daniel P. Sanders, Paul D. Seymour, Robin Thomas:
    The Four-Colour Theorem. J. Comb. Theory, Ser. B 70(1): 2-44 (1997)
  • [RS04] Neil Robertson, Paul D. Seymour:
    Graph Minors. XX. Wagner’s conjecture. J. Comb. Theory, Ser. B 92(2): 325-357 (2004)
  • [WS98] Duncan J. Watts et Steven H. Strogatz, Collective dynamics of ‘small-world’ networks, Nature, vol. 393, no 6684, 1998, p. 440–442

Comments are closed.