Diana Sans Oublier Ons

Youcef, Nathanaël, Justin, Marek Anne Lydia

Linda

Feu Hiba

Mehdi, Mehdi, Amine, Lamine, Saeed, Lyes, Raja, Louis, Raouia, Pedro Paul-Henri

Sami

Georges

Hossein, Oussama, Manel, Paul Axel Renaud

Mayassa Sonia Avec Qui

Keywords: Graphs, social networks, algorithm, complexity, approximation, community structures, s-clubs, independent 2-cliques

Après avoir écrit une thèse sur les communautés, il fallait que je remercie toutes celles qui ont partitionné mon entourage, durant les trois ans et demi qu'a demandé son écriture.

Je voudrais remercier en tout premier lieu Cristina Bazgan, qui a eu confiance en moi et qui m'a accompagné du début à la fin de cette thèse. Merci beaucoup de m'avoir soutenu, écouté, suivi. Merci pour ta bienveillance, ta confiance et ta présence.

I also thank Janka Chlebíková who welcomed me warmly in Portsmouth. Thank you for your support, your (very) rigorous follow-up, and especially your kindness. 1

Je remercie Ioan Todinca et Michel Habib pour avoir lu attentivement l'ensemble de ma thèse. Merci beaucoup pour toutes vos remarques. Je remercie également les autres membres du jury, Henning Fernau, Rodolphe Giroudeau, Aline Parreau et Yann Vaxès, pour l'intérêt qu'ils ont porté à mes travaux.

Je veux remercier aussi Daniel Vanderpooten pour m'avoir accueilli au sein du Master MODO et de m'avoir accompagné jusqu'à la thèse avec bienveillance.

Je remercie toute l'équipe du LAMSADE au sein de laquelle je me suis senti bien durant toutes mes années de thèse. Vous croiser dans les couloirs chaque jour fut toujours un plaisir.

J'ai une pensée particulière pour Anita Souissi, Stéphane Boucheron et Henning Bruhn-Fujimoto qui ont tous les trois été des professeurs formidables durant mon parcours scolaire et qui ont sans doute contribué indirectement à la réalisation de cette thèse.

Je remercie Clément Dallard, avec qui j'ai eu l'occasion de travailler régulièrement. Merci de m'avoir fait partager ta passion pour le snooker, pour ton amitié et pour ton humour si singulier. Des bisous à Angie. Grazie ad Alessio Petrozziello e Francesca Picariello per aver condiviso tanto buon umore (e buona cucina !) durante il mio soggiorno a Portsmouth. 2 Merci à toi Ian mon clé, qui a supporté avec une grande patience mes cocasseries. Merci d'avoir apporté cette atmosphère si particulière en C605. Si ces années furent le feu, c'est sans doute grâce à toi.

Je tiens également à remercier personnellement mes autres collègues du bureau C605 auxquels je me suis attaché. Khalil, pour ton amitié et toutes ces longues discussions sur tes projets de permaculture au Kirghizistan. Céline, pour ton sourire toujours présent et tes conseils bienveillants. Ioannis, για τιν καλ΄ ı σας διάτηεσι και ειδικά για το ςηιούμορ σας. 4 Boris, bientôt Diamant I, pour toutes ces parties de jeux de société.

Je n'oublie pas bien sûr mes autres collègues qui resteront dans mes souvenirs. Je tiens à remercier Anaëlle, que je connais depuis maintenant cinq ans, pour son rayonnement naturel et son sourire si communicatif. Fabien le vrai

Résumé de la thèse en français

Avec le récent développement de nombreux réseaux sociaux (Facebook, LinkedIn, Twitter...), l'étude de ces réseaux a particulièrement suscité l'intérêt de la communauté scientifique pour des raisons sociales ou économiques [START_REF] Easley | Networks, Crowds, and Markets: Reasoning About a Highly Connected World[END_REF][START_REF] Fortunato | Community detection in graphs[END_REF][START_REF] Newman | Detecting community structure in networks[END_REF]. En particulier, un des enjeux importants dans l'étude des réseaux sociaux est la recherche de communautés, domaine qui a beaucoup été étudié ces dernières années.

La première question qui vient naturellement lorsque l'on parle de détection de communautés est : qu'est-ce qu'une communauté ? La première intuition qui semblerait la plus naturelle est de considérer qu'une communauté est un groupe de personnes qui se connaissent toutes. Dans un graphe, cela correspond à un ensemble de sommets joints deux à deux par une arête. Une telle structure est appelée clique. Trouver une clique d'une certaine taille k est un problème combinatoire très connu et difficile à résoudre. Cependant, un ensemble de sommets dont tous les couples seraient joints par une arête, sauf un couple, ne serait pas considéré comme une communauté. Cette observation pousse naturellement à chercher d'autres définitions qui seraient pertinentes pour décrire une certaine cohésion, sans être aussi restrictive qu'une clique. A partir de là, le choix des contraintes qui décrivent la cohésion d'un ensemble de sommets est très arbitraire, et dépend du type de cohésion que l'on cherche. En ce sens, il n'existe pas de définition absolue pour une "communauté", mais la pertinence de diverses définitions peut être discutée.

Dans cette thèse, nous étudions quatre définitions pour décrire une communauté: les structures en communautés, les communautés, les clubs et les communautés potentielles. Cette dernière définition essaiera d'étendre l'intérêt du domaine à la recherche de groupes de personnes qui ne se connaissent pas, mais dont la cohésion est évaluée par les connaissances communes.

Communautés et structures en communautés (Chapitre 4)

Dans le Chapitre 4, nous étudions les structures en communautés. Une structure en k communautés dans un graphe connexe G = (V, E) est une partition Π = {C 1 , . . . , C k } de V , k ≥ 2, telle que ∀i ∈ {1, . . . , k}, |C i | ≥ 2, et ∀v ∈ C i , ∀C j ∈ Π, j = i, on a :

|d C i (v)| |C i | -1 ≥ |d C j (v)| |C j |
Une structure en k communautés au sens faible dans un graphe connexe G = (V, E) est une partition Π = {C 1 , . . . , C k } de V , k ≥ 2, telle que ∀i ∈ {1, . . . , k}, |C i | ≥ 2, et ∀v ∈ C i , ∀C j ∈ Π, j = i, on a :

|d C i [v]| |C i | ≥ |d C j (v)| |C j |
Nous appelons respectivement ces deux inégalités la condition de proportion et la condition de proportion au sens faible.

Informellement, une structure en k communautés est une partition des sommets en k parties telle que tout sommet a une plus grande proportion de voisins dans sa propre partie que dans toute autre partie. Cette définition nous a semblé pertinente, car elle prend en compte le nombre de connaissances qu'un individu peut avoir dans un groupe, mais aussi la taille du groupe. En effet, un individu n'a pas le même sentiment d'appartenance lorsqu'il connaît 2 personnes parmi 10 plutôt que 2 personnes parmi 100.

Nous nous intéressons alors au problème naturel suivant :

2-Community

Données : Un graphe G = (V, E). Question : Existe-t-il une structure en deux communautés dans G ?

Cette définition n'ayant été introduite que récemment, il existe peu de résultats dans la littérature à propos des structures en communautés. Olsen [START_REF] Olsen | A general view on computing communities[END_REF] a montré qu'étant donné un graphe, une structure en communautés peut toujours être trouvée (sans restriction sur le nombre de communautés) en temps polynomial si le graphe n'est pas une étoile. Plus récemment, Estivill-Castro et al. [START_REF] Estivill-Castro | Hardness and tractability of detecting connected communities[END_REF] ont montré que le problème de décider s'il existe une structure en k communautés, telle que chaque communauté doit être connexe et qu'elles soient toutes de tailles égales, est NP-complet dans les graphes généraux, mais résoluble en temps polynomial dans les arbres. Dans [START_REF] Olsen | A general view on computing communities[END_REF], Olsen a également montré qu'il est NPcomplet de décider s'il existe une structure en communautés dont l'une d'elles contient un ensemble de sommets défini en entrée.

Nous avons étudié le problème de trouver une structure en deux communautés dans un graphe, qui n'est pas une étoile, dans les classes de graphes suivantes :

• Pour les arbres, une structure en deux communautés existe et peut être générée en temps linéaire par un algorithme plus simple que celui donné dans [START_REF] Estivill-Castro | Hardness and tractability of detecting connected communities[END_REF]. Il existe des arbres avec une structure en deux communautés de même taille, mais sans structure en deux communautés connexes de même taille.

• Pour les graphes de degré maximum 3, il existe une structure en deux communautés connexes et celle-ci peut être générée en temps polynomial. De plus, il existe une structure en deux communautés de même taille au sens faible et celle-ci peut être générée en temps polynomial. Il existe des graphes sans structure de deux communautés de même taille. Il existe aussi des graphes ayant une structure en deux communautés de même taille, mais sans structure en deux communautés connexes de même taille au sens faible.

• Pour les graphes de degré minimum |V | -3, les graphes complémentaires de graphes bipartis, les graphes de degré minimum (c-1)•|V | c où c est la taille d'une clique maximale au sens de l'inclusion dans le graphe, une structure en deux communautés connexes existe et peut être générée en temps polynomial.

• Pour les graphes de largeur arborescente bornée, il existe des graphes sans structure en deux communautés de même taille, et décider si une telle structure existe (et si elle existe, la générer) peut être fait en temps polynomial.

Estivill-Castro et al. [START_REF] Estivill-Castro | On connected two communities[END_REF] ont prouvé que le problème de trouver une structure en deux communautés de même taille est NP-difficile dans les graphes généraux. Nous démontrons le même résultat en simplifiant drastiquement la preuve et en démontrant que ce problème est en fait équivalent à celui de trouver une partition en deux parties de même taille, telle que tout sommet a au moins autant de voisins dans sa propre partie que dans l'autre partie. Ce dernier problème a déjà été montré NP-complet [START_REF] Bazgan | The satisfactory partition problem[END_REF].

En ce qui concerne le problème de trouver une structure en deux communautés de même taille au sens faible, la situation est légèrement différente. Tout graphe de degré maximum 3 a une structure en deux communautés de même taille au sens faible, tandis qu'il existe des graphes sans structure en deux communautés de même taille dans la même classe de graphes. En terme de complexité, générer une structure en deux communautés de même taille au sens faible peut être fait en temps polynomial dans les graphes de degré maximum 3, tandis qu'il est NP-difficile d'établir s'il existe une structure en deux communautés de même taille dans les graphes généraux, tout comme sa version au sens faible. Les résultats sont similaires lorsque la connexité des deux communautés est requise.

Par ailleurs, nous avons trouvé des graphes non triviaux dans lesquels il n'existe pas de structure en deux communautés. Cette observation a motivé l'étude d'un nouveau problème lié à 2-Community, que nous étudions dans le Chapitre 5.

Max Community (Chapitre 5)

Etant donné qu'il existe des graphes dans lesquels il n'y a pas de structure en deux communautés, il est intéressant de considérer une relaxation de la définition d'une structure en deux communautés, en acceptant que l'une des deux parties n'ait pas besoin de respecter la condition de proportion. L'autre partie est alors considérée comme une communauté. Ainsi, nous étudions le problème de trouver une communauté de taille maximum:

Max Community Donnée : Un graphe G = (V, E). Résultat : Un ensemble C de taille maximale tel que pour tout sommet v ∈ C,

d C (v) |C|-1 ≥ d V \C (v) |V \C| .
Nous montrons dans le Chapitre 5 que ce problème est NP-complet et APX-difficile, même dans les graphes split. De plus, étant donné un graphe G = (V, E), il est toujours possible de trouver en temps polynomial une communauté de taille au moins |V | 2 , ce qui prouve que le problème est 2-approximable en temps polynomial. Nous donnons également une borne supérieure pour la taille d'une communauté, ce qui permet de légèrement l'améliorer. Ensuite, nous montrons que Max Community est résoluble en temps linéaire dans les graphes cubiques Hamiltoniens si un cycle Hamiltonien est donné en entrée. Enfin, nous montrons qu'il est NP-complet de déterminer si, étant donnés un graphe et un ensemble S de sommets du graphe, il existe une autre communauté incluant S.

Clubs (Chapitre 6)

Comme nous l'avons indiqué précédemment, une communauté peut être vue au premier abord comme une clique dans un graphe. Une relaxation naturelle est de chercher un sous graphe de diamètre restreint: au lieu d'établir que la distance entre toute paire de sommets soit 1, nous acceptons qu'elle soit d'au plus k pour un certain entier k. A cet effet, nous étudions plusieurs problèmes liés à la recherche de sous graphes de diamètre 2 et 3, appelés respectivement 2-clubs et 3-clubs.

Dans le Chapitre 6, nous étudions ainsi les problèmes suivants : k-Partition into s-clubs Données : Un graphe G = (V, E), deux entiers k, s. Question : Existe-t'il une partition {P 1 , P 2 , . . . , P k } de V telle que P i est un s-club, pour tout i ∈ {1, . . . , k} ? s-Club Edges Adding Données : Un graphe G = (V, E), deux entiers s, t. Question : Existe-t'il un ensemble d'arètes E de taille au plus t tel que V est un s-club dans le graphe G = (V, E ∪ E ) ?

Spanning s-club Données : Un graphe G = (V, E), un entier k. Question : Existe-t'il un sous-ensemble d'arètes E ⊂ E de taille au plus k tel que le graphe G = (V, E ) a pour diamètre s ? Nous démontrons que partitionner un graphe en deux 2-clubs est NP-difficile même dans les graphes split. De plus, nous montrons que 2-Club Edges Adding est W [START_REF] Abello | Massive quasi-clique detection[END_REF]-difficile même dans les graphes split. Nous discutons sur l'éventuelle NP-difficulté du problème de Spanning 3-club dans les graphes split. Cette NP-difficulté impliquerait la NP-difficulté de Spanning (2s + 1)-club dans les graphes généraux pour tout entier s ≥ 1. De plus, si Spanning 2-club est NP-difficile, on peut montrer que Spanning s-club est NP-difficile pour tout entier s ≥ 2.

Independent 2-Cliques (Chapitre 7)

Avec le développement récent des sites de rencontre dans lesquels les utilisateurs s'attendent à ne pas connaître les personnes qu'ils vont rencontrer (Meet-up, Couchsurfing...), nous définissons un problème de détection de communautés, dans le but de rapprocher des gens qui ne se connaissent pas a priori, mais qui sont liés par leurs connaissances communes.

Nous définissons un independent 2-clique comme un ensemble de sommets C tels que pour toute paire de sommets dans C, ces deux sommets sont non adjacents mais ont un voisin commun qui n'est pas dans C. Le problème étudié (Max Independent 2-Clique) est celui de trouver, étant donné un graphe, un independent 2-clique de taille maximale.

Max Independent 2-Clique Donnée : Un graphe G = (V, E). Résultat : Un independent 2-clique de taille maximale.

Etant proche du problème de recherche d'un ensemble de sommets deux à deux non adjacents de taille maximum (Max Independent Set), nous comparons la difficulté des deux problèmes selon la classe de graphes dans laquelle ils sont étudiés. La Figure 1 résume ces résultats. Une flèche d'une classe à une autre indique que cette classe contient l'autre. Max Independent 2-Clique est NP-difficile dans la partie hachurée (en haut), résoluble en temps polynomial (en bas). Max Independent Set est NP-difficile dans la partie en pointillé (à gauche) et résoluble en temps polynomial (à droite).

Du point de vue de l'approximation, nous montrons que Max Independent 2-Clique n'est pas n 1--approximable en temps polynomial dans les graphes partout denses et dans les graphes split. De plus, ce problème n'est pas n 1/2--approximable en temps polynomial dans les graphes bipartis et est APX-difficile dans les line graphes.

Introduction

The last decades have been marked by a significant explosion of communications with the developpement of the Internet. This turning point have led to the emergence of plenty of social networks like Facebook, Twitter, Snapchat, LinkdIn, Couchsurfing in which people can connect with each other and share information and messages.

In this way, studies about social networks have become a major stake in many different fields like economy, social science or marketing. In particular, one of the main questions in a social network analysis is to determine if there are communities, how many, and how the social network is organized by those communities.

Detecting communities has a lot of applications. Even before the existence of internet, people investigated problems around communities. In [START_REF] Zachary | An information flow model for conflict and fission in small groups[END_REF], Zachary presented the necessity of detecting communities in a karate club with 34 members, containing 78 pairwise links between members who interacted outside the club. Since a conflict arose between the administrator and the instructor, the club had to be split into two (see Figure 1.1). Many other various applications were investigated like identifying bitcoin users [START_REF] Cazabet | Tracking bitcoin users activity using community detection on a network of weak signals[END_REF] or placing component of an electronic circuit into printed circuit cards [START_REF] Kernighan | An efficient heuristic procedure for partitioning graphs[END_REF]. Nowadays with massive social networks like Facebook, community detection became an even more significant stake with other applications. For instance, Facebook tries to suggest new relationships to its members. More generally, massive online stores like Amazon, or event organizers try to find communities among their users in order to recommend them specific products or information.

Figure 1.1: Zachary's karate club given in [START_REF] Fortunato | Community detection in graphs[END_REF].

The first question you may ask is: "What is a community ?". If the term "community" refers to the intuition of some kind of cohesion in a social network, it is impossible to give a proper definition in absolute. Then, studying community detection is always made under a certain definition that is justified by specific criteria.

The standard structure of social networks is a group of individuals linked by relationships. A natural abstract model for those social network is a graph. A graph is a mathematical object constitued by a set of items called vertices and a set of links that join two vertices called edges.

In order to start with an intuitive way to apprehend a community, one simple definition that can be considered is a group of people in which everybody knows each other. In a graph, it corresponds to a subset of vertices such that any two vertices are linked by an edge. Such subset is called a clique. Looking for such community with the largest size could be a natural problem you may look at when you consider a social network.

Given a graph, finding a clique of maximum size should not be a mathematical problem in theory since it can be sorted by a simple exhaustive research. Indeed, it is sufficient to just consider all possible subsets of vertices, check if all edges occurs in this subset, and at the end, return the clique of maximum size you found. Suppose now that you have a computer able to check if a subset is a clique or not within 0.25 nanoseconds which is as fast as a processor of 4 GHz doing one operation. If you want to study a social network with only 70 members and try to find a clique of maximum size, you would have to check 2 70 subsets, which would require more than 90 centuries to process... This leads to a natural question: is it possible to design an algorithm running in a reasonable time to solve this problem?

Most of computer scientists believe that finding a clique of maximum size is too hard to be solved efficiently (in the sense that it requires too much memory and time running to be solved in a reasonable time). More precisely, they proved that, under the conjecture P =NP, there is no algorithm running in polynomial time solving this problem.

The goal of this thesis is to study several definitions of a community that are relevant for different reasons that we discuss. For each definition, we study different problems around it and discuss their hardness, sometimes regarding specific graph structures. Either we prove that the problem can be solved by an efficient algorithm, or we prove that the problem is NP-hard and we discuss other options to approximate the problem efficiently. Approximation algorithms run in polynomial time and guarantee to output a solution near to the optimal solution by some factor.

The thesis is organized as follows. Chapter 2 gives the basic background in order to understand the content. Chapter 3 gives a state-of-art of several definitions of communities studied in the literature. Those definitions are grouped into two categories depending on the studied problem. First, only one community is considered as a subset of vertices in a graph. On the other hand, a community is described as a part of a partition in which each part is considered as a community. This thesis study four definitions for communities in the Chapters 4, 5, 6, and 7. The Chapters 4 and 5 investigate a similar definition of a community, but under different aspects. In Chapter 4 we consider a partition of the graph into communities (called community structure) such that each member of the graph knows a greater proportion of people in its part than in any other part. In Chapter 5, we investigate the same definition in which we only consider one community: a community is defined as a subset of vertices such that any vertex of the subset is linked by an edge to a greater proportion of vertices in its part than out of its part. The studied problem is to find such subset of maximum size. In Chapter 6, we consider a community as a subset of vertices such that there is a chain of relationship of size at most s between any two members within this subset, for a certain integer s. We call such structure an s-club. We study several problems related to that definition: partitioning a graph into two s-clubs, adding a minimum number of links in order to set the whole graph as an s-club, and removing the maximum number of edges in order to maintain an s-club structure. In Chapter 7, we do not try to study communities but potential communities. In the context of meetup services, we want to form a group of people that do not know each other but are related by another criterion than direct relationship. In this way, we define an independent 2-clique as a subset of vertices such that nobody knows each other, but any two members have a common acquaintance. We study the problem of finding such structure of maximum size. In Chapter 8 we give some conclusions and perspectives for future work. In this chapter, we give the basic background on graph theory, complexity, approximation and parameterized complexity.

Graphs

Basics of graphs

A graph is an ordered pair of sets (V, E) such that E ⊆ V × V .

In this thesis, it is always assumed that we consider a graph G = (V, E). Items of V are called vertices and items of E are called edges. In order to simplify the notations, we always note xy an edge {x, y} ∈ E for any given two vertices x, y of V . Most of the time, we consider that for any graph G = (V, E) and any x ∈ V , xx / ∈ E. Considering an edge xy ∈ E, we call x and y the endpoints of the edge.

All graphs considered in this thesis are finite (in the sense that the number of vertices is finite) and simple (at most one edge exists between two vertices).

A directed graph is a graph in which each edge is ordered. In this case, we note (x, y) the directed edge from the vertex x to the vertex y.

The complement G = (V, E) of a graph G = (V, E) is the graph in which uv ∈ E if and only if uv / ∈ E, for all vertex pairs u, v ∈ V . For any vertex v ∈ V , we say that v is adjacent to another vertex v if vv ∈ E. We call neighborhood of v the set N (v) := {x ∈ V : vx ∈ E}. We call closed neighborhood the set N [v] := N (v) ∪ {v}. The size of a neighborhood of a vertex v is called degree of v and is noted d(v). For any subset H ⊂ V of the graph G, we note N H (v) the set of the neighbors of v in H, and similarly N H [v]

:= N H (v) ∪ {v} and d H (v) := |N H (v)|.
A graph is said to be of maximum (resp. minimum) degree d if and only if any vertex of the graph has degree at most (resp. at least) d. When all vertices have the same degree d, we say that the graph is d-regular. We sometimes call cubic a 3-regular graph.

A graph is said to be complete if for any two vertices x, y ∈ V , xy ∈ E.

A subgraph of G is a graph H = (V (H), E(H)) such that V (H) ⊂ V and E(H) ⊂ E. We say that H is the subgraph of G induced by V (H) if E(H) contains all edges from E with two endpoints in V (H). A proper subgraph of a graph G is a subgraph of G which is not G. A subgraph H is said to be maximal (or inclusion-wise maximal) under a certain property if there is no subgraph H respecting this property such that

H ⊂ H . A spanning subgraph of G is a subgraph H = (V (H), E(H)) of G such that V (H) = V , E(H) ⊂ E, and H is connected. Given a graph G = (V, E), a path is a finite sequence of vertices (v 1 , v 2 , • • • , v p ) of V such that for any i ∈ {1, • • • , p -1}, v i v i+1 ∈ E.
The length of a path is the number of edges involved in the sequence.

The distance between two vertices x, y ∈ V is the length of a shortest path between them.

The diameter of a graph is the maximum distance that can occur between two vertices of the graph.

The A graph is connected when for any two vertices x, y ∈ V , there exist a path between x and y. A connected component of a graph G is an inclusion-wise maximal connected induced subgraph of G.

k th power G k = (V k , E k ) of a graph G = (V, E) is a graph such that V k = V ,
A graph is k-connected if at least k vertices must be removed from the graph to make it disconnected.

A pendant vertex of G is any vertex of degree 1.

Given a graph G = (V, E), a cycle is a path (v 1 , v 2 , • • • , v p ) of V such that v 1 = v p .
Given a cycle, we sometimes call chord an edge from E between two non consecutive vertices in the cycle. The length of a cycle is the number of edges involved in the sequence. A k-cycle is a cycle of length k. We sometimes call triangle a cycle of length 3. An odd cycle is a cycle with an odd length. A Hamiltonian cycle is a cycle such that its sequence contains all vertices of V exactly once.

A partition of V is a set of subsets {V 1 , V 2 , . . . , V p } of V for some integer p such that ∪ p i=1 V i and for any two i, j ∈ {1, 2, . . . p}, i = j, V i ∩V j = ∅. A k-partition of V is a partition of V with k sets. 2-partitions are sometimes called cut. The size of a cut (sometimes called cut size) is the number of edges with one endpoint in each part. Given two vertices x, y of G, an x,y-cut is a 2-partition in which x and y do not belong to the same part. A partition is connected if the subgraphs induced by each part of vertices is connected. A partition is balanced if the sizes of each part differ by at most 1.

Given a partition of V , for any vertex v, we call in-neighbor (resp. out-neighbors) of v any neighbor of v which is in the same part of v (resp. not in the same part of v).

A k-coloration of V is a function f : V → {1, 2, . . . , k} such that for any two vertices x, y ∈ V , if f (x) = f (y) then xy / ∈ E. In the following, we define some graph structures that will appear several times in the thesis.

A star is a connected graph in which all vertices have degree 1 except one vertex that can have any degree.

A clique K is a subset K ⊂ V such that for any two vertices x, y ∈ K, xy ∈ E. We also call triangle a clique with 3 vertices. A biclique is a bipartite graph (see Subsection 2.1.3 for a definition of a bipartite graph) in which for any two vertices x, y from each independent set, xy ∈ E.

An independent set I is a subset I ⊂ V such that for any two vertices x, y

∈ K, xy / ∈ E. A vertex cover V is a subset V ⊂ V such that for for any edge e ∈ E, there exist a vertex v ∈ V such that e contains v. Notice that, given a graph G = (V, E), I ⊂ V is an independent set of G if and only if V \ I is a vertex cover of G.
A dominating set is a subset D of V such that for any vertex v ∈ V , either v ∈ D or there exists a vertex v ∈ D such that vv ∈ E.

Notations

Throughout the thesis, we use several notations that we regroup here. Given a graph G = (V, E), a subset H ⊂ V and two vertices v, w of G:

• G[H] is the subgraph induced by H i.e. the graph G = (H, E ) with E the set of edges between two vertices of H in G.

• G -{v} is an abuse of notation of G[V \ {v}], i.e. the subgraph induced by V \ {v}.

•

H is the complement of H in G, i.e. V \ H. • d(v) is the degree of v. • d H (v) is the number of neighbors of v that belong to H. • d in (v)
is the number of in-neighbors of v, when a partition is given.

• d out (v) is the number of out-neighbors of v, when a partition is given.

• ∆(G) is the maximum degree of a vertex in G.

• d(v, w) is the distance between v and w in G.

• d H (v, w) is the distance between v and w in G[H]. This notation is used when v, w ∈ H.

• K p is a clique with p vertices. K p,m is a biclique constructed with two independent sets respectively of size p and m.

• S p is a star with p vertices.

Graph classes

A graph class G is the set of all graphs respecting a certain property. We define all graph classes we study throughout this thesis.

A graph is a tree if it is connected and does not contain any cycle.

A cactus is a graph in which each edge occurs in at most one cycle.

A bipartite graph is a graph in which the set of vertices can be partitioned into two parts such that the subgraphs induced by each part are independent sets. We denote by K p,m the bipartite graph such that the sizes of the two independent sets are p and m, and each of the p vertices in the first one is adjacent to each of the m vertices in the second one.

A graph is planar if it can be embedded in the plane (drawn with points for vertices and curves for edges) without crossing edges. An equivalent definition given in [START_REF] Kuratowski | Sur le problème des courbes gauches en topologie[END_REF] is that a planar graph does not contain a subgraph that is an expansion (i.e. some edges xy could have been subdivided into two edges xz and zy with an added vertex z) of K 5 or K 3,3 .

A graph is outerplanar if it has a crossing-free embedding in the plane such that all vertices are on the same face. A graph is k-outerplanar if for k = 1, G is outerplanar and for k > 1 the graph has a planar embedding such that if all vertices on the exterior face are deleted, the connected components of the remaining graph are all (k -1)-outerplanar.

A graph G is apex if it contains a vertex v such that G \ {v} is planar. Given a graph H, a H-free graph is a graph not containing H as an induced subgraph.

An interval graph is a graph for which there exists a family of intervals on the real line and a bijection between the vertices of the graph and the intervals of the family in such a way that two vertices are joined by an edge if and only if the intersection of the two corresponding intervals is non-empty.

A graph is a threshold graph if it can be constructed from the empty graph by a sequence of two operations: insertion of an isolated vertex, and insertion of a dominating vertex (i.e., a vertex adjacent to all the other vertices). The original definition is that the graph admits a vertex labeling with positive real numbers, such that two vertices are adjacent if and only if the sum of their labels is at least a given 'threshold' t.

A cograph is a graph that can be generated from the single-vertex graph by (repeated applications of) complementation and vertex-disjoint union. These are precisely the graphs containing no induced paths on four vertices.

A split graph is a graph whose vertex set can be partitioned into two subsets, one inducing an independent set and the other one inducing a clique.

The line graph of a graph G (noted L(G)) is the graph whose vertices represent the edges of G, and two vertices of L(G) are adjacent if and only if the corresponding two edges of G share a vertex.

A graph on n vertices is δ-dense if it has at least δn 2 2 edges and is everywhere-δ-dense if the minimum degree is at least δn.

A family of graphs is dense if there is a constant δ > 0 such that all members of this family are δ-dense.

A family of graphs is everywhere-dense if there is a constant δ > 0 such that all members of this family are everywhere-δ-dense.

Computational complexity

Decision and optimization problems

Given a problem, an instance is the data involved in the problem.

Algorithms. An algorithm is a procedure that takes an instance as an input and gives an output. We distinguish two kinds of algorithms: deterministic algorithms, that have a unique execution and a unique output for each input, and non-deterministic algorithms, that can produce different executions for the same input. The running time of an algorithm is the number of operations that the algorithm uses in the worst case scenario to give an output. We say that the running time is polynomial if the running time can be expressed as a polynomial function on the size of the input. Usually, instead of giving the exact number of operations, we use the big O notation in order to express the general running time.

Decision problems and the class NP.

A decision problem is the data of a set of instances and a question whose answer is yes or no that can be asked for any instance of the set. When we introduce a new decision problem, we will make use of the following standard way to define it: Decision Problem Name Input : An instance. Question : A yes/no question that depends on the input.

NP is the set of all decision problems such that there exists a non-deterministic algorithm solving the problem in polynomial time. Given two decision problems D 1 , D 2 , we say that that D 1 polynomial-time reduces to D 2 if there exists an algorithm that, taking as input any instance x 1 of D 1 , gives in polynomial time an instance x 2 of D 2 such that x 1 is a yes-instance if and only if x 2 is a yes-instance. A decision problem D is NP-hard if any problem of NP polynomial-time reduces to D. If D is an NP-hard problem that belongs to NP, we say that D is NP-complete. As an example, we give the following famous NP-hard problem from Garey and Johnson [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]: Sat Input : A set U of variables, a collection C of clauses over U . Question : Is there a satisfying truth assignment for C? Cook proved in [START_REF] Cook | The complexity of theorem-proving procedures[END_REF] that Sat is NP-hard by proving that for any problem A in NP, there is a polynomial reduction from A to Sat. Most of the time, in order to prove the NP-hardness of a problem, we reduce our problem from an already proved NP-hard problem.

P is the set of all decision problems such that there exists a deterministic algorithm solving the problem in polynomial time. Most of computer scientists believe that P = NP, even though P ⊆ NP.

Optimization problems and the class NPO. An optimization problem is the data of:

• a set of instances.

• for each instance, a set of feasible solutions with a size that is bounded by a polynomial on the size of the instance.

• a goal (either maximization or minimization).

• a cost function that takes an instance and a feasible solution as parameters and output a number (that is computable in polynomial time).

Given an optimization problem, an optimal solution is a feasible solution that fulfils the goal of the problem, i.e. maximizes (or minimizes) the value of the cost function. Given an optimization problem and an instance I of this problem, we denote by |I| the size of I, by opt(I) the value of an optimal solution for I, and by val(I, S) the value of a feasible solution S for I. When we introduce a new optimization problem, we will make use of the following standard way to define it: Optimization Problem Name Input : An instance. Output : An optimal solution.

The link between optimization problems and decision problems is the following. If O is a maximization (resp. minimization) problem then we can define its decision version by introducing a parameter k and the question : "Is there a solution of value greater (resp. smaller) than k ?". We say that an optimization problem is NP-hard if its decision version is NP-hard.

NPO is the set of all optimization problems such that the associated decision problem is in NP. An optimization problem is polynomial-time solvable if there exists an algorithm that computes, for every instance of the problem, an optimal solution with a running time that is polynomial in the size of the instance. PO is the set of all optimization problems that are polynomial-time solvable.

Approximation and approximation-preserving reductions

Approximation. When an optimization problem is NP-hard, it is possible to study the approximation of this problem. The goal is to gives algorithms that run in polynomial time and output a solution which value is closed to the optimum value with a certain ratio called the performance ratio, which gives a guarantee for the quality of the given solution.

The performance ratio (or approximation factor) of a solution S for an instance I is r(I, S) := max val(I,S) opt(I) , opt(I) val(I,S) . The closer the performance ratio is to 1, the closer the value of the solution is to the optimum value. The error of S, denoted by (I, S), is defined as (I, S) := r(I, S) -1.

For a function f , we say that an algorithm is an f (|I|)-approximation, if for every instance I of the problem, it returns a solution S such that r(I, S) ≤ f (|I|) in polynomial time. In this way we can define several classes of optimization.

The class PTAS is the set of optimization problems that allow polynomial-time approximation algorithms such that val(S, I) ≤ (1 + ) • opt(I) for a minimization problem or val(S, I) ≥ (1 -) • opt(I) for a maximization problem, for any > 0 given in input. Such algorithm is called a ptas (for polynomial-time approximation scheme). Usually, the running time of such algorithm is exponential in 1 . The optimization problems from NPO such that a polynomial-time approximation algorithm can be design with a running time that is polynomial in the size of the instance and in 1 form the class FPTAS (See [START_REF] Vazirani | Approximation Algorithms[END_REF]).

The class APX is the set of optimization problems in NPO that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant. In the same way, the class log-APX (resp. poly-APX) is the set of optimization problems in NPO that allow polynomial-time approximation algorithms with approximation ratio bounded by c • log(|I|) (resp. c • p(|I|) with p a polynomial), for some constant c with |I| the size of the instance.

At the end, we can set the following inclusions:

PO ⊆ FPTAS ⊆ PTAS ⊆ APX ⊆ log-APX ⊆ poly-APX ⊆ NPO

Hardness of approximation.

For proofs concerning the non-existence of a ptas, we use an approximation-preserving reduction, called L-reduction, which was introduced by Papadimitriou and Yannakakis in [START_REF] Papadimitriou | Optimization, approximation, and complexity classes[END_REF]. Let A and B be two optimization problems. Then A is said to be L-reducible to B if there are two constants a, b > 0 such that:

• there exists a function, computable in polynomial time, which transforms each instance

I of A to an instance I of B such that opt B (I ) ≤ a • opt A (I),
• there exists a function, computable in polynomial time, which transforms each solution S of I to a solution S of I such that |val(I, S)

-opt A (I)| ≤ b • |val(I , S ) - opt B (I )|.
An optimization problem is APX-hard if every problem of APX L-reduces to that problem. Then, if A is L-reducible to B and A is APX-hard then B is APX-hard.

The notion of an E-reduction (error-preserving reduction) was introduced by Khanna et. al. [START_REF] Khanna | On syntactic versus computational views of approximability[END_REF]. A problem A is called E-reducible to a problem B, if there exist polynomialtime computable functions f and g, and a constant β such that • f maps an instance I of A to an instance I of B such that opt(I) and opt(I ) are related by a polynomial factor, i.e. there exists a polynomial p such that opt(I ) ≤ p(|I|) • opt(I),

• g maps any solution S of I to a solution S of I such that (I, S) ≤ β • (I , S ).

An important property of an E-reduction is that it can be applied uniformly to all levels of approximability; that is, if A is E-reducible to B and B belongs to C then A belongs to C as well, where C is a class of optimization problems with any kind of approximation guarantee (see [START_REF] Khanna | On syntactic versus computational views of approximability[END_REF]).

For more information about approximation algorithms, we recommand [START_REF] Hochbaum | Approximation Algorithms for NP-hard Problems[END_REF][START_REF] Vazirani | Approximation Algorithms[END_REF].

Parameterized complexity

When we have to handle an NP-hard problem, it can be interesting to investigate parameterized complexity. Usually, we always express the running time of an algorithm depending on the size of the instance (in graphs, it is often the number of vertices or edges). The goal of this framework is to express the complexity of a decision problem by another parameter.

In general, a natural parameter to study is the size of a solution.

A parameterized problem is a subset Q ⊂ Σ × N where the first component is a decision problem and the second component is called the parameter of the problem. A lot of parameterized problems that are parameterized by the size k of the solution admit an algorithm with running time bounded by c • |I| k for an instance I and a constant c. As an example, for the problem Clique parameterized by the size of the clique k, deciding if there is a clique of size at least k in a graph G = (V, E) can be easily solved in O(|V | k ) by checking any subset of size k in G. More generally, the set of parameterized problems that allow an algorithm that solves the decision problem with running time O(f (k) • |I| k ) for some computable function f is called XP.

However, it can be even more interesting to design algorithm with a running time that separates the size of the instance by the parameter. In that way, the class FPT contains every parameterized problem Q ⊂ Σ × N for which the question "Does (x, k) belong to Q?" can be decided by an algorithm that runs in f (k) • |x| O (1) time where (x, k) ∈ Σ × N and f is a computable function.

Let Q 1 , Q 2 ⊂ Σ × N be two parameterized problems. We say that Q 1 FPT-reduces to Q 2 if there exists two computable functions f and g and an algorithm that takes as input an instance ( (1) time such that:

x 1 , k 1 ) ∈ Σ × N and outputs a new instance (x 2 , k 2 ) ∈ Σ × N in f (k 1 ) • |x 1 | O
• (x 1 , k 1 ) ∈ Q 1 ⇔ (x 2 , k 2 ) ∈ Q 2 • k 2 ≤ g(k 1 )
Downey and Fellows [START_REF] Downey | Fixed-parameter tractability and completeness II: On completeness for W[1[END_REF] introduced the W -hierarchy as different classes of complexity for parameterized problems. Before defining it, we need first to define preliminary concepts. A boolean circuit C = (V, A) is a directed acyclic graph whose vertices V are called gates. The gates of in-degree 0 are called inputs. There is exactly one gate of out-degree 0 called output. Every gate that is neither an input nor an output is labeled by an element of {or, and, not}. A gate with label not has in-degree exactly one. A gate with in-degree bounded by a constant is said to be small, and otherwise it is called large. The weft of a boolean circuit is the maximum number of large gates on a path from an input to the output. The depth is the maximum number of all gates on a path from an input to the output. A truth assignment for a boolean circuit C is a function that associates the value true or false to each input gates. Given a truth assignment for C, the value of the output can be determined by computing the value of each gate according to their label and the values of the previous vertices. A truth assignment satisfies C if the value of the output gate is true. The weight of a truth assignment is the number of input gates set to true.

A parameterized problem (Q, k) belongs to W [t], for a fixed t > 0, if (Q, k) FPT-reduces to Weft-t Circuit Satisfiability parameterized by k, where the latter problem is defined as follows:

Weft-t Circuit Satisfiability

Input : A boolean circuit C with constant depth and weft at most t, and an integer k. Question : Is there a truth assignment of weight k that satisfies C? A way to prove that a parameterized problem belongs to W [t] is to construct an FPTreduction from this problem to a problem known to be in W [t]. As an example we give an FPT-reduction from the following problem established in [START_REF] Downey | Fixed-parameter tractability and completeness II: On completeness for W[1[END_REF]:

Independent Set

Input : A graph G = (V, E), an integer k. Question : Is there a subset of vertices S ⊂ V such that for any two vertices [START_REF] Downey | Fixed-parameter tractability and completeness II: On completeness for W[1[END_REF]). Independent Set belongs to W [START_REF] Abbas | Clustering bipartite, chordal graphs: Complexity, sequential, parallel algorithms[END_REF].

s 1 , s 2 of S, s 1 s 2 / ∈ E? Theorem 2.1 ([
Proof. We construct an FPT-reduction from Independent Set to Weft-1 Circuit Satisfiability. Let G = (V, E) be a graph as an instance of Independent Set. We construct a boolean circuit C = (V, A) as an instance of Weft-1 Circuit Satisfiability as follows (see Figure 2.1 for an illustration). Introduce |V | gates a i , i ∈ {1, • • • , |V |} of in-degree 0, each gate corresponding to a vertex in G. For each gate a i , introduce a gate b i labeled "not" and add an edge (a i , b i ) in A. For any two vertices v i , v j in V that are not linked by an edge, create a gate c ij labeled "or" and add the edges (b i , c ij ) and (b j , c ij ).

Finally, add a gate d labeled "and" and add the edges (c ij , d) for all c ij . Now notice that since d is the only large gate, the boolean circuit has weft 1 and depth 4. Moreover, notice that there is an independent set of size at least k in G if and only if there is a truth assignment of weight k that satisfies C.

v 1 v 2 v 3 v 4 v 5 a 1 a 2 a 3 a 4 a 5 ¬ ¬ ¬ ¬ ¬ ∨ ∨ ∨ ∨ ∨ ∧ G C → Figure 2.1: The construction of the boolean circuit C from G. A parameterized problem is W [t]-hard if every problem of W [t] FPT-reduces to it. It is W [t]-complete if it is W [t]-hard and belongs to W [t].
At the end, we can set the following inclusions:

P ⊆ FPT ⊆ W[1] ⊆ W[2] • • • ⊆ W[t] • • • ⊆ XP
For more information about parameterized complexity, we recommand [START_REF] Downey | Parameterized complexity[END_REF][START_REF] Niedermeier | Invitation to fixed-parameter algorithms[END_REF].

3

Community detection in graphs : an overview

Community detection in social networks

The recent development of social networks such as Facebook or Linkedin and online meetup services have motivated the investigation of community detection in such networks. A standard abstract model for those networks are graphs in which a community should intuitively describe some cohesion, that often corresponds to some density in a subgraph (see Figure 3.1).

Figure 3.1: A social network partitioned into intuitive communities

It is natural to see that the problem of finding a community in a social network is closely related to the chosen definition of a community. Even if the idea of a community is intuitive, the number of ways to define it is huge. The goal of community detection is to determine, within a given definition of a community, how to find such structure (if it exists) respecting a certain goal (constraints on the size of the community, on the number of communities, on their quality...).

Since no definition can be considered in absolute, the definition is usually chosen depending on which aspect of a community is wanted to be captured.

In the following we give an overview of the definitions of a community that have been studied in the literature. Further information about community detection and more definitions can be found in [START_REF] Fortunato | Community detection in graphs[END_REF][START_REF] Fortunato | Community detection in networks: A user guide[END_REF][START_REF] Lancichinetti | Community detection algorithms: A comparative analysis[END_REF].

Finding a single community

The first intuitive way to define a community is to look for a group of people in which all members of this group know each other. In graphs, it corresponds to a clique.

A classical problem related to finding a community as a subgraph is to look for a subgraph of inclusion-wise maximal size or maximum size. It has been proved in [START_REF] Moon | On cliques in graphs[END_REF] that the number of maximal cliques in a graph with n vertices in bounded by 3 n 3 . It is possible to list all maximal cliques in a graph in polynomial time on the number of vertices, edges and the number of maximal cliques [START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF]. On the other hand, the problem of finding a clique of maximum size is a well known NP-hard problem [START_REF] Karp | Reducibility among Combinatorial Problems[END_REF].

However, considering communities as cliques is too restrictive: a subgraph with all possible internal edges except one would not be considered as a community under this assumption, even if it probably should be in real world social networks. For this reason, other definitions of a community have been studied in order to capture aspects of a community in social networks regarding different features that define a cohesion.

Restrictions on the distance between members

A first way to relax the restrictive condition of a clique is to consider s-cliques. Given a graph, an s-clique is a subset of vertices such that the distance between any pair of vertices is not larger than s. It is easy to see that an 1-clique is a clique. This definition, more flexible than cliques, still has some limitations, deriving from the fact that the distance between two vertices in an s-clique may be ensured by vertices outside of it. In this way, there may be two disturbing consequences. First, the diameter of an s-clique may exceed s, even if the distance between any two vertices of the s-clique is at most s. Second, the subgraph induced by an s-clique may be disconnected, which is not consistent with the notion of cohesion a community should ensure. These problems for s-cliques have been studied in [START_REF] Alba | A graph-theoretic definition of a sociometric clique[END_REF].

In order to take those drawbacks into account, Mokken suggested to introduce the concept of s-club in [START_REF] Mokken | Cliques, clubs and clans[END_REF]. Given a graph, an s-club is a subset of vertices such that the subgraph induced by it has diameter at most s. Notice that any s-club is then included in an s-clique. See Figure 3.2 for an illustration taken from [START_REF] Alba | A graph-theoretic definition of a sociometric clique[END_REF][START_REF] Mokken | Cliques, clubs and clans[END_REF]. Hence 1-clubs are exactly cliques, and every s-club is also an (s + 1)-club by definition. Notice the non-hereditary nature of s-clubs, which makes their behavior different from that of cliques for s ≥ 2: although every subset of a clique is a clique, the same is not true for an s-club. In fact, given a graph G = (V, E) and an s-club S 1 in G, deciding if there exists another s-club S 2 such that S 1 ⊂ S 2 , S 1 = S 2 is NP-hard for every fixed s ≥ 2 [START_REF] Pajouh | On inclusion wise maximal and maximum cardinality k-clubs in graphs[END_REF].

A natural problem with s-clubs is, given a graph G and an integer s, to find an s-club of maximum cardinality. The problem is trivial if G has diameter at most s, but is NP-hard for every fixed s, even on graphs of diameter s + 1 [START_REF] Balasundaram | Novel approaches for analyzing biological networks[END_REF].

In this thesis, we investigate some aspects of s-clubs and prove several properties on problems related to them in Chapter 6.

A survey about various clique relaxation definitions for community detection can be found in [START_REF] Komusiewicz | Multivariate algorithmics for finding cohesive subnetworks[END_REF].

Restrictions on the neighborhood

Instead of relating members by their distance, another way to ensure cohesion within a group of people is to directly deal with the amount of relationships for each members in their group. For instance, we can ask that every vertex has at least a certain amount of neighbors in their group. Seidman introduced the notion of a k-core in [START_REF] Seidman | Network structure and minimum degree[END_REF]. Given a graph G, a subgraph C of G is a k-core if any vertex of C has at least k neighbors in C. Notice that all 1-cores of a graph are all the connected components of it, and trees have no 2-cores. However, since k does not depend on the size of a k-core, the restriction on the number of neighbors inside C for vertices of C does not always ensure high cohesion in the graph, in particular when k is much smaller than the size of C.

Similarly to a k-core, Matsuda et. al. [START_REF] Matsuda | Classifying molecular sequences using a linkage graph with their pairwise similarities[END_REF] introduced the notion of p-quasi complete subgraph, which is a subgraph such that the degree of each vertex is larger than p(k -1), where p is a real number in [0, 1] and k the size of the subgraph. They proved that determining whether a graph includes a 1 2 -quasi complete subgraph of size at least k is NP-complete.

Instead of imposing a certain number of neighbors for each vertex, we can impose a certain amount of non neighbors. Imposing that any vertex of a community should be connected to any other vertex has already been studied under the name of clique, and relaxing this strong condition can be still relevant to find communities. In this way, Seidman and Foster introduced a clique-like structure in [START_REF] Seidman | A graph-theoretic generalization of the clique concept[END_REF] under the notion of k-plex. Given a graph G = (V, E), a subgraph C is defined as a k-plex if any vertex has at least |C| -k neighbors inside C. Notice that cliques are k-plexes for any integer k,

1 ≤ k ≤ |C| -1.
Similarly, it is possible to set constraints on both (i.e. the number of neighbors inside and outside of the community). In this way, an (α, β)-community is defined in [START_REF] Mishra | Finding strongly knit clusters in social networks[END_REF] as a subset of vertices C in which each vertex in C has at least β • |C| neighbors in C (including itself) and each vertex outside of C is linked to at most α.|C| vertices of C, with α < β ≤ 1. Given a graph G = (V, E), the problem of finding a (1 -1

|V | , 1)-community is equivalent to finding a maximal clique in a graph, which is a well known problem we already discussed about. The ((1 -)β, β)-communities, for small , have been studied under the name of quasicliques in [START_REF] Abello | Massive quasi-clique detection[END_REF]. In [START_REF] He | Detecting the structure of social networks using (α,β)-communities[END_REF], they considered a similar definition by considering an (α, β)community as a subset of vertices C in which each vertex in C has at least β neighbors in C and each vertex outside of C has at most α neighbors in C, 0 ≤ α < β. The problem of finding an (α, β)-community of maximum size in a graph has been proved NP-hard in [START_REF] Wang | Extracting the core structure of social networks using (α, β)-communities[END_REF].

Instead of just studying the amount of neighbors inside or outside a community, it is also relevant to compare them and ask that the number of neighbors inside must be larger than the number of neighbors outside of the community in order to ensure the cohesion of the group. In this way, given a graph, an alliance is defined as a set of vertices C such that each vertex of C has at least as many neighbors in C as out of C. This definition has been motivated by the searching links in web graphs and introduced by Flake et al. [START_REF] Flake | Efficient identification of web communities[END_REF], under the name of web community. The term "alliance" has been introduced by Kristiansen et. al. [START_REF] Kristiansen | Alliances in graphs[END_REF] under the same definition.

It is easy to see that, given a graph G and two vertices x, y of G, it is possible to efficiently compute an alliance containing x but not y. Indeed, since of the well know theorem of "max flow/min cut" [START_REF] Ford | Maximal flow through a network[END_REF], we know that the value of the maximum flow through this network equals the minimum value of an (x, y)-cut. Then, considering a minimum (x, y)-cut in G which can be found in polynomial time [START_REF] Ford | Maximal flow through a network[END_REF], notice that any vertex of the set containing x given by the cut must have more neighbors in its own part than in the other part, otherwise the cut would not be of minimum value (see Figure 3.3 as an illustration).

x y showed that the problem of finding an alliance of minimum size in a graph is NP-hard even when restricted to split, chordal or bipartite graphs. In addition, finding an alliance of minimum size such that the alliance is also a dominating set is known to be NP-hard from [START_REF] Cami | On the complexity of finding optimal global alliances[END_REF].

Radicchi et. al. introduced a similar definition in [START_REF] Radicchi | Defining and identifying communities in networks[END_REF] where a community in the strong sense is defined as a set of vertices C such that each vertex of C has strictly more neighbors in C than out of C. They also considered a community in the weak sense by considering subgraphs in which the condition for strong communities must be true only on average, i.e. the sum of the internal degree of each vertex of the community must be greater than the sum of the external degree of each vertex of the community.

In [START_REF] Sigarreta | On the complement graph and defensive k-alliances[END_REF], Sigaretta et. al. studied the variant of defensive k-alliance in which any vertex must have at least k more neighbors in its part than out of its part. A survey and more information about alliances can be found in [START_REF] Fernau | Alliances in graphs: a complexity-theoretic study[END_REF][START_REF] Fernau | A survey on alliances and related parameters in graphs[END_REF].

If the cohesion of a set of vertices can be related to the number of in-neighbors of each vertex of a community, some studies tried to restrict the structure of the neighborhood of each vertex of a community. In this way, one can try to put vertices together according to the role that have by defining role assignments. This concept was in introduced in [START_REF] Everett | Role colouring a graph[END_REF] under the name "role coloring". Given two graphs G = (V G , E G ) and R = (V R , E R ), an Rrole assignment for G is a vertex mapping r : V G → V R such that the neighborhood relation is maintained, i.e. all roles of the image of a vertex appear on the vertex's neighborhood. Formally, for any vertex u ∈ V G , r(N G (u)) = N R (r(u)). From the complexity point of view, several questions can be asked. Given two graph G and R, deciding if there is a role assignment r from G to R is NP-complete [START_REF] Roberts | How hard is it to determine if a graph has a 2-role assignment[END_REF] even if R has 2 vertices. If R is not given in input, deciding if there is an assignment from G to R for some graph R is also NP-complete [START_REF] Fiala | A complete complexity classification of the role assignment problem[END_REF].

Maximizing the relationship density

Another way to express the cohesion within a subset of vertices is to deal with the density of relationships within a community, i.e. the density of edges occurring in a subgraph. A lot of densities, based either on high internal or low external connectivity have been studied in the literature. Given a graph G = (V, E) and a set S of vertices in V considered as a community, we define a quality function f (S) quantifying how community-like is the connectivity of vertices in S. We denote E(S) the set of edges in E with two endpoints in S and cut(S) the set of edges in E with one endpoint in S and one endpoint out of S.

Several definitions for densities can be found in the literature. The following non exhaustive list gives some quality functions that can be found:

• Internal density: f (S) = |E(S)| |S|•(|S|-1
)/2 that is the internal edge density of S [START_REF] Mancoridis | Using automatic clustering to produce high-level system organizations of source code[END_REF].

• Internal-external density:

f (S) = |E(S)| |S|•(|S|-1)/2 -|cut(S)| |S|•(|S|-1
)/2 that is the difference between the internal edge density and the external edge density [START_REF] Mancoridis | Using automatic clustering to produce high-level system organizations of source code[END_REF].

• Edges inside: f (S) = |E(S)| which is the number of connexions in S [START_REF] Corneil | Clustering and domination in perfect graphs[END_REF][START_REF] Feige | The dense k-subgraph problem[END_REF][START_REF] Raman | Triangles, 4-cycles and parameterized (in-)tractability[END_REF].

A variant with weights on edges has been studied in [START_REF] Asahiro | Greedily finding a dense subgraph[END_REF].

• Average degree:

f (S) = 2•|E(S)|
|S| that is the average in-degree of vertices in S [START_REF] Goldberg | Finding a maximum density subgraph[END_REF].

• Fraction over median degree:

f (S) = |{v∈S:d in (v)>d}|

|S|

is the fraction of vertices in S that have internal degree higher than the median value d of d(u) in V [START_REF] Leskovec | Empirical comparison of algorithms for network community detection[END_REF].

• Triangle Participation Ratio: f (S) = |{v∈S:v belongs to a triangle in S}| |S| that is the ratio of vertices belonging to a triangle in S [START_REF] Leskovec | Empirical comparison of algorithms for network community detection[END_REF].

• Conductance: f (S) = |cut(S)| 2•|E(S)|+|cut(S)
| that is the fraction of edge contribution in S that have an endpoint out of S [START_REF] Leskovec | Statistical properties of community structure in large social and information networks[END_REF].

Most of those densities are NP-hard to maximize [START_REF] Schaeffer | Survey: Graph clustering[END_REF]. A comparison of heuristics for finding subsets of maximum density can be found in [START_REF] Leskovec | Empirical comparison of algorithms for network community detection[END_REF][START_REF] Yang | Defining and evaluating network communities based on ground-truth[END_REF].

Other features of communities

Other definitions in the literature tried to capture other features of communities. In [START_REF] Lawler | Cutsets and partitions of hypergraphs[END_REF], the notion of LS set was introduced to capture the idea that any subgraph of an LS set is less relevant as a community than itself. LS sets were first introduced by Luccio et. al. [START_REF] Luccio | On the decomposition of networks in minimally interconnected subnetworks[END_REF] under the name of "minimal groups", and Lawler [START_REF] Lawler | Cutsets and partitions of hypergraphs[END_REF] renamed them LS sets. An LS set is defined as follows. Given a graph G = (V, E), a subset H ⊂ V is an LS set if for any proper subgraph H ⊂ H, the number of edges in E with one endpoint in H and one endpoint in V \ H is always strictly greater than the number of edges with one endpoint in H and one endpoint in V \ H. In this way, any subset contained in an LS set has more connections to the outside of it than the LS set itself. Hence, by being less connected to the rest of the graph, the LS set captures better the notion of cohesion.

Every singleton and the set of vertices V are trivial LS sets, but not interesting in our context. It can be noticed that any vertex of an LS set H has more neighbors in H than in V \ H, which seems an interesting property in the context of community detection, as we seen previously with alliances in Subsection 3.2.2.

An equivalent definition for an LS set given by Seidman in [START_REF] Seidman | LS sets as cohesive subsets of graphs and hypergraphs[END_REF] is that an LS set is a subset of vertices H such that for any proper subset H ⊂ H, the number of edges in E with one endpoint in H and one endpoint in H \ H is strictly greater than the number of edges in E with one endpoint in H and one endpoint in V \ H.

On the other hand, it has been showed in [START_REF] Luccio | On the decomposition of networks in minimally interconnected subnetworks[END_REF] that for any two LS sets H and H , either H ∩ H is empty or one is included in the other. This property gives a good organization of the graph into communities (see Figure 3.4) that can be seen as a hierarchical clustering (see Section 3.3.7). Denoting λ(a, b) the minimum number of edges to remove in order to disconnect two vertices a, b in the graph, Borgatti et. al. showed in [START_REF] Borgatti | LS sets, lambda sets and other cohesive subsets[END_REF] that given a graph G = (V, E) and an LS set H ⊂ V , for any a, b, c ∈ H and d ∈ V \ H, λ(a, b) > λ (c, d). This property highlights the cohesion of an LS set, and has been considered as a generalization of LS sets called lambda sets that has been defined as subsets of vertices satisfying this property [START_REF] Borgatti | LS sets, lambda sets and other cohesive subsets[END_REF].

H 1 H 2 H 3 H 4
Notice that the two definitions are not equivalent. In Figure 3.5, the subset of vertices H is not an LS set. Indeed, considering the proper subset H ⊂ H represented by the gray vertices, there are 4 edges with one endpoint in H and one endpoint in V \ H whereas there are only 2 edges with one endpoint in H and one endpoint in H. On the other hand, H is a lambda set since the minimum number of edges to remove in order to disconnect any vertex of H from any vertex of V \ H is 1, whereas H is 2-connected.

Finding a partition into communities

In this section, we focus on partitioning a graph into several parts that will be considered as communities. In the area of graph partitioning, results may find applications such H Figure 3.5: A graph in which the subset H is a lambda set but not an LS set.

as parallel-computing, VLSI-circuit design, route planning [START_REF] Delling | Customizable route planning[END_REF] and divide-and-conquer algorithms [START_REF] Shmoys | Cut problems and their application to divide-and-conquer[END_REF]. Several methods have been developed in order to find partitions that are relevant to describe a network partitioned into communities, like spectral clustering [START_REF] Bordenave | Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs[END_REF][START_REF] Gulikers | A spectral method for community detection in moderately sparse degree-corrected stochastic block models[END_REF][START_REF] Massoulié | Community detection thresholds and the weak ramanujan property[END_REF]. However, this section focuses on several definitions of a partition into communities in the literature and discusses their relevance in the context of community detection.

It is important to notice that Kleinberg showed in [START_REF] Kleinberg | An impossibility theorem for clustering[END_REF] that no clustering function (i.e. a function that take a graph G = (V, E) and a distance function on V × V as an input and output a partition of V ) can satisfy at the same time three natural properties for a partition into communities. This highlights the fact that there is no unique definition for a partition into communities, and such definition depends on the aspect of cohesion we want to capture.

Maximizing the number of links within the communities

A first natural way to partition a graph into communities is to maximize the number of links within communities. As discussed previously, the most cohesive communities we can found are cliques. Given a graph, deciding if there is a partition into k cliques in a graph is NP-complete from [START_REF] Karp | Reducibility among Combinatorial Problems[END_REF] and even NP-complete on planar cubic graphs [START_REF] Cerioli | Partition into cliques for cubic graphs: Planar case, complexity and approximation[END_REF]. However, finding a partition into k cliques can be done in polynomial time in some classes of graphs. In triangle-free graphs, such partition corresponds obviously to the union of a matching of maximum size and the remaining singletons. Finding a matching of maximum size can be done in polynomial time by solving a flow of maximum value in the adjacency graph. In perfect graphs1 , since the complement of a perfect graph is also a perfect graph [START_REF] Lovász | A characterization of perfect graphs[END_REF], the minimum number of cliques in a partition into clique equals the size of an independent set of maximum size in the graph. Since finding an independent set of maximum size can be done in polynomial time in perfect graphs [START_REF] Grötschel | Stable sets in graphs[END_REF], it is the same result for finding a partition into a minimum number of cliques.

From the approximation point of view, finding a partition into a minimum number of cliques is not n 1--approximable in polynomial time unless P = NP [START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF]. The NP-hardness of this problem and its approximation has also been studied in unit disk graphs2 [START_REF] Cerioli | A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation[END_REF][START_REF] Dumitrescu | Minimum clique partition in unit disk graphs[END_REF][START_REF] Pirwani | A weakly robust PTAS for minimum clique partition in unit disk graphs[END_REF]. On the other hand, there is a polynomial-time 5 4 -approximation algorithm for finding a partition into a minimum number of cliques in graphs of maximum degree 3 [START_REF] Cerioli | Partition into cliques for cubic graphs: Planar case, complexity and approximation[END_REF].

Minimizing the number of links between the communities

Intuitively, a partition into communities should have a lot of links inside each community and few of them between communities. One can then think about partitioning a graph into k communities (for any integer k) by looking for a k-cut of minimum size. This problem has already been studied in the literature, and known to be solvable in polynomial time for k = 2 [START_REF] Ford | Maximal flow through a network[END_REF] and for any integer k [START_REF] Goldschmidt | Polynomial algorithm for the k-cut problem[END_REF]. More generally, if we put weights on edges (that would represent the strength of a relationship), one can look for a k-cut minimizing the sum of all costs of the edges of the cut. In this way, given a graph G = (V, E) and an integer b, a k-way partition is a partition

P = (C 1 , • • • , C k ) of V such that |C i | ≤ b for any i ∈ {1, • • • , k}.
A natural optimization problem is, given a graph G = (V, E), to find a k-way partition P of V minimizing the total cost of all edges having the two endpoints in different parts of P . It has been proved in [START_REF] Garey | Some simplified NP-complete graph problems[END_REF] that this problem is NP-hard, even for 2way partitions with b = |V | 2 . However, this problem and some variants have been widely studied and a lot of heuristic algorithms have been designed to solve it. An heuristic has been suggested for general k in [START_REF] Kernighan | An efficient heuristic procedure for partitioning graphs[END_REF] and for k = 2 in [START_REF] Cheng | An improved two-way partitioning algorithm with stable performance[END_REF]. For general k and b = |V | k , heuristics have been suggested in [START_REF] Choe | A k-way graph partitioning algorithm based on clustering by eigenvector[END_REF][START_REF] Karypis | Multilevel k-way partitioning scheme for irregular graphs[END_REF]. A generalization with weights on vertices (the size of a subset is then the sum of the weights of its vertices) has been studied in [START_REF] Hendrickson | A multi-level algorithm for partitioning graphs[END_REF] for b = |V | k .

Imposing a certain neighborhood for members of communities

Similarly to Subsection 3.2.2, another aspect of communities is that each people should have more relationships in their community than out of it. In this way, we can design partitions into communities such that each vertex should have a certain amount of people they know in their own part rather than out of their part. Gerber and Kobler introduced in [START_REF] Gerber | Partitioning a graph to satisfy all vertices[END_REF][START_REF] Gerber | Algorithmic approach to the satisfactory graph partitioning problem[END_REF] the problem of deciding if a given graph G has a vertex partition into two nonempty parts such that each vertex has at least as many neighbors in its part as in the other part. Given a graph G, we say that G is partitionable if G has such partition. Some graphs are not partitionable, like complete graphs, stars, and complete bipartite graphs with at least one of the two vertex sets having odd size. On the other hand some other graphs are easily partitionable: cycles of length at least 4, trees which are not stars, and disconnected graphs.

Bazgan et. al. proved in [START_REF] Bazgan | The satisfactory partition problem[END_REF] that the problem is NP-complete and polynomially equivalent to its balanced variant in which the partition is requested to be balanced (i.e. both sets are requested to have the same size). The variant of finding a partition into two nonempty parts such that each vertex has at most as many neighbors in its part as in the other part has also been proved NP-complete in [START_REF] Bazgan | Approximation of satisfactory bisection problems[END_REF].

The previous definition of Gerber and Kobler gives a simple and natural way to define a partition into two communities. However, it could be more relevant to consider a condition involving the size of each part. In this way, Olsen [START_REF] Olsen | A general view on computing communities[END_REF] introduced the notion of community structures. A community structure is a partition of the vertex set into several parts such that for each vertex, the ratio between the number of neighbors in its own part and the size of its part (excluding the vertex itself) must be at least as large as the ratio between the number of neighbors in any other part and the size of this part. Informally, if someone belongs to a community structure, then he knows a greater proportion of his group than in any other group. In Figure 3.6, the white and black vertices form a satisfactory partition. However, the vertex x know only 1 5 of its group whereas it knows half of the other group. It seems legit to consider that this member should not be happy to belong to the left community.

x Figure 3.6: The black and white vertices form a satisfactory partition, but is not a community structure This definition has been introduced very recently. Consequently, few results have been discovered. In Chapter 4, we investigate this definition further and prove that a community structure with two parts can be found in polynomial-time in some graph classes. We also investigate the problem of finding a community structure into two parts with the additional constraint of obtaining a balanced partition, i.e. a partition in which both parts are equal sized.

Ensuring stability

First introduced in social psychology in [START_REF] Heider | Attitudes and cognitive organization[END_REF] by Heider, structural balance was defined in graphs theory by Cartwright and Harary in [START_REF] Cartwright | Structural balance: A generalization of Heider's theory[END_REF]. We consider a graph as a social network and all edges are labeled by "+" or "-", indicating if two members of the social network are friends or enemies. Such graph is called a signed graph.

The crucial idea with structural balance is the following. When we look at sets of three people at a time knowing each other (that we call a triangle), some configurations of +'s and -'s are socially and psychologically more stable than others, in the sense that the situation is unlikely to change in the future. In particular, there are four distinct ways (up to symmetry) to label the three edges among those three people with +'s and -'s, see Figure 3.7. Within the four possible configurations, we distinguish two stable situations. A triangle having three "+" is a very stable situation: all three people are mutual friends (Case A). A triangle having only one "+" is also a stable situation since a group of two friends have a common enemy (Case C).

+ + + - + + - - + - - - Case A Case B Case C Case D
The other two possible labelings of the triangle introduce some amount of psychological stress or instability into the relationships. A triangle with two "+" and one "-" (Case B) corresponds to a situation in which a person have two friends who do not get along with each other. This situation is unstable since it pushes that person to choose one side and become an enemy of the other one, or could also push the two enemies to become friends. Finally, if the triangle has only "-", two of the three people could be motivated to team up against the third one, turning one of the three edge labels to a "+". Now, a signed graph is said to be balanced (resp. weakly balanced) if it does not contain any triangle of case B and D (resp. case B). Such property ensures that the social network is stable in the sense that relationships are unlikely to change in the future. Checking if a graph is balanced can be useful in political contexts: by looking at the relationships between countries or populations, it is interesting to figure if some diplomatic tensions might appear or not. An appealing example of the evolution of alliances before World War I can be found in [START_REF] Antal | Dynamics of social balance on networks[END_REF].

It is interesting to notice that a complete signed graph is balanced (resp. weakly balanced) if and only if the graph can be partitioned into two parts (resp. a certain number of parts) such that any edge with two endpoints in the same parts are labeled "+" and any edge with each endpoint in different parts are labeled "-" [START_REF] Cartwright | Structural balance: A generalization of Heider's theory[END_REF][START_REF] Harary | On the notion of balance of a signed graph[END_REF]. If the graph is not complete, then the graph is balanced if and only if it contains no odd cycle labeled "-" [START_REF] Cartwright | Structural balance: A generalization of Heider's theory[END_REF][START_REF] Harary | On the notion of balance of a signed graph[END_REF].

On the other hand, checking if a graph can be partitioned into parts such that any edge with two endpoints in the same parts are labeled "+" and any edge with each endpoint in different parts are labeled "-" can be done easily in polynomial time: any pair of vertices x, y with an edge labeled "+" linking them can be merged into one vertex w preserving the original edges with the labels (i.e. for any edge xz or yz in the graph, we add the edge zw preserving the label). If an edge has two labels, then the graph is not partitionable. If not, the end of the editing will lead to a graph with only edges with a label "-" and the partition will be given by the merging.

The balanced property gives a good indicator of the stableness of a social network and gives a good partition into communities.

Evaluating the quality of a partition

Similarly to Subsection 3.2.3, we can design quality function to evaluate how relevant is a partition to reveal a community structure. The most famous one is modularity that has been a major measure in community detection and has been used in many works to evaluate the quality of partitions into communities [START_REF] Barber | Modularity and community detection in bipartite networks[END_REF][START_REF] Blondel | Fast unfolding of communities in large networks[END_REF][START_REF] Duch | Community detection in complex networks using extremal optimization[END_REF].

The general idea of modularity is to assume that if the number of edges between vertices in a part is higher than what we would expect on the basis of random chance, then it would constitutes evidence of meaningful community structure. On the other hand, if the number of edges between groups is less than what we expect by chance, then it is reasonable to conclude that some structure is worth of interest.

Newman and Girvan [START_REF] Newman | Finding and evaluating community structure in networks[END_REF] defined modularity, based on a previous measure proposed by Newman [130]. Modularity is defined as the fraction of the edges in the network that connect vertices within their community minus the expected value of the same quantity in a network with the same community divisions but edges are distributed randomly (preserving the degree of each vertex).

Optimizing the latter version of modularity has been proved NP-hard in [START_REF] Brandes | On finding graph clusterings with maximum modularity[END_REF]. Heuristics have been studied in the literature in order to give a partition with a good modularity [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF][START_REF] Cafieri | Improving heuristics for network modularity maximization using an exact algorithm[END_REF].

Overlapping partitions into communities

As we discussed before, finding a partition into communities is useful in lots of contexts like VLSI-circuits. However, regarding real world social network, asking for a partition may sometimes appear too restrictive. Indeed, some people might belong to several communities: it seems natural that some people have relationships with different groups of interest. In this way, given a graph G = (V, E), we define an overlapping partition as a set S = {S i } p i=1 of subsets of V such that ∪ p i=1 S i = V . Contrary to regular partitions, we allow that S i ∩ S j = ∅ for some i, j.

A first natural way to define an overlapping partition into communities is to ask for an overlapping partition into cliques, also called clique cover. However, the problem of finding a clique cover of size k is equivalent to finding a partition into k cliques: given a graph, it is easy to see that any clique partition is also a clique cover, and any clique cover of size k can be easily transformed into a partition into k clique by choosing arbitrarily only one set to belong to for any vertex that is in multiple parts.

On the other hand, one could argue that two cliques of size k sharing k-1 vertices should not be considered as two distinct communities. An easy solution consists in considering that two such sets should belong to a unique community. In this way, we can set that two cliques of size k are said to be adjacent if they share k -1 vertices. For a given integer k, This definition has many applications, like in identification of protein communities involved in cancer metastasis [START_REF] Jonsson | Global topological features of cancer proteins in the human interactome[END_REF][START_REF] Jonsson | Cluster analysis of networks generated through homology: automatic identification of important protein communities involved in cancer metastasis[END_REF] and studies of social networks [START_REF] González | Community structure and ethnic preferences in school friendship networks[END_REF][START_REF] Palla | Quantifying social group evolution[END_REF].

a chain of adjacency (C 1 , • • • , C p )
Another way to define overlapping partition into communities is to partition the edges. In [START_REF] Evans | Line graphs, link partitions, and overlapping communities[END_REF], Evans and Lambiotte investigated constructing a partition of the vertices of the line graph of the original graph. In this way, a partition of the line graph gives an overlapping partition of the vertices in the original graph, allowing vertices to belong to several communities. Then, such partition can be searched according to a certain criterion as it is discussed in Section 3.3. In [START_REF] Ahn | Link communities reveal multiscale complexity in networks[END_REF], edge partition is used via hierarchical clustering for community detection applied in biological and social networks.

A specific state-of-art about overlapping partition into communities can be found in [START_REF] Xie | Overlapping community detection in networks: The state-of-the-art and comparative study[END_REF].

Finding a hierarchical clustering of communities

Another approach consists in constructing a hierarchical clustering, which gives another organization of a networks into communities. Given a graph G = (V, E), a hierarchical clustering is a set S of subsets of V such that V ∈ S and ∀s 1 , s 2 ∈ S, s 1 ⊂ s 2 or s 2 ⊂ s 1 or s 1 ∩ s 2 = ∅. This gives an organization of the vertices of G into communities, each set of S being considered as a community.

In order to express the hierarchy in a more clear way, we can define a hierarchical clustering in an equivalent way [START_REF] Brahim | Citations among blogs in a hierarchy of communities: Method and case study[END_REF]: Given a graph G = (V, E), and a community partition

P = {C 1 , C 2 , • • • , C } of V , a sub-partition P = {C 1 , C 2 , • • • , C m } of P is a partition of V such that ∀C i ∈ P , ∃C j ∈ P such that C i ⊆ C j . A hierarchical community structure of G is defined as a series of partitions P k , P k-1 , • • • , P 2 , P 1 , P 0 with P 0 = V and P k = {v}, v ∈ V such that P i is a sub-partition of P i-1 for any i ∈ {1, • • • , k}.
Given a partition P i , we can define i as the level of the partition P i within the global tree of communities with (k + 1) levels.

Such hierarchy can be illustrated by a dendrogram. Again, several legit criteria can be considered in order to construct this hierarchical clustering. A dendrogram can be used to visualize the final hierarchical clustering: any horizontal line gives a partition of the graph (See Figure 3.9 as an illustration given in [START_REF] Puig-Centelles | Surveying the identification of communities[END_REF]). Hierarchical clustering finds applications in bioinformatics and data analysis [START_REF] Everitt | Cluster analysis[END_REF]. A very famous way to define a hierarchical clustering that describes a network into communities is the algorithm of Newman and Girvan [START_REF] Girvan | Community structure in social and biological networks[END_REF] based on edge betweenness. Firstly, the notion of betweenness has been proposed by Freeman [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF]. He defined the betweenness centrality of a vertex v as the number of shortest paths between any two vertices except v that contain v. This gives an indication of the influence of a vertex over the flow of information between other vertices. This notion is particularly relevant when information flow over a network primarily follows the shortest available path. In a similar way, Newman and Girvan proposed to introduce the notion of edge-betweenness [START_REF] Girvan | Community structure in social and biological networks[END_REF]. The edge-betweenness of an edge is defined as the number of shortest paths between any two vertices that contains it. If a network contains groups of people that are connected by a small amount of edges, then all shortest paths between those different groups must go along one of these few edges that will have then a high edge-betweenness (see Figure 3.10). In [START_REF] Newman | Finding and evaluating community structure in networks[END_REF], an efficient algorithm is proposed that consists in computing the betweenness of all edges first, and then repeating the two following steps in order to reveal a hierarchical clustering of the graph:

• Remove the edge with maximum edge-betweenness

• Compute again the edge-betweenness of all edges Each step of the algorithm gives a partition of the graph into communities. Its final output is a hierarchical clustering containing all partitions given at each step of the algorithm.

On the other hand, it is also possible to describe a network of communities with a hierarchical clustering by using other features. As a first example, a method has been developed using random walk that is called walktrap clustering. It consists in assuming that a random walk starting from a vertex tends to stay in the community it belongs to. If we do a random walk starting from a vertex v, then the probability to reach a neighbor is p = 1 d(v) , and then it is possible to compute the probability to reach a vertex j from a vertex i after k steps. Then we consider that two vertices are close if they have a similar probability to reach other vertices by a random walk of length k. The hierarchical clustering is made by first considering singletons communities, and then regrouping vertices that have the smallest distance between them, and compute again the distances. This way of describing communities has been studied in [START_REF] Gaume | Balades aléatoires dans les petits mondes lexicaux[END_REF][START_REF] Jespersen | Relaxation properties of small-world networks[END_REF][START_REF] Pons | Computing Communities in Large Networks Using Random Walks[END_REF][START_REF] Zhou | Network brownian motion: A new method to measure vertex-vertex proximity and to identify communities and subcommunities[END_REF], and has been used in order to study the similarity of words with applications in web navigation [START_REF] Gaume | Balades aléatoires dans les petits mondes lexicaux[END_REF] or diffusion processes in small-world networks3 [START_REF] Jespersen | Relaxation properties of small-world networks[END_REF].

As a second example, we can consider that members of a network should be in the same community if they share the same neighborhood. Given a graph G = (V, E), a module is a set of vertices M ⊂ V such that for any two vertices x, y ∈ M , N (x) \ M = N (y) \ M . The concept of module has been introduced by Gallai in [START_REF] Gallai | Transitiv orientierbare graphen[END_REF]. A strong module is a module that does not strictly overlap any other module. A graph is said to be prime if the only modules are the empty set, the set of all vertices and the singletons. Notice that given a graph G = (V, E), if G is disconnected then all connected components of G are strong modules. In the same way, if G is disconnected, then then all connected components of G are strong modules.

If both G and G are connected, then Gallai showed in [START_REF] Gallai | Transitiv orientierbare graphen[END_REF] that inclusion-wise maximal modules of G define a partition P of V which is called a modular partition. The quotient graph of G, in which each module of P is associated with one vertex, is prime.

Recursively, for each subgraph

G[M ] induced by a module M ∈ P , either G[M ] (resp. G[M ]
) is disconnected and thus can be partitioned into strong modules that are the connected components of G[M ] (resp. G[M ]), or G has a modular partition as seen before.

This recursion defines a modular decomposition that is a hierarchical clustering in which each partition is a partition of V into strong modules. Such hierarchical clustering can be represented by a dendrogram, called a modular decomposition tree. This tree is rooted by the set of vertices and all singletons are leaves.

A modular decomposition can be found in linear time [START_REF] Cournier | A new linear algorithm for modular decomposition[END_REF]. A survey about modular decomposition can be found in [START_REF] Habib | A survey of the algorithmic aspects of modular decomposition[END_REF]. The content of this chapter is based on the following papers [START_REF] Bazgan | Family of graphs without 2-community structure[END_REF][START_REF] Bazgan | New insight into 2-community structures in graphs with applications in social networks[END_REF][START_REF] Bazgan | Structural and algorithmic properties of 2-community structures[END_REF]:

O C.

Introduction

In this chapter, we study the structural and complexity problems related to the recent definition of a community structure in graphs as defined in [START_REF] Estivill-Castro | On connected two communities[END_REF][START_REF] Estivill-Castro | Hardness and tractability of detecting connected communities[END_REF][START_REF] Olsen | A general view on computing communities[END_REF]. This definition reflects closeness between members of a community taking into account the number of neighbors of each member and the size of the communities. This new approach for communities is supported by the practical experiments showing the importance of capturing the sizes of communities for a better description of their properties [START_REF] Olsen | A general view on computing communities[END_REF].

Informally, a community structure in a graph is a partition of the vertex set such that each vertex has a greater proportion of neighbors in its part than in any other part. In this chapter, we focus on a partition with the restriction of outputting a community structure with two communities where the problems are already appealing. The presented techniques may offer some possibilities for an extension to a larger required number of communities.

We also introduce the concept of weak community structure in which the vertex itself contributes to the proportion of neighbors in its part. The ratio condition in the latter definition becomes weaker, but it reflects the reasonable requirement that each member should be considered as a part of its own community. Even if there are minor differences between the definitions, the structural and complexity results for the two problems are very different as it is presented in this paper. Both definitions are relevant to describe the community structures, the choice depends on the suitability of the model.

We also study the 2-community problems with additional constraints such as connectivity or equality of sizes for both parts (balanced partition). The connectivity request corresponds to the essential condition that each member in the community should 'indirectly know' all members in its own community, where the 'indirectly know' relation corresponds to a path between two vertices in the graph. The study of balanced communities is motivated by the practical interest for equal size of the communities. In general, the balanced graph partitions are well studied, e.g. due to its applications in the divideand-conquer algorithms, see e.g. [START_REF] Chlebíková | Approximating the maximally balanced connected partition problem in graphs[END_REF]. In the balanced partition problem, which can be seen as a generalization of the bisection problem to any given number of parts, the goal is to minimize the number of edges between partitions. It is known that the problem cannot be approximated within any finite factor in polynomial time in general graphs and it remains APX-hard even on trees of constant maximum degree [START_REF] Feldmann | Balanced partitions of trees and applications[END_REF]. It demonstrates that some graph partitions problems that are related to e.g. balanced communities are hard to solve even for restricted graph classes and indicates hardness of various problems related to a community structure too. Hence all positive results in community structure problems would be important to get better understanding of the differences between community and partition problems.

Furthermore, a community structure is in fact a graph partition with a restricted num-ber of edges between parts, therefore the new results for communities may find applications in the areas similar to a graph partition such as parallel-computing, VLSI-circuit design, route planning [START_REF] Delling | Customizable route planning[END_REF] and divide-and-conquer algorithms [START_REF] Shmoys | Cut problems and their application to divide-and-conquer[END_REF].

There are only a few results related to our definition of a community structure. Olsen [START_REF] Olsen | A general view on computing communities[END_REF] proved that a community structure (without the condition on the exact number of communities) can be found in polynomial time in any graph with at least 4 vertices, except a star. Recently, Estivill-Castro et al. [START_REF] Estivill-Castro | Hardness and tractability of detecting connected communities[END_REF] claimed that the problem to find a k-community structure with restriction to all communities to be connected and equal size is NP-complete in general graphs, but polynomially solvable in trees. In [START_REF] Olsen | A general view on computing communities[END_REF] Olsen also proved that it is NP-complete to decide, whether there is a community structure in a graph in which a given set of vertices is included in a community. It is interesting to see that the problem of finding a community structure has been seen as a fractional hedonic game problem in [START_REF] Aziz | Fractional hedonic games[END_REF].

The chapter is structured as follows. In Section 4.2 we introduce formally some notations and definitions of the studied problems and give some general observations about community structures. In Section 4.3 we show that in some well-studied graph classes a 2-community structure always exists and can be found in polynomial time, even with additional request for connectivity in both parts. In Section 4.4 we focus on the balanced 2-community structure and present the structural and algorithmic results in general graphs and some graph classes. Conclusions and open problems are provided in Section 4.6.

Preliminaries

In this section, we introduce definitions related to community structures and the related problems. Some general observations are also given in order to discuss the problem and give a better understanding of the concept of community structures.

k-community structures

We introduce Olsen's definition of a k-community structure from [START_REF] Olsen | A general view on computing communities[END_REF].

Definition 4.1. A k-community structure for a connected graph G = (V, E) is a partition Π = {C 1 , . . . , C k } of V , k ≥ 2, such that ∀i ∈ {1, . . . , k}, |C i | ≥ 2, and ∀v ∈ C i , ∀C j ∈ Π, j = i, the following holds: |N C i (v)| |C i | -1 ≥ |N C j (v)| |C j |
The latter inequality will be called the proportion condition all along this chapter for easier reading.

In a more general sense, a community structure is a k-community structure for some integer k. The concept of community structure and the proportion condition of Definition 4.1 are quite intuitive to understand. As explained in the introduction, a community structure corresponds to a partition of the vertex set such that each vertex has a greater proportion of neighbors in its part than in any other part. See On the other hand, the proportion condition of the definition of a community structure can be relaxed. Indeed, it may have sense to consider that a member of a community considers itself as a part of his group. In this way, we define weak k-community structures as follows:

Definition 4.2. A weak k-community structure for a connected graph G = (V, E) is a partition Π = {C 1 , . . . , C k } of V , k ≥ 2, such that ∀i ∈ {1, . . . , k}, |C i | ≥ 2, and
|N C i [v]| |C i | ≥ |N C j (v)| |C j |
The latter inequality will be called the weak proportion condition all along this chapter for easier reading. In a more general sense, a weak community structure is a weak kcommunity structure for some integer k.

Notice that a k-community structure is obviously a weak k-community structure since for any partition {C 1 , C 2 , . . . , C k } and any vertex v,

|N C i [v]| |C i | = |N C i (v)|+1 |C i |-1+1 ≥ |N C i (v)| |C i |-1
, and thus if the proportion condition of Definition 4.1 is satisfied, it is also satisfied for the Definition 4.2. The other way direction is not always true, that is a weak k-community structure is not necessarily a k-community structure (see Figure 4.2).

Notice that if a graph has a community structure, it must have at least 4 vertices (since of the condition on the sizes of the parts) and not be isomorphic to a star. Indeed, any star never contains any community structure since all leaves need to be in the same part as the center of the star in order to satisfy the proportion condition of a community structure. Thus, any partition satisfying this condition could not have more than one part and thus would not be a community structure.

Studied problems

In this part we investigate community structures for a fixed number of two communities and also study some variants of the 2-Community problem:

2-Community

Input: A graph G = (V, E). Question: Does G have a 2-community structure? A 2-community structure is a 2-partition {C 1 , C 2 } of the vertex set V such that |C 1 |, |C 2 | ≥ 2, and for each vertex v ∈ C i , i ∈ {1, 2}, |N C i (v)| |C i | -1 ≥ |N C 3-i (v)| |C 3-i |
which is a re-writting of the proportion condition of Definition 4.1. Since a graph containing a 2-community structure must have at least 4 vertices and be non-isomorphic to a star, those assumptions are assumed in this chapter even without explicitly mentioning that in some informal parts.

In the Weak 2-Community problem we are looking for a weak 2-community structure in a graph where the proportion condition is replaced by its corresponding weak proportion condition:

|N C i [v]| |C i | ≥ |N C 3-i (v)| |C 3-i |
Adding the balanced condition to the 2-Community problem, we obtain the Balanced 2-Community problem introduced by Estivill-Castro et al. [START_REF] Estivill-Castro | On connected two communities[END_REF]. Similarly we can define the Balanced Weak 2-community problem.

The additional constraint which asks for subgraphs induced by each part of the partition to be connected is a natural condition useful for the problems related to the connectedness. The Connected 2-Community problem is to decide if a graph has a connected 2community structure, i.e. a 2-community structure {C 1 , C 2 } such that the subgraphs induced by C 1 , C 2 are connected. We can define analogous problems for weak and balanced versions.

General observations

An interesting result about community structure has been proved by Olsen in [START_REF] Olsen | A general view on computing communities[END_REF]. He showed that if there is no restriction on the number of parts, a community structure can always be found in polynomial time in any graph which is not a star. Theorem 4.3 [START_REF] Olsen | A general view on computing communities[END_REF]. A community structure can be computed in polynomial time for any connected graph G = (V, E) containing at least four vertices, except stars.

Proof. The proof consists in setting up a polynomial time local search among certain partitions of V and prove that the result of the local search is a community structure.

Specifying the search space S. Considering a subset C ⊂ V , if we have a vertex u ∈ C such that all vertices in C \ {u} are neighbors of u, then we refer to u as a center of C. We now define the search space S as the set of all partitions Π of V with |Π| ≥ 2 such that for all C ∈ Π, |C| ≥ 2 and C has a center. The neighbors of a partition Π ∈ S are partitions in S that can be obtained from Π by moving one vertex from one set to another set of Π or by letting two vertices form a new set.

Generating one element of S. We consider four different vertices u 1 , u 2 , u 3 , u 4 such that {u 1 , u 2 }, {u 3 , u 4 } ∈ E. Now we expand the collection {{u 1 , u 2 }, {u 3 , u 4 }} with one vertex at each step carefully making sure that each set contains at least two vertices and has a center. Sometimes we might have to form a new set containing the new vertex and another vertex. By using induction on the total number of vertices in the sets in the collection, it is always possible to add a vertex and still have a collection of sets with at least two vertices and a center. Thus an element Π 1 ∈ S can be computed in polynomial time.

The objective function. For a partition Π we define g(Π) as the number of edges in the complement graph of G connecting vertices in different members of Π. More precisely, g is defined as follows:

g(Π) := {uv ∈ E : u ∈ C, v ∈ C , C ∈ Π, C ∈ Π, C = C }
where E is the complement of E. We now use local search on S to maximize the number of parts and g, by defining the following objective function h:

h(Π) := |Π| + g(Π)
We start with an element Π 1 of S and pick any neighbor of Π 1 such that the value of h increases for that neighbor. The process is repeated until h cannot be increased, and the final partition Π is returned as a community structure.

Analysis. We prove by contradiction that Π is a community structure. Assume that there is a vertex i ∈ V and C ∈ Π violating the proportion condition of a community structure, meaning that:

|N i (C i )| |C i | -1 < |N i (C)| |C| (4.1)
where C i ∈ Π is the part of Π containing i. If i is a center then (4.1) cannot hold because the left hand side is 1. Consequently, the set C i must contain at least three elements and i is not a center. We also note that i must have at least one neighbor in C, otherwise the right hand side would be 0. We now consider the following cases.

• If |C| = 2 and |C i | = 3, the vertex i is connected to the center of C i but not to the third vertex in C i (otherwise the left hand side of (4.1) would be 1), and i must have both vertices in C as neighbors (otherwise the proportion condition would be satisfied for i) on C i and C). If i is moved to C we would obtain a higher value of g without modifying the number of parts, thus the value of h would increase, contradiction. The local search can be done in polynomial time since each step in the process can be carried out in polynomial time and h(Π

• If |C| = 2
) ≤ n + n(n-1) 2 .
The previous algorithm uses local search in order to produce a community structure. Since a community may consist in two vertices linked by an edge, computing a community structure with the previous local search might lead to a community structure in which the number of communities is huge and the sizes of the communities are small (note that the algorithm split any clique into cliques of size 2 or 3). This is not always relevant for a proper community detection, especially when huge subsets of vertices that are strongly connected are never output as proper communities by the algorithm. A natural way to avoid this problem is to fix the number of communities in the community structure that we want to compute.

It can be noticed that there exist graphs in which it is easy to decide if there exists a k-community structure or not, for any integer k. In particular, as seen before, any star never contains any community structure. On the other hand, complete graphs on n vertices, n ≥ 4, always contain a k-community structure for any integer k ≤ n 2 since any k-partition in which each part contains at least 2 vertices is a k-community structure. Indeed, the proportion condition of a community structure is trivially satisfied since the left part of the inequation equals 1, i.e. all members knows everyone in its community (see Figure 4.3). More generally, for the same reasons, a partition of a graph in which each part is a clique is a community structure, and thus also a weak community structure. More generally, disconnected graphs can be an easy case when the number of connected components is at least 3 or if there are two connected components with at least 2 vertices. Indeed, any partition in which each part contains at least 2 vertices and corresponds to the union of some connected components is trivially a community structure since the right part of the proportion condition equals 0, i.e. each member does not know any members from the other communities.

However, because of the condition on the size of each community within a community structure, when there are only 2 connected components including an isolated vertex, there exists some graphs in which there is no community structure. As an example, in Figure 4.4, suppose first that x and y belongs to the same part of a community structure. Then, all vertices (except the isolated one) must belong to this part in order to fulfill the proportion condition since their only neighbors are x and y, and then the isolated vertex must be alone in a separated part, which is not possible because of the size restriction of communities. On the other hand, suppose that x and y are in different parts. Then, any neighbors of x (which are also neighbors of y) must be either with x or y as we discussed previously. Let be any partition such that x and y are not in the same part and each part is of size at least 2. Suppose that the isolated vertex belongs to the same part as x. Then, x does not satisfy the proportion condition of a community structure since the left part of the proportion condition is strictly less than 1 and the right part equals 1. By symmetry, if the isolated vertex belongs to the part containing y, the partition is not a community structure. Now if the isolated vertex belongs to a part not containing x nor y, then any other vertex of its part does not satisfy the proportion condition since this vertex has no neighbor in its part but has x and y as neighbors in the other parts.

Since such case is minor, we only investigate community structure in connected graphs in this chapter.

2-community structures in graph classes

This section contains our contribution about 2-community structures in some graph classes. In particular, we first show that if a graph has certain structural properties, then it has a connected 2-community structure which can be found in polynomial time. More precisely, we prove that such a statement is valid for complete bipartite graphs, complete split graphs, trees and graphs of high minimum or low maximum degrees.

Some graph classes in which the problem is easy to handle in linear time

Proposition 4.4. Any complete bipartite graph has a connected 2-community structure. Moreover, such community structure can be found in linear time.

Proof. Let G = (V = V 1 ∪ V 2 , E) be a complete bipartite graph with V 1 , V 2 the two independent sets. Wlog consider that |V 1 | ≤ |V 2 |.
Suppose first that V 1 contains an odd number of vertices (let

|V 1 | := 2k + 1). If |V 1 | = |V 2 |, let k vertices from V 1 and k vertices from V 2 be in a set C 1 and let C 2 := V \ C 1 . Then it can be checked that {C 1 , C 2 } is a connected 2-community structure. Now assume that |V 1 | < |V 2 |.
We define a connected partition as follows: let

k vertices from V 1 and x := k|V 2 |-k 2k+1 vertices from V 2 be in a set C 1 and define C 2 := V \ C 1 . Notice that x ≤ k|V 2 |-k 2k+1 + 2k+1 2k+1 = k|V 2 |+k+1 2k+1 . We show that {C 1 , C 2 } is a connected community structure. Let a be a vertex of V 1 ∩ C 1 . Since |V 2 | ≥ |V 1 | ≥ 2k = 2k 2 k ≥ 2k 2 k+1 , we have k|V 2 | + |V 2 | ≥ 2k 2 . Thus 2k 2 |V 2 | -2k 2 ≥ 2k 2 |V 2 | + k|V 2 | -2k|V 2 | -|V 2 | and we obtain k|V 2 |-k 2k+1 ≥ k|V 2 |-|V 2 | 2k . Thus, since x ≥ k|V 2 |-k 2k+1 , we have x ≥ k|V 2 |-|V 2 | 2k . Finally, we have x|V 2 | -x 2 + kx + x ≥ k|V 2 | + x|V 2 | -|V 2 | -kx -x 2 + x and we obtain x x+k-1 ≥ |V 2 |-x |V 2 |-x+k+1
and thus a satisfies the proportion condition of a community structure.

Let b be a vertex of

V 2 ∩ C 1 . Since x ≤ k|V 2 |+k+1 2k+1 , we have |V 2 |k + k 2 -xk + k ≥ xk + k 2 -k + x + k -1. Thus k x+k-1 ≥ k+1 |V 2 |-x+k+1
and b satisfies the proportion condition of a community structure.

Let c be a vertex of

V 1 ∩ C 2 . Since |V 2 | > |V 1 |, we have |V 2 | ≥ 2k + 2. This implies that k|V 2 |+k+1 2k+1 ≤ |V 2 | 2 . Since x ≤ k|V 2 |+k+1 2k+1 , we have x ≤ |V 2 | 2 . Thus, we have |V 2 |x + |V 2 |k -x 2 - xk ≥ |V 2 |x -x 2 + kx. Thus |V 2 |-x |V 2 |-x+k ≥ x x+k-1 and c satisfies the proportion condition of a community structure. Let d be a vertex of V 2 ∩ C 2 . Since x ≥ k|V 2 |-|V 2 | 2k+1 (as seen previously), we have kx + k 2 + x + k ≥ |V 2 |k -kx + k 2 . Thus k+1 |V 2 |-x+k ≥ k x+k-1
and d satisfies the proportion condition of a community structure.

Since Proof. The proof is similar to the one for bipartite graphs considering V 1 , V 2 as the clique and the independent set of the split graph. The only difference is that any vertex in the clique part will always trivially satisfy the proportion condition since it has all of the other vertices of its part as neighbors.

G[C 1 ] and G[C 2 ] are clearly connected, {C 1 , C 2 } is a connected 2-community structure. Now suppose that V 1 contains an even number of vertices. Then consider |V 1 | 2 vertices from V 1 and |V 2 | 2 vertices from V 2 in a set C 1 and put C 2 := V \ C 1 ,
Theorem 4.6. Every tree with at least 4 vertices (except a star) has a connected 2community structure that can be found in linear time.

Proof. Let G = (V, E) be a tree not isomorphic to a star. We prove that there exists an edge e ∈ E such that the two connected components of G \ e form a 2-partition which is a connected 2-community structure.

Let e = {u, v} be an edge in E such that d(v), d(u) ≥ 2 (due to the assumption about G such an edge e must exist). Consider a partition {X u , X v } of V with X u (resp. X v ) be the set of vertices of the connected component of G \ e containing u (resp. v).

First we notice that only one of the vertices u and v may not satisfy the proportion condition. If this is not true then

d(u)-1 |Xu|-1 < 1 |Xv| and d(v)-1 |Xv|-1 < 1 |Xu| . Since d(u), d(v) ≥ 2, it implies |X v | < |Xu|-1 d(u)-1 ≤ |X u | -1 and |X u | < |Xv|-1 d(v)-1 ≤ |X v | -1,
which is not possible. If both vertices u and v satisfy the proportion condition, then {X u , X v } is obviously a 2-community structure. If not, then without loss of generality, let the vertex u satisfy the proportion condition and v do not. Then the Update procedure is repeated and if no update is possible, a modified partition {X u , X v } is already a 2-community structure as it is shown later.

The Update procedure:

Let v 1 , v 2 , . . . , v d(v)-1 be the neighbors of v excluding u (there is at least one such a vertex due to our assumption d(v) ≥ 2). For each i,

1 ≤ i ≤ d(v) -1, and e i = {v, v i } ∈ E, let X i be the set of vertices of the connected component in G \ e i containing v i . Notice that if for all j, 1 ≤ j ≤ d(v) -1, d(v j ) = 1,
then v must already satisfy the proportion condition in the partition {X u , X v } at the beginning of the Update procedure.

Hence from now we suppose that v has at least one neighbor of degree at least 2 excluding u. In the following we show that there exists j, 1 ≤ j ≤ d(v) -1, such that d(v j ) > 1 and the vertex v satisfies the proportion condition in the partition {X j , V \ X j }. Indeed, suppose that for all j, 1 ≤ j ≤ d(v) -1, with d(v j ) > 1, this is not true. Notice that for each such j and the partition {X

j , V \ X j } must hold d(v)-1 n-|X j |-1 < 1 |X j | which implies that: d(v)|X j | < n -1. (4.2)
Moreover, for any j, 1 ≤ j ≤ d(v) -1 with d(v j ) = 1 we have |X j | = 1 and hence:

d(v)|X j | < n -1, (4.3)
since G is not a star. Recall that v doesn't satisfy the proportion condition in the partition {X u , X v }, hence d(v)-1 |Xv|-1 < 1 |Xu| and also:

d(v)|X u | < n -1, (4.4)
Summing (4.2), (4.3) and (4.4) together, we obtain d(v)

d(v) j=1 |X j | = d(v)(n -1) < d(v)(n -1), a contradiction.
Hence, there exists i,

1 ≤ i ≤ d(v) -1 such that d(v i ) > 1
and the vertex v satisfies the proportion condition in the partition {X i , V \ X i }. Then, relabel u := v and v := v i and return to the beginning of the Update procedure.

Each time the labels of u and v are updated, the size of X u strictly increases by at least one, hence the whole process always terminates. A final partition at the end of the process is a connected 2-community structure because both partitions correspond to two connected components of a tree obtained by removing an edge.

Notice that finding such an edge can be done in O(|V |) operations. First, in constant time fix an edge e = {u, v} such that d(v), d(u) ≥ 2. Then, consider G \ e as a union of two trees T u and T v , where T u is a tree on the vertex set X u rooted in u (and similarly for T v on X v rooted in v). For each vertex w of G calculate recursively the size of the subtree of T u (or T v ) rooted in w which can be done in time O(|V |). Finally, using the sizes of the subtrees, check if {X u , X v } corresponds to a 2-community structure and if needed, update X u , X v according to the algorithm. The number of such updates is clearly at most |E|. Since G is a tree, the repetition of the Update procedure finishes with a connected 2-community structure in O(|V |) time.

Very recently, Estivill-Castro et al. proved in [START_REF] Estivill-Castro | Hardness and tractability of detecting connected communities[END_REF] the same result using different methods. Our approach is more structural and the proof for the existence of an edge that connects two communities results directly in a linear time algorithm.

Cubic graphs and graphs of maximum degree 3

Now we investigate other graph classes that have low densities. We first prove that 2community structures always exist in cubic graphs, and then we extend the result to graphs of maximum degree 3. In both cases, it is possible to design an algorithm running in polynomial time to guarantee the connectedness of each part of the 2-community structure.

First, the restrictions on the size of partitions are discussed to ensure the vertices fulfil the proportion condition of a 2-community structure.

Lemma 4.7. Let G = (V, E) be a graph of maximum degree 3 of size n. Let {C 1 , C 2 } be a partition of V such that n-1 3 ≤ |C i | ≤ n -n-1 3 , i = 1, 2.
Then each vertex of degree 3 in G with at most one out-neighbor fulfils the proportion condition of a 2-community structure.

Furthermore, if for some i ∈ {1, 2},

|C i | = n-1 3 (or also |C i | = n-1 3
+1 in case n ≡ 1 mod 3) then each vertex of degree 3 in C i with two out-neighbors fulfils the proportion condition too.

Proof. Let {C 1 , C 2 } be a fixed partition of G such that n-1 3 ≤ |C i | ≤ n -n-1 3 , i = 1, 2.
It is clear that the proportion condition is true for each vertex which has only neighbors in its own part. Firstly, suppose the vertex v from C i , i ∈ {1, 2} has exactly one out-neighbor.

Since

|C i | ≤ n -n-1 3 , then obviously |C i | ≤ n -n-1 3 and 2 |C i |-1 ≥ 1 n-|C i | .
Therefore the proportion condition is fulfilled for the vertex v. Now suppose that for i ∈ {1, 2} there is a vertex v ∈ C i with exactly two out-neighbors and

|C i | = n-1 3 . Obviously, n-1 3 ≤ n+2 3 and hence 2 n-1 3 -2 ≤ n -n-1 3 which implies 1 n-1 3 -1 ≥ 2 n-n-1

3

. This corresponds to the proportion condition for the vertex v. Similarly

if |C i | = n-1 3 + 1 and n ≡ 1 mod 3: n -1 = 3 n-1 3 which implies 1 n-1 3 ≥ 2 n-n-1 3 -1 .
This lemma can be used to design a polynomial time algorithm which outputs a 2community structure with a cubic graph in input.

Stage 2:

The algorithm moves some vertices between C 1 and C 2 until n-1

3 ≤ |C 1 | ≤ n -n-1 3
and each vertex of G has a restricted number of neighbors out of its own part in a such way that Lemma 4.7 can be applied.

Stage 1:

Let u, v ∈ V be such that uv ∈ E and put C 1 = {u, v}. Now repeat the following steps (S1) and (S2) until

|C 1 | = n-1 3 : (S1) Let w be a neighbor of u (or v) which is not in C 1 , put C 1 := C 1 ∪ {w}, u := w (or v := w). ( S2
C 1 is three which implies G is not connected. Thus |C 1 | ≤ 2 n-1 3 -1 ≤ n -n-1

3

. Note that now every vertex in G has at most one neighbor out of its part and thus applying Lemma 4.7, {C 1 , C 2 } is a 2-community structure.

Case 2(B): Wlog we suppose that d out (u) = 2 and u is adjacent to w. Furthermore, if d out (v) = 2 then also v is adjacent to w. Now using C 1 , C 2 we define a 2-community partition. After the initial update: There are two possible scenarios: -If n ≡ 0 mod 3 or n ≡ 1 mod 3, then define the last update:

C 1 := C 1 ∪ {w}, C 2 := C 2 \ {w}, all vertices in C 1 have at most one neighbor in C 2 and |C 1 | = n-1 3 + 1. Then repeat the update step until |C 1 | = 2 n-1 3 -1 or if there is no such a vertex z to update C 1 : • if ∃z ∈ C 2 , d out (z) ≥ 2, define C 1 := C 1 ∪ {z}, C 2 := C 2 \ {z}, C 1 C 2 C 1 C 2
(i) if |C 1 | ≤ 2 n-1 3 - 1
C 1 := C 1 ∪ {z}, C 2 := C 2 \ {z}. Now only one vertex of C 1 has one neighbor in C 2 . Because |C 1 | = 2 n-1 3 ≤ n -n-1 3
, the proportion condition is true for all vertices of G because of Lemma 4.7. Hence the updated partition {C 1 , C 2 } is a 2-community structure.

Case 2(C): Without loss of generality, we suppose that

d out (u) = 2. Update C 1 := C 1 ∪ {w} \ {u}, C 2 := V \ C 1 .
Notice that after the update, |C 1 | = n-1 3 and there may be at most two vertices in C 1 which have two neighbors in C 2 . Hence we are again in one of the cases (A)-(D) of second stage, but each time we apply this update the size of the cut between C 1 and C 2 is decreases by two. Therefore the process is finite.

Case 2(D): Without loss of generality, suppose that u is adjacent to w and

d out (u) = 2. Update C 1 := C 1 ∪ {w} \ {v}, C 2 := V \ C 1 .
Notice that after the update, |C 1 | = n-1

3

. Moreover, u has two neighbors inside C 1 since u is obviously not adjacent to v. Hence we are in one of the previous cases of stage 2, since there is at most one vertex in C 1 (the neighbor of v) which could have two neighbors in C 2 . Now we investigate the problem of finding a 2-community structure in 3-regular graphs with additional condition of connectivity for each part. Using the algorithm from Theorem 4.8 as a tool we extend the result in 3-regular graphs for a connected 2-community structure, but with many fine details in the proof. We first introduce a new lemma to make the construction more simple to read. Lemma 4.9. Let G be a 3-regular graph and

{C 1 , C 2 } a connected 2-partition of G with n-1 3 ≤ |C 1 | ≤ n -n-1
3 such that each part has at most one vertex with two neighbors out of its own part. Then G has a connected 2-community structure which can be found in polynomial time.

Proof. The main idea is to move selected vertices between two parts in such a way that it preserves connectivity and offers the option to use Lemma 4.7.

We discuss four cases depending on which vertices have two neighbors out of its own part. Notice that transferring a vertex which has two neighbors out of its part does not compromise the connectivity of the partition.

(a) If there is no vertex in C 1 and C 2 with two neighbors out of its own part, then using Lemma 4.7 the partition {C 1 , C 2 } is already a connected 2-community structure.

(b) If the only vertex with two neighbors out of its own part is in C 2 , then update C 1 , C 2 using the following loop:

• While |C 1 | < n-n-1 3
and there exists a vertex z in C 2 which has two neighbors in C 1 , update

C 2 := C 2 \ {z}, C 1 := C 1 ∪ {z}.
Obviously after each run of the while loop both parts of the partition remains connected. At the end of the while loop

-if |C 1 | < n -n-1 3
, then all vertices in G have at most one neighbor out of their parts and satisfy the properties of 2-community structure due to Lemma 4.7, -if

|C 1 | = n-n-1 3 then |C 2 | = n-1 3
and hence all vertices in C 2 with two neighbors out of the own part satisfy the properties of 2-community structure due to Lemma 4.7, the rest of vertices also satisfy Lemma 4.7.

(c) The only vertex with two neighbors out of its own part is in C 1 . Then the case is similar to (b) by symmetry swapping the roles between C 1 and C 2 .

(d) There are two vertices:

v 1 ∈ C 1 with two neighbors in C 2 and let v 0 1 be the neighbor of v 1 ∈ C 1 ; v 2 ∈ C 2 with two neighbors in C 1 and let v 0 2 be the neighbor of v 2 ∈ C 2 . Now we need to distinguish two cases:

(i) If v 1 v 2 ∈ E, then we update the partition as follows. If |C 1 | < n -n-1 3 then define a new partition C 1 := C 1 ∪{v 2 }; C 2 := C 2 \{v 2 }, otherwise C 1 := C 1 \{v 1 }; C 2 := C 2 ∪ {v 1 }. Obviously, {C 1 , C 2 }
is a connected partition which fulfil initial conditions of lemma, so we can apply case (a), (b), (c) or (d) again. Notice that the case (d) can be repeated only finite number of times since the cut size between C 1 and C 2 decreases each time the case is applied.

(ii) If v 1 v 2 /
∈ E we define the following update

C 1 := C 1 ∪ {v 2 } \ {v 1 }, C 2 := C 2 ∪ {v 1 } \ {v 2 }.
The new partition is a connected partition with no change in sizes and the following options are possible:

• If d out (v 0 1 ) = 0 or d out (v 0
2 ) = 0 before the update, then update removes at least one of the vertices with two outgoing edges. Now we can again apply one of cases (a), (b) or (c) which leads to a connected 2-community structure.

• If d out (v 0 1 ) > 0 and d out (v 0 2 ) > 0 then we can apply case (d) again. This process is finite because each time the size of the cut size between C 1 and C 2 is decreased by 2.

Obviously, the whole procedure can be run in polynomial time. Now we can prove the following theorem: The difference to the approach from Theorem 4.8 is that C 2 remains connected until the end of the first stage, where C 1 is connected in both approaches.

Then we apply the second stage of the algorithm from Theorem 4.8. Since moving a vertex which has 2 neighbors in the other part never disconnect any part and all transfers only affect such vertices, the final partition {C 1 , C 2 } remains connected at the end of the second stage.

The major update construction:

Step A: Let N ⊆ C 2 be the set of neighbors of all labelled vertices from C 1 , hence 1 ≤ |N | ≤ 4. Step A consists in splitting C 2 by defining subsets Q, Q , Z of C 2 and vertices q, q ∈ N (q, q are not necessarily distinct) such that {Q, Q , Z, {q}, {q }} is a connected partition of the graph induced by C 2 and each vertex from Q ∪ Q has at most one neighbor in C 1 . Furthermore, the entire set Q (resp. Q ) has exactly one neighbor outside Q (resp. Q ) in C 2 and this is the vertex q ∈ N (resp. q ∈ N ).

We show that such Q, Q , Z exist and are always connected. Consider a vertex v 1 ∈ N . The vertex v 1 has necessarily two neighbors in C 2 and the subgraph induced by

C 2 \ {v 1 } is disconnected (otherwise (S1) or (S2) from Stage 1 could be applied). Let C 1 2 and C 2 2 be the two connected components of C 2 \ {v 1 }. Define Q := C 1 2 , Q := C 2 2 and q = q = v 1 . Moreover, Z = ∅ is trivially connected. Hence in case |N | = 1 we can now move directly to Step B. If |N | > 1, select another vertex v 2 ∈ N . Such vertex must be in Q or Q defined above. Consider wlog that v 2 ∈ Q. If v 1 v 2 ∈ E, then update Q := Q \ {v 2 }, q := v 2 , q := v 1 and Z := ∅. Notice that Q is still connected since v 2 has only one neighbor in Q. If v 1 v 2 ∈ E, Q \ {v 2 } must be disconnected into two part Q 1 and Q 2 . Name Q 2 the
set which contains a neighbor of v 1 (Q 1 obviously cannot have a neighbor of v 1 , since the other two neighbors are in Q and C 1 , respectively). Update Q := Q 1 , q := v 2 and Z := Q 2 . Hence in case |N | = 2, the construction in Step A is over and we can continue directly with Step B. Indeed, Q has only v 2 ∈ N as a neighbor in C 2 \ Q and similarly for Q and v 1 ∈ N .

Suppose now that |N | ≥ 3. Then select another vertex v 3 ∈ N , the vertex v 3 must be in Q, Q or Z defined above. If v 3 ∈ Z, then Q, Q , Z, q and q already satisfy the properties. Otherwise, It is also important to notice that if |N | > 2 then following the construction N \{q, q } ⊆ Z.

v 3 ∈ Q ∪ Q and wlog we suppose v 3 ∈ Q. If v 3 v 2 ∈ E, then update Q := Q \ {v 3 }, q := v 3 and Z := Z ∪ {v 2 } which is trivially connected. Otherwise, Q \ {v 3 } must be disconnected, let Q 1 and Q 2 be its connected parts. Denote Q 2 the set which has a neighbor of v 2 (then Q 1 cannot have a neighbor of v 2 ). Update Q := Q 1 , q := v 3 , Z := Z ∪ Q 2 ∪ {v 2 }. Again, if |N | = 3,
Step B: This step consists in looking at the size of the sets

Z, Q, Q , Z ∪ Q ∪ {q}, Z ∪ Q ∪ {q } and update {C 1 , C 2 }
depending on the size of those sets which are known to be connected by moving entire sets of vertices instead of moving them one by one.

(i) If |Q| > n -n-1 3 or |Q | > n -n-1 3 then define C 1 := V \Q, C 2 := Q (similarly for Q
) and remove all labels. Then label q and apply again the updates of the initial construction on the partition { C 1 , C 2 }.

Note. The size of C 1 is still strictly less than n-1 3 but it has strictly grown and the partition { C 1 , C 2 } is connected, so the update is correct.

(ii) If n-1 3 ≤ |Q| ≤ n -n-1 3 or n-1 3 ≤ |Q | ≤ n -n-1 3 , define C 1 := V \Q, C 2 := Q (similarly for Q ).
The vertices in C 1 have at most one neighbor in C 2 and there may be only one vertex in Q (= C 2 ), the neighbor of q in Q, with two neighbors out of its part. Following the definition of Q, all other vertices in Q may only have at most one vertex in C 1 (their neighbors were only in C 1 and the vertex q). Obviously both parts of the partition are connected. Hence, we can use Lemma 4.9 to find a connected 2-community structure.

(iii) If |Q| = n-1 3 -1 or |Q | = n-1 3 -1. The construction below is based on |Q| = n-1 3
-1, but it can be easily modified for

|Q | = n-1 3 -1. If |Q| = n-1 3 -1 then -in case |N | > 1: update C 1 := Q ∪ {q}, C 2 := V \(Q ∪ {q}) (similarly in case of Q ).
The subgraphs induced by C 1 and C 2 are obviously connected and

| C 1 | = n-1

3

. All vertices have at most one neighbor in the other part except q which has two neighbors in C 2 . Then applying Lemma 4.7, the partition

{ C 1 , C 2 } is a connected 2-community structure. -in case |N | = 1: update C 1 := Q , C 2 := V \Q Due to the sizes of the sets C 1 and Q (|C 1 | < n-1 3 and |Q| = n-1 3 -1) obviously |Q | ≥ n -2 n-1 3 + 1 which means |Q | ≥ n-1 3 . But similarly also |Q | ≤ n -n-1 3 , hence n-1 3 ≤ |Q | ≤ n -n-1 3 .
Furthermore, there is at most one vertex from each part C 1 , C 2 which may have two vertices out of its own part. Hence Lemma 4.9 can be used to find a connected 2-community structure.

(iv) If |Q| < n-1 3 -1 and |Q | < n-1 3 -1 (then necessarily |Z| > 0). • If |Z| ≥ n -n-1 3
, define C 1 := V \ Z, C2 := Z and remove all labels. If there exists a vertex in C 1 which has two neighbors in Z then label it (it can be at most one such vertex), else label q. Then continue with the updates of the initial construction for { C 1 , C 2 }.

Note. | C 1 | ≤ n-1 3
and the size of C 1 has strictly grown compared to C 1 . Moreover, there is no vertex which has two neighbors out of its own part, except one vertex in C 1 which may have two neighbors in Z (in that case such a vertex is labeled). Besides, the partition is connected, so the step is correctly defined.

• If n-1 3 ≤ |Z| < n -n-1 3 , define C 1 := V \ Z, C 2 := Z. If there is no vertex x in C 1 such that d out (x) = 2, then move any vertex z ∈ C 2 such that d out (x) = 2
to C 1 until you can apply Lemma 4.7. So now we consider that there exist some vertex x ∈ C 1 such that d out (x) = 2 (notice that there are at most two vertices in C 2 which may have two neighbors in C 1 ).

While there exist one vertex z ∈ C 2 and one vertex y

∈ C 1 such that d out (z) = d out (y) = 2 and {z, y} / ∈ E, update C 2 := C 2 ∪ {y} \ {z}, C 1 := V \ C 2 .
If there is at most one vertex x ∈ C 1 such that d out (x) = 2 and at most one vertex z ∈ C 2 such that d out (z) = 2, then apply Lemma 4.9 to obtain a connected 2-community structure.

Else if there exist z, z ∈ C 2 and x ∈ C 1 such that

d out (z) = d out (z ) = d out (x) = 2, zx ∈ E and z x ∈ E, then move x into C 2 . Notice that we still have | C 2 | ≤ n -n-1
3 and now every vertex in C 2 has at most one neighbor in C 1 so we can move every vertex z ∈ C 1 into C 2 until we can use Lemma 4.7 and obtain a connected 2-community structure.

Else, every vertex in C 2 has at most one neighbor in C 1 so we can move every vertex z ∈ C 1 into C 2 until we can use Lemma 4.7 and obtain a connected 2-community structure.

• If 0 < |Z| < n-1 3 then |Z ∪ Q ∪ {q}| ≤ 2 n-1 3 -2 < n -n-1 3 . Notice that n-1 3 ≤ |Z ∪ Q ∪ {q}| (indeed, |Z ∪ Q ∪ {q}| < n-1 3 is not possible since |C 1 | + |Z| + |Q| + |Q | + 2 = n). Then define C 1 := Z ∪ Q ∪ {q} and C 2 := V \ (Z ∪ Q ∪ {q}
). Now the only vertices which may have two neighbors out of their own part are one labeled vertex in the old C 1 and a neighbor of q in Z. Hence we can apply Lemma 4.9 to obtain a connected 2-community structure.

Each case leads to a connected 2-community structure. This approach is very structural and efficient but is a little fastidious. It is possible to design a more general algorithm for graphs of maximum degree 3 which uses convergence properties to obtain a 2-community structure in polynomial time.

Similarly to vertices of degree 3, the restrictions on the size of partitions are discussed to ensure the vertices of degree 2 fulfil the proportion condition of a 2-community structure. Lemma 4.11. Let G = (V, E) be a graph of maximum degree 3 of size n.

Let {C 1 , C 2 } be a partition of V such that n-1 3 ≤ |C 1 | ≤ n 2 .
Then each vertex of degree 2 in C 1 with at most one out-neighbor fulfils the proportion condition of a 2-community structure.

If the partition is balanced, then each vertex of degree 2 in G with at most one outneighbor fulfils the proportion condition.

Proof. Let {C 1 , C 2 } be a partition of V such that n-1 3 ≤ |C 1 | ≤ n 2 .
Obviously, any vertex of degree 2 with no neighbors out of its own part fulfils the proportion condition. Moreover any vertex of degree 2 in C 1 with only one out-neighbor satisfies 1

|C 1 |-1 ≥ 1 |C 2 | since |C 1 | ≤ |C 2 |. If the partition is balanced, then 1 |C 1 |-1 ≥ 1 |C 2 | and 1 |C 2 |-1 ≥ 1 |C 1 |
, and hence the vertices of degree 2 from both parts with exactly one out-neighbor satisfy the proportion condition.

The lemmas 4.7 and 4.11 can be sum up into the following theorem which gives a good overview of the possibilities for each vertex belonging to a 2-community structure. Theorem 4.12. Let G = (V, E) be a graph of maximum degree 3 of size n and {C 1 , C 2 } be a partition of V such that n-1

3 ≤ |C i | ≤ n -n-1 3 , i = 1, 2.
If the partition has one of the properties (i)-(iii) where only specified vertices may have out-neighbors (the other ones have only in-neighbors), then {C 1 , C 2 } is a 2-community structure on G:

(i) The vertices of degree 2 from the smaller part and all the vertices of degree 3 have at most one out-neighbor.

(ii) The vertices of degree 2 and 3 have at most one out-neighbor and the partition is balanced.

(iii) The vertices of degree 2 from the smaller part have at most one out-neighbor, the vertices of degree 3 in C i , for some i ∈ {1, 2}, have at most two out-neighbors and

|C i | = n-1 3 (or also |C i | = n-1 3 + 1 if n ≡ 1 mod 3
) and the vertices of degree 3 in C 3-i have at most one out-neighbor.

Proof. In each case (i), (ii), or (iii), all the vertices of the graph G satisfy the proportion condition due to Lemmas 4.7 and 4.11. Thus, {C 1 , C 2 } is a 2-community structure on G.

The general algorithm which find a 2-community structure in polynomial time in graphs of maximum degree 3 consists in starting with an initial partition with the property that no vertex has all of its neighbors out of its part (see Lemma 4.13). Then, the algorithm consists in moving vertices from one part to the other until the remaining partition is a 2-community structure (see Theorem 4.14). Convergence properties ensure that the algorithm always finishes and output the solution in polynomial time. Lemma 4.13. Every connected graph of maximum degree 3 on at least 6 vertices has a partition {C 1 , C 2 } such that no vertex in the graph has all of its neighbors out of its own part, n-1

3 ≤ |C i | ≤ n -n-1 3 , i = 1, 2.
Moreover, such a partition can be found in polynomial time.

Proof. Let G = (V, E) be a connected graph of maximum degree 3 on n vertices, n ≥ 6.

Let u, v ∈ V be such that uv ∈ E and initially, put into C 1 the vertices u, v including its pendant vertices. If there is a vertex z of degree 2 with u and v as neighbors, update (S2) If there is no such vertex w then u and v have all its neighbors in C 1 . In such a case let u be any vertex in C 1 with at least one out-neighbor in C 2 (such a vertex must always exist due to connectivity of G).

Notice that each time we apply (S1), by (S2) we ensure that there is no vertex in C 2 with only out-neighbors. The algorithm finishes with a set C 1 , n-1

3 ≤ |C 1 | ≤ n-1 3 + 2 where |C 1 | ≤ n -n-1 3 , due to n ≥ 6.
Clearly, the algorithm runs in a polynomial time and results in a partition

{C 1 , C 2 }, n-1 3 ≤ |C i | ≤ n -n-1 3
, i = 1, 2 such that no vertex has all its neighbors out of its own part. Now we give the general algorithm which output a 2-community structure from a connected graph of maximum degree 3. Let n ≥ 6. Consider any partition

{C 1 , C 2 } of V , n-1 3 ≤ |C i | ≤ n -n-1 3 , i = 1, 2,
such that no vertex in G has all of its neighbors out of its part (such a partition can be found in polynomial time due to Lemma 4.13). In such partition there may exist vertices not satisfying the proportion condition which can be split into two categories:

(A) if there exists i ∈ {1, 2}, |C i | > n-1 3 and n ≡ 1 mod 3 or |C i | > n
3 and n ≡ 1 mod 3, the vertices of degree 3 in C i with two out-neighbors, (B) the vertices of degree 2 in the larger part with one out-neighbor, if the partition is not balanced.

Our algorithm transfers the vertices between C 1 and C 2 in several steps until all vertices satisfy the proportion condition. In each step of the algorithm the size of the cut between C 1 and C 2 decreases and we insure that no vertex from the partition has only out-neighbors.

The algorithm applies the improvement procedure (consisting of three stages) as many time as there is a vertex transferred between the parts. In the initial partition {C 1 , C 2 }, there are only 3 type of vertices that do not satisfy the proportion condition: vertices of degree 3 in C 1 with two out-neighbors (if

|C 1 | > n-1 3 ), vertices of degree 3 in C 2 with two out-neighbors (if (if |C 2 | > n-1 3
) and vertices of degree 2 with one out-neighbor, respectively handled by the three stages. Each stage consists in moving such vertices in the other part so they satisfy the proportion condition (See Figure 4.8 as an illustration), taking care of not compromising the proportion condition for any other vertex.

← ← Stage 1 → → Stage 2 ← Stage 3 C 1 C 2 C 1 C 2 C 1 C 2 Figure 4
.8: Sketch of the three stages of the algorithm to compute a 2-community structure in a graph of maximum degree 3. Candidates vertices to be moved are in gray.

Improvement Procedure: Stage 1

In this stage we primarily handle vertices of degree 3 in C 2 which have two out-neighbors by transferring them into C 1 , keeping the size of C 1 under n -n-1 and the property that there is no vertex in the partition with only out-neighbors.

While |C 1 | < n -n-1 3
and there is a vertex u ∈ C 2 which has two out-neighbors, repeat the following two steps: We emphasize that at the end of each iteration of the while loop in Stage 1, no vertex in the partition has only out-neighbors. By assumption such vertex doesn't exist before entering the first iteration of the while loop. In each iteration of the while loop when (a) is executed, it may create at most one vertex with only out-neighbors (which must be the neighbor of u in C 2 ), and (b) transfers it into C 1 . In the part (b) a vertex with only out-neighbors cannot be created since the transferred vertex v has no neighbor in C 2 .

(a) Update C 1 := C 1 ∪ {u}, C 2 := C 2 \ {u}.
Moreover, notice that each iteration of the while loop in Stage 1 decreases the size of the cut by at least one since both parts (a) and (b) decrease the size of the cut by at least one each time they are executed. After the last iteration of while loop necessarily |C 1 | ≤ n -n-1 3 + 1 since each iteration of the while loop may increase the size of C 1 by at most 2.

If

|C 1 | = n -n-1 3
+ 1, then the last iteration of the while loop had to decrease the size of the cut by at least two by applying both steps (a) and (b). In such a case we make the following Size Update.

Size Update in case |C

1 | = n -n-1 3 + 1: (a*) Let v ∈ C 1 be a vertex with at least one neighbor in C 2 , update C 1 := C 1 \ {v}, C 2 := C 2 ∪ {v}.
(b*) If there exists vertices in C 1 with only out-neighbors, then transfer all such vertices into C 2 .

Since G is connected, such vertex v in part (a * ) always exists. Such transfer may create at most 2 vertices in C 1 with only out-neighbors (they must be neighbours of v in C 1 ), so we also transfer them into C 2 in part (b * ). After the Size Update, there is no vertex with only out-neighbours and n-1

3 ≤ |C 1 | ≤ n -n-1 3 since n ≥ 6.
Notice that the Size Update may increase the size of the cut by at most one, but the last iteration of the while loop in Stage 1 decreases it by at least two, hence together the size of the cut decreases by at least one.

Improvement Procedure: Stage 2

In this stage we primarily handle vertices of degree 3 in C 1 which have two out-neighbors by transferring them into C 2 , keeping the size of C 2 under (nn-1

3

) and the property that there is no vertex in the partition with only out-neighbors.

Since Stage 2 is symmetrical to Stage 1, swap the roles of C 1 and C 2 by relabelling C 1 := C 2 and C 2 := V \ C 1 and apply Stage 1. Notice then all previous conclusions hold.

Improvement Procedure: Stage 3

If the partition is not balanced, the vertices of degree 2 with one out-neighbor must be transferred from the larger part to the smaller part, keeping the property that there is no vertex in the partition with only out-neighbors. In each iteration of the while loop in Stage 3 when (a) is executed, part (b) ensures that there is no vertex in the partition with only out-neighbors at the end of the iteration.

If |C 1 | > |C 2 |, relabel C 1 := C 2 and C 2 := V \ C 1 While |C 1 | < n
Each iteration of the while loop in Stage 3 doesn't increase the size of the cut. In the end of Stage 3 if the final partition doesn't have a 2-community structure then a vertex of the category (A) or (B) must exist in the partition. In the first case Stage 1 or 2 must be executed before entering Stage 3 again, hence the cut-set is decreased by at least 1. The second case is only possible if n 2 = n 2 and two vertices were added in the last iteration of the while loop. It means part (b) must be executed and the cut-size is decreased by at least 2. Notice that Stage 3 may again create vertices of the category (A) even if they didn't exist before entering Stage 3.

It is easy to see that the algorithm always finishes. After each iteration of the while loop in Stage 1 (resp. Stage 2), the size of the cut decreases by at least one. In Stage 3 each iteration of the while loop increases the size of the smaller parts by at least one vertex and stops before/when the partition is balanced or the smaller part becomes the larger part, but in that case the cut-size is decreased by at least 2. The algorithm clearly runs in a polynomial time.

Let's discuss the correctness of the algorithm. It always finishes with the sizes n-1

3 ≤ |C i | ≤ n -n-1 3 , i = 1, 2.
The algorithm starts with the partition in which every vertex has at least one neighbor in its own part. The key feature of the algorithm is to keep this property valid during the all stages of the algorithm which was discussed separately for each stage. Hence all vertices of degree 1 in the final partition clearly satisfy the proportion condition.

• If the final partition is balanced then all vertices of degree 2 and 3 may have at most one out-neighbor (otherwise Improvement Procedure could be applied again), hence it has a 2-community structure due to Theorem 4.12(ii).

• If the final partition is not balanced, then the partition must have the properties described in Theorem 4.12(i) or (iii). Otherwise, one of Stages 1-3 could be applied again. Hence, the final partition has a 2-community structure.

The latter algorithm gives a 2-community structure in polynomial time without any restriction about its connectivity. It is interesting that this algorithm can be modified in order to insure the connectivity of the 2-community structure given in output. The key difference from the previous algorithm is to ensure that the initial partition is connected (instead of just requiring that any vertex has at least one neighbor in its part). This can be found in polynomial time and allows us to design a new algorithm which ensure the connectedness of the 2-community structure.

≤ |C i | ≤ n -n-1 3 , i = 1, 2.
Moreover, such a partition can be found in polynomial time.

Proof. Let G = (V, E) be a graph with the given properties.

Initially, put into C 1 any vertex v such that G[V \ {v}] is connected. The existence of such vertex is ensured by the following procedure. Let x be any vertex of G. While G[V \{x}] is disconnected, label the vertex x and consider any other vertex x in a connected component of G[V \ {x}] that does not contains any labeled vertex, and let x := x . Let v be the last considered vertex x. This procedure terminates in less than |V | steps.

The algorithm keeps connectivity of G[C 1 ] and G[C 2 ] and extends C 1 either by transferring vertices from C 2 to C 1 or relabelling a suitable connected part of the graph until

n-1 3 ≤ |C i | ≤ n -n-1 3 , i = 1, 2.
The algorithm starts with the initial set C 1 and repeats the Update Procedure until

|C 1 | ≥ n-1 3
. In each run of the procedure only one of the options 1 or 2 is executed.

The Update procedure: Let w be a vertex in C 2 which has a neighbor in C 1 (such a vertex must exist since G is connected).

Option 1: If the subgraph induced by C 2 \ {w} is connected, put:

C 1 := C 1 ∪ {w}, C 2 := C 2 \ {w}.
Option 2: If the subgraph induced by C 2 \ {w} is disconnected (w must be of degree 3), then denote by A, B the vertex-sets of two connected induced subgraphs of G on C 2 \ {w}. Depending on the size of A, the following update is executed.

• If |A| ≤ n -2 n-1 3 , put: C 1 := C 1 ∪ A ∪ {w}, C 2 := B. Notice that |C 1 | ≤ n -n-1 3 , {C 1 , C 2 }
is a connected partition and the size of C 1 strictly increased.

• If n -2 n-1 3 + 1 ≤ |A| ≤ n -n-1 3
, then notice that |A| ≥ n-1 3 and put:

C 1 := A, C 2 := V \ A. Obviously, {C 1 , C 2 } is a connected partition with n-1 3 ≤ |C i | ≤ n -n-1 3 , i = 1, 2, hence the Update Procedure halts. • If |A| > n -n-1 3
, put:

C 1 := C 1 ∪ B ∪ {w}, C 2 := A. Notice that |C 1 | < n-1 3 , {C 1 , C 2 }
is a connected partition and the size of C 1 strictly increased.

If |C 1 | ≥ n-1 3
after the execution of the option 1 or 2, then the Update procedure halts, otherwise the Update Procedure is repeated again.

By our construction, the partition {C 1 , C 2 } remains connected during each run of the Update procedure. Each time the Update procedure is executed, the size of C 1 strictly increases, hence the algorithm always terminates. At the end of the algorithm Proof. Let G = (V, E) be a connected graph of maximum degree 3 on n vertices, n ≥ 4, not isomorphic to a star. Due to Lemma 4.15, a connected partition

n-1 3 ≤ |C i | ≤ n -n-1 3 , i = 1,
{C 1 , C 2 } of V such that n-1 3 ≤ |C i | ≤ n -n-1 3 , i = 1, 2
, can be found in polynomial time. Let {C 1 , C 2 } be such a partition and notice that the vertices that do not satisfy the proportion condition can be split into two categories:

(A) if there exists i ∈ {1, 2} such that |C i | > n-1 3 in case n ≡ 1 mod 3 or |C i | > n-1 3
+ 1 in case n ≡ 1 mod 3, then all the vertices of degree 3 in C i with two out-neighbors, (B) if the partition is not balanced, then all the vertices of degree 2 in the larger part with one out-neighbor.

The algorithm starts with the initial partition {C 1 , C 2 } and then the Improvement Procedure (consisting in three stages) can be applied several times. The procedure transfers step-by-step all the vertices of degree at least 2 (with exactly one neighbor in its own part) between C 1 and C 2 or relabel the sets, until all the vertices satisfy the proportion condition. Since the initial partition is connected, transferring vertices with such a property never disconnects any part of the partition.

The Improvement Procedure: Stage 1 (Category (A) vertices) In this stage we handle vertices in C 2 of degree 3 with two out-neighbors by transferring them into C 1 , keeping the size of C 1 smaller than n -n-1

While |C 1 | < n -n-1 3
and there is a vertex u ∈ C 2 with two out-neighbors, update:

C 1 := C 1 ∪ {u}, C 2 := C 2 \ {u}.
While |C 2 | < n -n-1 3
and there is a vertex u ∈ C 1 with two out-neighbors, update:

C 2 := C 2 ∪ {u}, C 1 := C 1 \ {u}.
Notice that each iteration of Stage 2 decreases the cut-size by at least one.

The Improvement Procedure: Stage 3 (Category (B) vertices) If the partition is not balanced, the vertices of degree 2 with one out-neighbor must be transferred from the larger part to the smaller part.

If |C 1 | > |C 2 |, relabel C 1 := C 2 and C 2 := V \ C 1 . While |C 1 | < n
2 and there exists a vertex u of degree 2 in C 2 with one neighbor in C 1 , update:

C 1 := C 1 ∪ {u}, C 2 := C 2 \ {u}.
Each iteration of the while loop in Stage 3 doesn't increase the size of the cut. In the end of Stage 3 if the final partition doesn't have a 2-community structure then a vertex of the category (A) must exist in the partition. In that case, Stage 1 or 2 must be executed before entering Stage 3 again, hence the cut-size is decreased by at least one. Notice that Stage 3 may again create vertices of the category (A) even if they didn't exist before entering Stage 3.

It is easy to see that the algorithm always terminates. Each iteration of the while loop in Stage 1 (resp. Stage 2) decreases the cut-size by at least one. In Stage 3 each iteration of the while loop increases the size of the smaller part by at least one and halts before or when the partition is balanced. Following the construction, if the Improvement Procedure needs to be run again, it must first run through Stage 1 or 2 which decreases the cut-size by at least one. Moreover, the algorithm clearly runs in polynomial time.

Let's discuss the correctness of the algorithm. Suppose the algorithm terminates with the final partition {C 1 , C 2 }. Due to the conditions inside the algorithm, n-1

3 ≤ |C i | ≤ n -n-1 3 , i = 1, 2.
Initially, the partition is connected and remains so after each stage, hence the final partition is connected too. Moreover, each vertex of degree 1 necessarily satisfies the proportion condition since it must be in the same part as its neighbor. Now there are two options:

• If the final partition is balanced then all vertices of degree 2 and 3 may have at most one out-neighbor (otherwise the Improvement Procedure could be applied again), hence the final partition {C 1 , C 2 } is a 2-community structure due to Lemma 4.12(ii).

• If the final partition is not balanced, then the partition must have the properties described in Lemma 4.12(i) or (iii) (otherwise, one of Stages 1-2 could be applied again). Hence the final partition {C 1 , C 2 } is a 2-community structure.

Dense graphs

Now we investigate the problem of the existence and finding of a connected 2-community structure in dense graphs. We prove that any graph G = (V, E) of minimum degree |V | -3 has a connected 2-community structure which can be found in polynomial time.

Lemma 4.17. If the complement of the graph G is 2-colorable (using each color for at least 2 vertices), then G has a connected 2-community structure which can be found in polynomial time.

Proof. Let G = (V, E) be a graph such that its complement G is 2-colorable. Fix a 2coloring of G (with at least 2 vertices for each color) and define {C Proof. Let G be a graph of size n and of minimum degree (n -3) (except a star), n ≥ 4, and G be the complement of G. Notice that G is of degree at most 2. If G does not contain an odd cycle, then there exists a 2-coloring of G with at least 2 vertices for each color.

In such case, a connected 2-community structure can be found in polynomial time due to Lemma 4.17. Now let A be the union of all vertices belonging to an odd cycle in G and denote by B := V \A. G[A] is the union of p odd induced cycles with the vertex sets O 1 , . . . , O p , p ≥ 1. For each i,

1 ≤ i ≤ p, let v i be any vertex of O i and fix a 2-coloring of G[O i \{v i }]. Let O i,1 , O i,2 be the set of vertices corresponding to each color, obviously |O i,1 | = |O i,2 |. If |B| ≥ 2, take a 2-coloring of B and define a partition {B 1 , B 2 } of B (each part corresponding to a color) such that |B 1 | ≥ |B 2 | ≥ 1, otherwise B 1 := B, B 2 := ∅. Define C 1 := ∪ p i=1 (O i,1 ∪ {v i }) ∪ B 1 , C 2 := ∪ p i=1 O i,2 ∪ B 2 . Observe that |C 1 |, |C 2 | ≥ 2 (|C 2 | ≤ 1 is
only possible for a star or a graph with 3 vertices). Obviously, every such 2-colouring can be found in polynomial time. Finally we show that the partition {C 1 , C 2 } is a connected 2-community structure.

All vertices of C 2 satisfy the proportion condition in If c ≤ |V | -2, let C be the inclusion-wise maximal clique in G and take {C, V \ C} as a partition. Obviously, the size of both parts is at least 2. C is a clique, hence the proportion condition is trivially satisfied for all vertices in C. If a vertex u ∈ V \ C has a neighbor in C, then:

G since G[C 2 ] is a clique. For each i, 1 ≤ i ≤ p, all neighbors of v i in G[C 1 ] satisfy the proportion condition in G since they have all vertices of C 1 as neighbors. Moreover, the non-neighbor of v i in G[C 1 ] and v i itself satisfy the proportion condition in G since |C 1 | > |C 2 | implies that |C 1 |-2 |C 1 |-1 ≥ |C 2 |-1 |C 2 | . Observe that the partition {C 1 , C 2 } is connected. Obviously, G[C 2 ] is connected since G[C 2 ]
d in (u) |V | -c -1 ≥ (c-1).|V | c -(c -1) |V | -c -1 ≥ c -1 c ≥ d out (u) c ,
hence the proportion condition is satisfied for all vertices u ∈ V \ C with a neighbor in C.

The rest of vertices in V \ C trivially satisfy the proportion condition since they do not have a neighbor in C.

Now we prove that the partition

{C, V \ C} is connected, which is obviously true for G[C]. Let suppose that G[V \ C] be disconnected and A be the smallest connected component of G[V \ C]. Notice that |A| ≤ |V |-c 2 and let u ∈ A. Then (c-1)•|V | c ≤ d(u) ≤ |V |-c 2 + c -2 and hence |V | ≤ c(c-4) c-2 < c, which is impossible. Therefore, G[V \ C] is a connected subgraph.

Balanced 2-community structures

In this section we study complexity of the problems related to balanced 2-community structures. First, we discuss the hardness of the problem in general graphs. We prove that the Balanced Weak 2-community and Balanced 2-community problems are NP-complete. The latter result is contained as the main result in [START_REF] Estivill-Castro | On connected two communities[END_REF], an alternative shorter proof is presented in this section. Both NP-completeness results are extended to a connected balanced 2-community structure. Then, we investigate the problem in graphs of low edge density. We prove that every graph of maximum degree 3 has a balanced weak 2-community structure that can be found in polynomial time. The structural properties of low-degree graphs are crucial to obtain such a result. Finally, we prove that the problem is polynomial-time solvable for graphs with bounded treewidth.

General graphs

We focus on the problem of Balanced 2-community in general graphs. In [START_REF] Chlebíková | Approximating the maximally balanced connected partition problem in graphs[END_REF] it has been proved that finding a connected balanced partition without any additional constraint is an NP-complete problem in general graphs. We prove similar results for Balanced Weak 2-community and Balanced 2-community and their connected variants. To show that Balanced Weak 2-community is NP-complete, we use a reduction from the Balanced Co-Satisfactory Partition problem, proved to be NP-complete in [START_REF] Bazgan | Approximation of satisfactory bisection problems[END_REF].

The problems is defined as follow:

Balanced Co-Satisfactory Partition Input : A graph G = (V, E) on an even number of vertices. Question : Is there a balanced partition

{C 1 , C 2 } of V such that for every v ∈ V , d in (v) ≤ d out (v)? Theorem 4.21. Balanced Weak 2-community is NP-complete.
Proof. The problem is clearly in NP. In the following we define a polynomial-time reduction from Balanced Co-Satisfactory Partition to Balanced Weak 2-community.

Let G be a graph on an even number n of vertices as an instance of Balanced Co-Satisfactory Partition, and let G, the complement of G, be an instance of Balanced Weak 2-community. If G admits a balanced co-satisfactory partition {C 1 , C 2 } then {C 1 , C 2 } is also a weak 2-community. Suppose d in (v) ≤ d out (v) for every vertex v ∈ V (in the graph G). Let din (v) (resp. dout (v)) be the number of in-neighbors (resp. out-neighbors) of v in G. Then, the following holds din

(v) + 1 = n 2 -d in (v) ≥ n 2 -d out (v) = dout (v)
, which is the weak proportion condition for a balanced partition. Conversely, any balanced weak 2-community in G is a balanced co-satisfactory partition in G.

The proof of the NP-completeness of Balanced Co-Satisfactory Partition in [START_REF] Bazgan | Approximation of satisfactory bisection problems[END_REF] is based on the graphs G = (V, E), where V = F ∪ T ∪ V 0 with some additional properties: F and T are independent sets, there are no edges between T and V 0 , and there is a vertex f ∈ F that is not adjacent to any vertex of V 0 . Any balanced co-satisfactory partition {C 1 , C 2 } of V must have the following structure:

C 1 = F ∪ S and C 2 = T ∪ (V 0 \ S)
where S ⊆ V 0 . If G is an instance of Balanced Weak 2-community (constructed following the proof of Theorem 4.21), one can see that C 1 is connected since f is adjacent to all vertices in F ∪ S and C 2 is connected since T is a clique and every vertex of T is adjacent to every vertex of V 0 \ S. Hence we can conclude that even the connected version of Balanced Weak 2-community is NP-complete: Theorem 4.22. Connected Balanced Weak 2-community is NP-complete.

Estivill-Castro et al. [START_REF] Estivill-Castro | On connected two communities[END_REF] have shown that Balanced 2-community is NP-complete by constructing a reduction from a variant of the Clique problem. We propose a shorter alternative proof which is also valid for the Connected Balanced 2-community problem. The proof is based on the NP-complete problem Balanced Satisfactory Partition which was introduced by Bazgan et al. [START_REF] Bazgan | The satisfactory partition problem[END_REF] as follows:

Balanced Satisfactory Partition

Input : A graph G = (V, E) on an even number of vertices. Question : Is there a balanced partition

{C 1 , C 2 } of V such that for every v ∈ V , d in (v) ≥ d(v) 2 ?
It can be proved that these two problems are in fact equivalent when the number of vertices is even. Lemma 4.23. Let G = (V, E) be a graph with n vertices. Consider a partition {C 1 , C 2 } of V and v ∈ C 1 . Then the following assertions are equivalent:

1. d in (v) |C 1 |-1 ≥ d(v) n-1 2. dout(v) |C 2 | ≤ d(v) n-1 3. d in (v) |C 1 |-1 ≥ dout(v) |C 2 | Proof. (1) ⇔ (2) : d in (v) d(v) ≥ |C 1 |-1 n-1 ⇔ 1 -dout(v) d(v) ≥ n-|C 2 |-1 n-1 ⇔ 1 -n-|C 2 |-1 n-1 ≥ dout(v) d(v) ⇔ dout(v) d(v) ≤ |C 2 | n-1 (3) ⇔ (1) : d in (v) |C 1 |-1 ≥ dout(v) |C 2 | ⇔ d in (v) |C 1 |-1 ≥ d(v)-d in (v) n-|C 1 | ⇔ d in (v)[ 1 |C 1 |-1 + 1 n-|C 1 | ] ≥ d(v) n-|C 1 | ⇔ d in (v) d(v) ≥ |C 1 |-1 n-1
v ∈ V , d in (v) = n/2-1 n-1 d(v) if and only if d(v) = n -1. Proof. If d(v) = n -1, then clearly d in (v) = n 2 -1. Suppose now that d in (v) = n/2-1 n-1 d(v). Notice that (-2)( n 2 -1) + 1(n -1)
= 1 from which it can be easily shown that n 2 -1 and n -1 do not have common divisors. This implies that d(v) is a multiple of n -1. Thus, Proof. Suppose that G = (V, E) is a yes-instance of Balanced Satisfactory Partition. Hence there exists a balanced partition

d(v) = n -1.
{C 1 , C 2 } of V such that any vertex v ∈ V satisfies the condition d in (v) ≥ 1 2 d(v), which implies that d in (v) ≥ |C 1 |-1 2|C 1 |-1 d(v) = |C 1 |-1 n-1 d(v). Thus, G is a yes-instance of Balanced 2-Community.
Suppose now that G is a yes-instance of Balanced 2-Community. Hence there exists a balanced partition

{C 1 , C 2 } of V such that any vertex v ∈ V satisfies the con- dition d in (v) ≥ |C 1 |-1 |C 2 | d out (v) that is equivalent to d in (v) ≥ |C 1 |-1 n-1 d(v) using Lemma 4.23. According to Lemma 4.25, there is no vertex v such that d in (v) = |C 1 |-1 n-1 d(v). Now we need to show that for every vertex v ∈ V, d in (v) ≥ 1 2 d(v).
Suppose by contradiction that there exists a vertex v ∈ V that does not satisfy the inequality that is:

|C 1 | -1 n -1 d(v) < d in (v) < 1 2 d(v) First, notice that 1 2 d(v) -|C 1 |-1 n-1 d(v) = 1 2(n-1) d(v) < 1,
which means that there is at most one integer number between

|C 1 |-1 n-1 d(v) and 1 2 d(v). Moreover, d(v) cannot be even, since otherwise d(v)
2 would be a whole number and thus d in (v) could not be an integer number. Then d(v) is odd and let d(v) = 2p + 1 for some integer p. We arrive to a contradiction by showing that p < d in (v)

< p + 1 2 . Notice that d(v) < n -1 ⇒ d(v)-1
Balanced Satisfactory Partition has already been proved NP-complete in [START_REF] Bazgan | The satisfactory partition problem[END_REF], even if both parts are required to be connected. Moreover, the reduction used in [START_REF] Bazgan | The satisfactory partition problem[END_REF] does not construct a graph with vertices of degree n -1.

Thus we obtain a similar result as in [START_REF] Estivill-Castro | On connected two communities[END_REF] (the authors have mentioned in the proof that used technique works also in a connected case). Finally, it is interesting to notice that there exist graphs in which every 2-community structure is balanced (see Figure 4.9). Nevertheless, if we focus on a weak community, a balanced weak 2-community always exists in graphs of maximum degree 3, as it is shown in the following theorem. Theorem 4.30. Any graph of maximum degree 3 with at least 4 vertices has a balanced weak 2-community structure. Moreover, such a community structure can be found in polynomial time.

Proof. Let G = (V, E) be a connected graph of maximum degree 3. First notice that in any balanced partition of V , each vertex of degree 1 fulfils the weak proportion condition (even if its neighbor is not in its own part), and each vertex of degree 2 or 3, which has at least one neighbor in its own part, satisfies the weak proportion condition.

Therefore, the only vertices which may not satisfy the weak proportion condition are vertices of degree 2 or 3 which have no neighbor in their own part.

Consider any balanced partition {C 1 , C 2 } of G and repeat the following steps (S1)-(S2) until it is possible: (S1) If both parts contain a vertex of degree 2 or 3 that has no neighbor in its own part (say

v 1 ∈ C 1 , v 2 ∈ C 2 ), then update: C 1 := C 1 ∪ {v 2 }\{v 1 }, C 2 := C 2 ∪ {v 1 }\{v 2 }. (S2)
If there is only one partition that contains a vertex v of degree 2 or 3 that has no neighbor in its own part (without loss of generality suppose v ∈ C 1 ), then choose a vertex w ∈ C 2 such that w has at least one neighbor in C 1 and update:

C 1 := C 1 ∪ {w}\{v}, C 2 := C 2 ∪ {v}\{w}.
First notice that if case (S2) occurs, such a vertex w always exists since the graph is connected. Moreover, the partition remains balanced after each step (S1) or (S2). Besides, the cut size between the partitions C 1 and C 2 always decreases (by at least 2 in case (S1), by at least 1 in case (S2)) so after a finite number of iterations (bounded trivially by O(|V | 2 ), every vertex of degree 2 or 3 has at least one neighbor in its own part. Hence, the algorithm returns a balanced weak 2-community structure. Proof. Such result follows from [START_REF] Bazgan | Degree-constrained decompositions of graphs: Bounded treewidth and planarity[END_REF] where the t-Decomposition problem closely related to communities was studied. The input to the t-Decomposition problem is a graph G = (V, E), an integer-valued function t = t(n) such that 0 ≤ t(n) ≤ n for every n ∈ N, and two functions a, b :

V → N such that a(v), b(v) ≤ d(v), for all v ∈ V . The problem consists of deciding if there is a partition {V 1 , V 2 } of V with |V 1 | = t(|V |) such that d G[V 1 ] (v) ≥ a(v) for every v ∈ V 1 and d G[V 2 ] (v) ≥ b(v) for every v ∈ V 2 .
In order for {V 1 , V 2 } to be a balanced 2-community structure with

|V 1 | ≥ |V 2 |, every v ∈ V 1 must satisfy the condition d G[V 1 ] (v) n/2 -1 ≥ d(v)-d G[V 1 ] (v) n/2
and analogously for every

v ∈ V 2 must hold d G[V 2 ] (v) n/2 -1 ≥ d(v)-d G[V 2 ] (v) n/2
. Thus, Balanced 2-community can be condidered as the t-Decomposition problem for selected values of the functions t, a, b. The conditions for Balanced 2-community can be transformed to the conditions of the t-Decomposition problem where t

(n) = n 2 , a(v) = b(v) = n/2-1 n-1 d(v) for n even and a(v) = d(v)/2 , b(v) = (n-1)/2-1 n-1 d(v)
for n odd. Since the t-Decomposition problem was proved to be polynomial-time solvable for bounded treewidth in [START_REF] Bazgan | Degree-constrained decompositions of graphs: Bounded treewidth and planarity[END_REF], we can conclude the same result for the Balanced 2-community problem.

Notice that the result cannot be extended to a connected case for all graphs, see a tree on Figure 4.11 as a counterexample.

About graphs without 2-community structures

We know that any graph that is a star does not contain any community structure. We investigate if there are other graphs without any 2-community structure. By enumerating, using the computer, all graphs with n vertices starting with n = 4, we found that the minimum integer n for which there are graphs (not isomorphic to stars) that do not contain any 2-community structures is n = 10. The planar graph showed in Figure 4.12 has 10 vertices and has no 2-community structure. We were able to generalize those counter-example in a infinite class of graphs in which there is no 2-community structure. Definition 4.33. Let G be a class of the graphs such that for G = (V, E) ∈ G:

• V = W 1 ∪ W 2 ∪ {w, x,
y, z}, where W 1 , W 2 are cliques of the same size k, k ≥ 3, and {x, y, w} is a clique of size 3;

• w is adjacent to all vertices in W 1 ∪ W 2 ,
• z is a pendant vertex adjacent to the vertex y,

• 1 ≤ d W 1 (x) = d W 2 (x) ≤ k -1 and 2 ≤ d W 1 (y) = d W 2 (y) ≤ k -1, • |W i ∩ (N (x) ∪ N (y)) | > 3k k+3
for each i ∈ {1, 2}, and furthermore there exist vertices

α, β ∈ W 1 ∪ W 2 such that α ∈ N (y) \ N (x), and β ∈ N (x) ∩ N (y),
• there is no edge between the vertex sets W 1 and W 2 . Proof. Firstly, notice that there is no 2-community structure {A, B} in G such that |A| = 1 or |B| = 1. Wlog, suppose by contradiction that A = {v} for some vertex v, and notice that the neighbor of v in B must be a universal vertex in order to be satisfied. Since G does not contain a universal vertex, there is no 2-community structure {A, B} in G with |A| = 1 or |B| = 1. Hence, assume that |A|, |B| ≥ 2.

Observe that the vertex z is satisfied if and only if it belongs to the same community as the vertex y, hence without loss of generality we assume that y, z ∈ B. In addition, the vertex w has degree |V | -2 and is not connected to z ∈ B. Hence, necessarily w ∈ A. Now we prove that for any partition {A, B} of V , where w ∈ A and y, z ∈ B, there is at least one vertex which is not satisfied, hence there is no 2-community structure in G.

For any partition {A, B} of V , we denote by A i and B i the sets A ∩ W i and B ∩ W i , respectively, for i ∈ {1, 2}. In the first case, we suppose that B 1 or B 2 is empty. In the second case, we assume that B 1 and B 2 are not empty.

Case 1:

B 1 = ∅ or B 2 = ∅ Suppose first that B 1 = ∅ and B ⊆ {x, y, z} ∪ W 2 .
• If B 2 = ∅, we have two possibilities:

-if x ∈ B, then B = {x, y, z} and β ∈ A is not satisfied since d A (β) |A|-1 = k 2k < 2 3 = d B (β) |B| ; -if x ∈ A, then B = {y, z} and α ∈ A is not satisfied since d A (α) |A|-1 = k 2k+1 < 1 2 = d B (α) |B| . • If B 2 = ∅ and B 2 = W 2 , -Case x ∈ B. * If there exists u ∈ A 2 such that u ∈ N (x) ∪ N (y), then if u is satisfied then: |A 2 | k + |A 2 | = d A (u) |A| -1 ≥ d(u) |V | -1 ≥ k + 1 2k + 3 ⇒ |A 2 | ≥ k 2 + k k + 2 > k -1 , which is not possible since |A 2 | ≤ k -1. * Otherwise, for all u ∈ A 2 , u /
∈ N (x) ∪ N (y). Hence, for any u ∈ A 2 , if u is satisfied then:

|A 2 | k + |A 2 | = d A (u) |A| -1 ≥ d(u) |V | -1 = k 2k + 3 ⇒ |A 2 | ≥ k 2 k + 3 .
Due to our assumptions about the graph,

|W 2 ∩ (N (x) ∪ N (y)) | > 3k k+3 . Thus, k -3k k+3 > |W 2 \ (N (x) ∪ N (y))| ≥ |A 2 | ≥ k 2 k+3 which implies k > k, a contradiction. -Case x ∈ A. Let u ∈ A 2 . * If u ∈ N (y) ∩ N (x)
, then if u is satisfied we have:

|A 2 | + 1 k + |A 2 | + 1 = d A (u) |A| -1 ≥ d(u) |V | -1 = k + 2 2k + 3 , which implies |A 2 | ≥ k -1 k+1 ,
|A 2 | + 1 k + |A 2 | + 1 = d A (u) |A| -1 ≥ d(u) |V | -1 = k + 1 2k + 3 ⇒ |A 2 | ≥ k 2 -2 k + 2 > k -2 .
Since assuming that there is a vertex in A 2 ∩ N (y) leads to a contradiction (see previous cases), we can assume that A 2 ∩ N (y) = ∅. Then, since

d W 2 (y) ≥ 2, then |W 2 \ N (y)| ≤ k -2. Thus k -2 ≥ |A 2 | > k -2, a contradiction. * If u / ∈ N (x) ∪ N (y),
d B (y) |B|-1 < d B (y)+1 |B| = d A (y) |B| = d A (y)
|A| , thus y is not satisfied.

We conclude that if there is a 2-community structure in G, then B 1 = ∅. The case B 2 = ∅ is similar and we also conclude that if there is a 2-community structure in G, B 2 = ∅.

Case 2: B 1 , B 2 = ∅.
Without loss of generality, we suppose |B 1 | ≤ |B 2 |. Let u ∈ B 1 and suppose that u is satisfied in the partition {A, B}. We prove that in all cases, if u is satisfied then it implies a contradiction with

|B 1 | ≤ |B 2 |. • If x ∈ A -If u ∈ N (x) ∩ N (y): |B 1 | |B 1 | + |B 2 | + 1 = d B (u) |B| -1 ≥ d(u) |V | -1 = k + 2 2k + 3 ⇒ |B 1 | > |B 2 | , a contradiction, hence u is not satisfied. -If u ∈ N (x) \ N (y), we have d B (u) = |B 1 | -1 and d(u) = k + 1 and similarly we obtain |B 1 |•(k+2) ≥ |B 2 |•(k+1)+(k+4) ≥ |B 2 |•(k+1)+(|B 2 |+4) > |B 2 |•(k+2), a contradiction since |B 1 | ≤ |B 2 |. -If u ∈ N (y) \ N (x), we have d B (u) = |B 1 | and d(u) = k + 1 and similarly we obtain |B 1 |•(k+2) ≥ |B 2 |•(k+1)+(k+1) ≥ |B 2 |•(k+1)+(|B 2 |+1) > |B 2 |•(k+2), a contradiction since |B 1 | ≤ |B 2 |. -If u / ∈ N (x) ∪ N (y), we have d B (u) = |B 1 | -1 and d(u) = k and similarly we obtain |B 1 | • (k + 3) ≥ |B 2 | • k + 3(k + 1) ≥ |B 2 | • k + 3(|B 2 | + 1) > |B 2 | • (k + 3), a contradiction since |B 1 | ≤ |B 2 |. • If x ∈ B -If u ∈ N (x) ∩ N (y): |B 1 | + 1 |B 1 | + |B 2 | + 2 = d B (u) |B| -1 ≥ d(u) |V | -1 = k + 2 2k + 3 ⇒ |B 1 | > |B 2 | , a contradiction, hence u is not satisfied. -If u ∈ N (x) \ N (y) or u ∈ N (y) \ N (x), we have d B (u) = |B 1 | and d(u) = k + 1 and similarly we obtain |B 1 | • (k + 2) ≥ |B 2 | • (k + 1) + 2(k + 1) ≥ |B 2 | • (k + 1) + 2(|B 2 | + 1) > |B 2 | • (k + 3), a contradiction since |B 1 | ≤ |B 2 |. -If u / ∈ N (x) ∪ N (y), we have d B (u) = |B 1 | -1 and d(u) = k and similarly we obtain |B 1 | • (k + 3) ≥ |B 2 | • k + 4k + 3 ≥ |B 2 | • k k+3 + 4 • |B 2 | + 3 > |B 2 | • (k + 4), a contradiction since |B 1 | ≤ |B 2 |.
On the other hand, any graph in G has {W 1 ∪{x, w}, W 2 ∪{y, z}} as a balanced weak 2community structure. Thus, the existence of graphs in which there is no weak 2-community structure remains open for all graphs.

Conclusions

The following overview summarises the results achieved in this chapter. All considered graphs are of size at least 4 and are not stars. The problem of finding a 2-community structure in a graph has been studied in the following graph classes.

(i) trees:

-a connected 2-community structure exists and can be found in linear time (Theorem 4.6), -there are trees with a balanced 2-community structure, but without a connected balanced weak 2-community structure (Remark 4.31), (ii) graphs of maximum degree 3:

-a connected 2-community structure exists and can be found in polynomial time (Theorem 4. where c is the size of an inclusion-wise maximal clique in the graph: -a connected 2-community structure exists and can be found in polynomial time (Theorems 4. 18, 4.19, 4.20) (iv) graphs of bounded tree-width:

-there are graphs without a balanced 2-community structure (Remark 4.29), but to decide whether such a structure exists and if it exists, find it, can be done in polynomial time (Remark 4.32)

Estivill-Castro et al. [START_REF] Estivill-Castro | On connected two communities[END_REF] proved that the problem of finding a balanced 2-community structure is NP-complete in general graphs. In Section 4.4 it has been showed that the same result also holds for a weak community, even with additional constraint of connectivity for both parts. It also has been presented a shorter proof of the known NP-complete result for a balanced 2-community structure in general graphs based on an alternative definition of community structure [START_REF] Bazgan | The satisfactory partition problem[END_REF], which also implies NP-completeness for a connected balanced 2-community structure.

In case of Balanced 2-Community the situation is different. Any graph of maximum degree 3 has a balanced weak 2-community structure, while there are graphs without a balanced 2-community structure within the same class. Computationally speaking, finding a balanced weak 2-community structure can be done in polynomial time in graphs of maximum degree 3 while the Balanced 2-Community problem is NP-complete in general graphs just as its weak version. The results are similar for connected 2-community structures.

Finally, we found a family of graphs that do not contain any 2-community structure. Finding other families of graphs that satisfy this property could help to distinguish graphs that contain 2-community structures and the other ones. On the other hand, our family of graphs always have a balanced weak 2-community structure.

In addition, in order to get a better understanding of community structures, there are other interesting problems left open, as to extend 2-community results to other graph classes, to characterize graph classes where the existential and complexity results for 2community and weak 2-community problems and their connected versions are different or to generalize the results to k-communities for a fixed k, k ≥ 3.

Introduction

As we saw in Chapter 4, there exist graphs in which there is no 2-community structure. In this way, it is interesting to consider a relaxation of the definition by accepting that one of the two parts may not fulfill the proportion condition. In this way, we investigated finding a community of maximum size.

In this chapter, we use the definition of a community of Olsen [START_REF] Olsen | A general view on computing communities[END_REF] i.e. a community is defined as a subset C of vertices such that each vertex of C has a greater proportion of neighbors in C than outside of C. We study the problem of, given a graph, finding a community of maximum size. Section 5.2 gives notations that we use in this paper. Section 5.3 discuss the NP-hardness of the problem. Section 5.4 gives several results about the approximation of this problem. We investigate the co-NP-hardness of deciding if a community is inclusion-wise maximal in Section 5.6. We discuss the linear time solvability of the problem in some graph classes, and in particular in Hamiltonian cubic graphs, in Section 5. 5. Conclusions and open problems are given in Section 5.7.

Preliminaries

In this chapter all considered graphs are simple, undirected and connected. Let G = (V, E) be a graph, C ⊂ V a subset of vertices and v ∈ V a vertex.

For a given graph G = (V, E), Olsen ([133]) defined a 2-community structure as a partition {C 1 , C 2 } of V such that each part has at least two vertices and each vertex has a greater proportion of neighbor in its part than in the other part, i.e. for each vertex in

C i , i ∈ {1, 2}, d C i (v) |C i |-1 ≥ d C i (v) |C i | .
In this chapter, we investigate a variant consisting in finding only one community (in the sense that the previous condition only need to be fulfilled for vertices of one part of the partition) of maximum size. Such condition will still be called proportion condition throughout this chapter.

Definition 5.1. Given a graph

G = (V, E), a community is a subset of vertives C ⊂ V , C = V , such that |C| ≥ 2 and for each vertex u ∈ C, d C (u) |C| -1 ≥ d C (u) |C| . ( 5.1)
If a vertex u ∈ C respects the latter proportion condition, we say u is satisfied (in C).

Notice that since we are looking for a community of maximum size, a community of size less than 2 is not worth of interest. Thus, we can derive that the proportion condition is equivalent to

|C| • d C (u) ≥ (|C| -1) • d C (u)
, that we also use in the chapter.

Observe that the induced subgraph of a community may either be connected or not. We study both cases and talk about connected community when the subgraph induced by the community is connected.

We define our main problem Max Community as follows:

Max Community

Input: A graph G = (V, E). Output: A community in G of maximum size. I Lemma 4. Let G = (V, E) be a connected graph not isomorphic to a star and let

G Õ = (V Õ , E Õ ) = (G). Let C 1 µ V Õ be a community in G Õ . Then there exists a community C 2 in G Õ such that |C 2 | Ø |C 1 | and M fi {z 1 , z 2 } ™ C 2 .
Moreover, C 2 can be found in polynomial time.

Proof. Firstly, we claim that N * C 1 . We denote by C 1 := V Õ \ C 1 the set of vertices which are not in the community C 1 . To prove a contradiction, consider the two following cases:

if

C 1 = N , since G Õ [N ]
is an independent set, then any vertex u oe C 1 has d C 1 (u) = 0 and d C 1 (u) > 0; hence u does not satisfies Eq. ( 1) and

C 1 is not a community; if N µ C 1 , then C 1 is a subset of the clique M fi {z 1 , z 2 }; it means any vertex u oe M fi {z 1 , z 2 } fl C 1 has d C 1 (u) = |C 1 | and d C 1 (u) < |C 1 | ≠ 2, thus |C 1 | • d C 1 (u) < |C 1 | • (|C 1 | ≠ 2) < (|C 1 | ≠ 1) • |C 1 | = (|C 1 | ≠ 1) • d C 1 (u) ,
hence v does not satisfies Eq. ( 1) and C 1 is not a community. Thus, we can consider that N * C 1 . Now, let

C 2 := C 1 fi M fi {z 1 , z 2 } and C 2 := V Õ \ C 2 . Notice that C 2 ™ N and that a vertex u oe C 1 fl N is satisfied in C 2 , since d C 2 (u) = 0. Obviously, z 1 and z 2 are satisfied in C 2 .
Let e oe M be a vertex not satisfied in C 2 . Hence, for all e oe M which is not satisfied in C 2 , transfer a vertex u oe N , non adjacent to e, from C 2 to C 2 . Notice that for any

f oe M fl C 1 , d C 2 (f ) Ø d C 1 (f ) and d C 2 (f ) = d C 1 (f ), hence f is satisfied in C 2 .
G = (V , E ) = Γ(G). Let C 1 ⊂ V be a community in G . Then there exists a community C 2 in G such that |C 2 | ≥ |C 1 | and M ∪ {z 1 , z 2 } ⊆ C 2 . Moreover, C 2 can be found in polynomial time.
Proof. Firstly, we claim that N is not included in C 1 . We denote by C 1 := V \ C 1 the set of vertices which are not in the community C 1 . To prove a contradiction, consider the two following cases:

• if C 1 = N , since G [N ] is an independent set, then any vertex u ∈ C 1 has d C 1 (u) = 0
and d C 1 (u) > 0; hence u does not satisfies the proportion condition and C 1 is not a community;

• if N ⊂ C 1 , then C 1 is a subset of the clique M ∪ {z 1 , z 2 }; it means any vertex u ∈ M ∪ {z 1 , z 2 } ∩ C 1 has d C 1 (u) = |C 1 | and d C 1 (u) < |C 1 | -2, thus |C 1 | • d C 1 (u) < |C 1 | • (|C 1 | -2) < (|C 1 | -1) • |C 1 | = (|C 1 | -1) • d C 1 (u) ,
hence v does not satisfies the proportion condition and C 1 is not a community.

Thus, we can consider that N is not included in

C 1 . Now, let C 2 := C 1 ∪ M ∪ {z 1 , z 2 } and C 2 := V \ C 2 . Notice that C 2 ⊆ N and that a vertex u ∈ C 1 ∩ N is satisfied in C 2 , since d C 2 (u) = 0. Obviously, z 1 and z 2 are satisfied in C 2 .
Let e ∈ M be a vertex not satisfied in C 2 . Hence, for all e ∈ M which is not satisfied in C 2 , transfer a vertex u ∈ N , non adjacent to e, from C 2 to C 2 . Notice that for any We can now prove the main theorem: Theorem 5.5. Max Community is NP-hard, even on split graphs.

f ∈ M ∩ C 1 , d C 2 (f ) ≥ d C 1 (f ) and d C 2 (f ) = d C 1 (f ), hence f is satisfied in C 2 . Since e
Proof. We consider the decision variants of the problems Max Community and Max Independent Set. Let G = (V, E) be a connected graph not isomorphic to a star and let G = (V , E ) := Γ(G) and k ∈ {1, . . . , |V | -1}. We claim that there is an independent set of size at least k in G if and only if there is a community of size at least

|M | + 2 + k in G .
Let R be a independent set of G of size at least k. In G , we define Notice that there exists graphs on which a community of maximum size is not connected, even if the graph is a cubic graph (Figure 5.2) or a caterpillar (Figure 5.3).

C := M ∪{z 1 , z 2 }∪R and C := V \ C. First, note that R ⊆ N thus C = N \ R. The vertices in C ∩ N ∪ {z 2 ,

Non-approximability

The previous reduction from Theorem 5.5 is actually an L-reduction which allow us to establish its APX-hardness. Proposition 5.6. Max Community is APX-hard, even on split graphs. Proof. We prove that the reduction from Theorem 5.5 is an L-reduction when we reduce Max Independent Set on cubic graphs to Max Community. Let I be an instance of Max Independent Set on the cubic graph G = (V, E) and we construct an instance I of Max Community defined on the graph G = (V , E ) = Γ(G).

We recall that since a cubic graph is 4-colorable, opt(I) Since Max Independent Set is APX-hard on cubic graphs [7], we conclude that Max Community is APX-hard on split graphs.

≥ |V | 4 . Since a cubic graph contains exactly 3|V | 2 edges we have opt(I ) = 2 + |E| + opt(I) = 2 + 3|V | 2 + opt(I) ≤ 2 + 3|V | 2 + |V | ≤ 2 + 5|V | 2 ≤ 2 +

Corollary 5.7.

There is no ptas for Max Community unless P=NP.

In the next section, we discuss some positive results for approximation.

Positive results for approximation

We show that Max Community is polynomial-time 2-approximable, which establishes its APX-completeness. We also give a polynomial-time 2•(∆-1)+1 ∆ -approximation algorithm, where ∆ is the maximum degree of the graph, using an upper-bound of the size of a community.

We design a polynomial-time algorithm that generates, given a graph G = (V, E), a community of size at least |V | 2 .

Lemma 5.8. Let G = (V, E) be a graph with n vertices. Let C ⊂ V be a set of vertices of size n 2 or n 2 + 1 for n even, and

n+1 2 for n odd. If C is not a community in G, then there exists a vertex u ∈ C such that d C (u) < d C (u) if |C| ≤ n+1 2 , and d C (u) ≤ d C (u) otherwise.
Proof. Let C ⊂ V such that C is not a community. Hence, there exists a vertex u ∈ C such that the proportion condition is not satisfied and thus

|C| • d C (u) < (|C| -1) • d C (u) (*). • If |C| = n 2 + 1 (n even), assume by contradiction that d C (v) > d C (v), for each vertex v ∈ C. In particular inequality (*) becomes ( n 2 -1) • (d C (u) + 1) < n 2 • d C (u) which is true if and only if d C (u) ≥ n 2 . Thus d(u) = d C (u) + d C (u) > n, which is not possible. • If |C| = n 2 , assume by contradiction that d C (v) ≥ d C (v), for each vertex v ∈ C. In particular inequality (*) becomes n 2 • d C (u) < ( n 2 -1) • d C (u) ≤ n 2 • d C (u)
, which contradicts our assumption. Theorem 5.9. Given a connected graph on n vertices, a community of size at least n 2 vertices can be constructed in linear time.

Proof. We apply Algorithm 1 on G and prove that the algorithm terminates.

Algorithm 1: Find a community of size at least n 2 .

Input: G = (V, E) a graph with n vertices. Output: C ⊂ V a community in G. Let C ⊂ V with |C| = n 2 ; while C is not a community do Let u ∈ C such that d C (u) -d C (u) is maximum; C := C ∪ {u};
return C;

• Case 1: n is odd. Notice that at the end of each loop, the set C is modified without changing its size |C| = n+1 2 . If C is not a community, then according to Lemma 5.8 there is a vertex v ∈ C for which d C (v) < d C (v). Therefore, the vertex u chosen within the loop has d C (u) -d C (u) > 0. Thus the size of the cut between C and C decreases after each loop and the algorithm terminates. We show in the following how the calculation of the approximation ratio can be improved with regard to the maximum degree of the graph. Lemma 5.10. Let G = (V, E) be a connected graph and C ⊂ V be a community in G.

Then |C| ≤ |V |•(∆(G)-1)+1 ∆(G) . Proof. Let v be a vertex of C with at least one neighbor in C = V \ C (such vertex exists since G is connected). Since C is a community, v fulfills the proportion condition, that is ∆(G)-1 |C|-1 ≥ d C (v) |C|-1 ≥ d C (v) |C| ≥ 1 |V |-|C| which implies that |C| ≤ |V |•(∆(G)-1)+1 ∆(G) . Since |C| is an integer, we obtain |C| ≤ |V |•(∆(G)-1)+1 ∆(G) . Proposition 5.11. Max Community is polynomial-time 2•(∆(G)-1)+1 ∆(G)
-approximable.

Proof. Let G = (V, E) be a graph, C be a solution given by Algorithm 1 and opt(G) denote the size of a community of maximum size in G. According to Lemma 5.10 we have opt(G)

≤ |V |•(∆(G)-1)+1 ∆(G)
. Thus we obtain in the cycle. Without loss of generality, we assume that such graphs have a Hamiltonian cycle (0, 1, ..., |V | -1, 0). To avoid tedious notations, we may use i ∈ Z to refer to the vertex (i (mod n)).

|C| ≥ |V | 2 ≥ ∆(G) 2•(∆(G)-1)+1 • |V |•(∆(G)-1)+1 ∆(G) ≥ ∆(G) 2•(∆(G)-1)+1 • opt(G).
We introduce two essential notions that will be used throughout the proof. , then:

• a good shift denotes a set

P := {u, u + 1, u + 2, . . . , u -k -1} for some u ∈ V , such that d P (u) = d P (u -k -1) = 2.
• an almost good shift denotes a set P := {u, u + 1, u + 2, . . . , u -k} for some u ∈ V , such that d

P (u) = d P (u -k) = 2.
Notice that a good shift P is a community of size 2•|V |+1 3 since any vertex of P has at least two neighbors in P due to the structure of the graph. An almost good shift P is of size 2•|V |+1 3 + 1, and thus is not a community due to Lemma 5.10, but has the property that any vertex of P has at least two neighbors in P . Now, we prove that if G does not contain a good shift, then G contains an almost good shift P and, in such case, it is always possible to find a vertex v ∈ P such that P \ {v} is a community of size , then:

• for each vertex u ∈ V , c(u) denotes the vertex v ∈ V such that uv ∈ E and |u-v| > 1; • L := {u ∈ V : c(u) ∈ {u -k, u -k + 1, , . . . , u -2}}; • R := {u ∈ V : c(u) ∈ {u + 2, u + 3, . . . , u + k}};
We derive some observations from these definitions. For a given Hamiltonian cubic graph G = (V, E) and u ∈ V , notice that u ∈ L if and only if c(u) ∈ R, and symmetrically. This particularly implies that |L| = |R| ≤ |V | 2 . Moreover, notice that for a vertex u ∈ L, the set P := {u, u + 1, • • • , u -k -1} cannot be a good shift, since d P (u) = 1. Symmetrically, if u ∈ R, the set P := {u + k + 1, u + k + 2, . . . , u -1, u} cannot be a good shift, since d P (u) = 1. These observations are summed up in the following lemma. Lemma 5.17.

Let G = (V, E) be a Hamiltonian cubic graph, k := |V |-1 3 and u ∈ V . If u / ∈ L and (u-(k+1)) / ∈ R, then the set {u, u+1, . . . , u-(k+1)-1, u-(k+1)} is a good shift. Symmetrically, if u / ∈ R and (u + k + 1) / ∈ L, then the set {u + k + 1, u + k + 2, . . . , u -1, u} is a good shift.
Proof. The proof is straightforward. Since u / ∈ L and (u -

(k + 1)) / ∈ R, we have d P (u) = d P (u-(k+1)) = 2, where P := {u, u+1, • • • , u-(k+1)}. The other case is symmetrical.
A natural consequence of Lemma 5.17 is that if a Hamiltonian cubic graph G has no good shift, then we can define a whole set of vertices that must be either in L or in R. In that way, we define the following:

Definition 5.18. Given a Hamiltonian cubic graph G = (V, E) and a vertex u ∈ V , we define < u >:= {u + δ • (k + 1) : δ ≥ 1, δ ∈ N} with k := |V |-1 3 .
Applying Lemma 5.17 recursively on a graph without any good shift, we obtain Corollary 5.19.

Corollary 5.19. Let G = (V, E) be a Hamiltonian cubic graph without a good shift and u ∈ V . Therefore:

• if u / ∈ R then < u >⊆ L and also u ∈ L, • if u / ∈ L, then < u >⊆ R and also u ∈ R, • |L| = |R| = |V | 2 . Proof. First notice that since u + |V | • (k + 1) = u, we have u ∈< u >. If u /
∈ R, we can apply Lemma 5.17 recursively and derive that < u >= {u

+ δ • (k + 1) : δ ≥ 1, δ ∈ N} ⊆ L, and since u ∈< u >, u ∈ L. Symmetrically, if u / ∈ L, then {u -δ • (k + 1) : δ ≥ 1, δ ∈ N} ⊆ R. Since u -δ • (k + 1) = u-δ•(k+1)+|V |•(k+1) = u+δ•(|V |-1)•(k+1), we have {u-δ•(k+1) : δ ≥ 1, δ ∈ N} =< u >. Thus, < u >⊆ R, and since u ∈< u >, u ∈ R.
This implies that for any vertex

u ∈ V , u ∈ L or u ∈ R. Finally, since u ∈ L if and only if c(u) ∈ R and u ∈ R if and only if c(u) ∈ L, then it is obvious that |L| = |R| = |V |
2 . Now, given a Hamiltonian cubic graph G = (V, E) that does not contain any good shift, we show that V can be partitioned into sets < i > with i ∈ {0, 1, • • • , gcd(|V |, k + 1) -1}, with gcd(|V |, k + 1) the greatest common divisor of |V | and k + 1. This partition will be hence 5.20). According to Corollary 5.19, < i >⊆ L or < i >⊆ R for any i ∈ {0, 1, 2}, thus |R| = |L|, which is not possible.

V = L or V = R, which is impossible. If d = 3, then |V | = < 0 > ∪ < 1 > ∪ < 2 > (Lemma
From Lemma 5.20 and Lemma 5.21, if a Hamiltonian cubic graph G = (V, E) has no good shift, then V can be written as

V = < 0 > ∪ < 1 > ∪ < 2 > ∪ < 3 > (we may have < 0 > = < 2 > and < 1 > = < 3 >).
Hence those graphs can be split into two categories:

• type RLRL: for any vertices i, i + 1 with i ∈ V , we have i ∈ L and i + 1 ∈ R, or i ∈ R and i + 1 ∈ L. In this case, we always assume without loss of generality that

R = < 0 > ∪ < 2 > and L = < 1 > ∪ < 3 >.
• type RRLL: there exist two vertices i, i

+ 1 with i ∈ V such that i, i + 1 ∈ L or i, i + 1 ∈ R.
In this case, we always assume without loss of generality that

R = < 0 > ∪ < 1 > and L = < 2 > ∪ < 3 >.
We can finally show that, given a Hamiltonian cubic graph G, if G has no good shift, then there exist an almost good shift P in G (Lemma 5.23) and a vertex v ∈ P such that P \ {v} is a community (Proposition 5.24 and Theorem 5.25). . Then there exist an almost good shift We suppose that gcd(k + 1, |V |) ∈ {2, 4}. If G contains a good shift, then the proof is done. Hence, we assume that G has no good shift. We prove that given an almost good shift P , there exists a vertex u * ∈ P such that P \ {u * } is a community. Observe that such vertex u * exists if and only if c(u * -1), c(u * + 1) ∈ P , and either c(u * ) ∈ V \ P or d P (c(u * )) = 3.

P := {u, u + 1, u + 2, • • • , u -k}, u ∈ V , of size |V | -k + 1 such that d P (v) ≥ 2 for all v ∈ P , and u + 1 ∈ L and u -k -1 ∈ R.
• If G is of type RLRL, then R = < 0 > ∪ < 2 > and L = < 1 > ∪ < 3 >.
According to Lemma 5.23, the set

P := {0, 1, 2, • • • , -k} is an almost good shift and 0 ∈ R, 1 ∈ L. Since 2 ∈ R and 4 ∈ R, then c(2) ∈ P and c(4) ∈ P . If c(3) = 0, then c(3) ∈ V \ P since 3 ∈ L. Thus, P \ {3} is a community of size 2•|V |+1 3 . Symmetrically, if c(-k -3) = -k, then c(-k -3) ∈ V \ P since 3 ∈ R. Thus, P \ {-k -3} is a community of size 2•|V |+1 3 . On the other hand, if c(3) = 0 and c(-k -3) = -k, then c(k -1) = -k and c(k -1) ∈ P . Moreover, since k -3 ∈ R then c(k -3) ∈ P . Therefore, c(k -2) ∈ V \ or d P (c(k -2)) = 3 (since k ≥ 7, k -2 = 3 and c(k -2) = 0). Thus, P \ {k -2} is a community of size 2•|V |+1 3 . • If G is of type RRLL, then R = < 0 > ∪ < 1 > and L = < 2 > ∪ < 3 >. According to Lemma 5.23, the set P := {1, 2, • • • , -k + 1} is an almost good shift and 1 ∈ R, 2 ∈ L, -k ∈ R, -k + 1 ∈ L. Since k + 1 ∈ < 0 > and k + 2 ∈ < 1 >, we necessarily have k -1, k ∈ L and k + 1, k + 2 ∈ R. In this case, notice that since k ≥ 7, {k -3, k -2, k -1} ∈ P . Moreover, k -3, k -2 ∈ R,

Extension of a vertex subset into a community

Olsen proved that deciding whether a given vertex subset can be extended into a community structure in a graph is NP-complete [START_REF] Olsen | A general view on computing communities[END_REF]. In this section we prove that the same result holds for a community, i.e. to answer whether a given subset of vertices of a graph can be extended into a community is NP-complete, even on bipartite graphs.

Community Extension

Input: A graph G = (V, E), a set S ⊂ V in G. Question: Does it exist C ⊂ V such that S ⊂ C and C is a community in G? Lemma 5.27. Let m, n and k be positive integers such that 1 ≤ k < n -1 ≤ m and

:= m • (n -k -1) -k + 1. Then +k-1 m+ +k-1 = n-k-1 n-k . Proof. (n -k) • ( + k -1) = (n -k -1) • ( + k -1) + + k -1 = (n -k -1) • ( + k + 1) + m • (n -k -1) = (n -k -1) • (m + + k + 1) .
Definition 5.28. Let G = (V, E) be a graph not isomorphic to a star with n vertices and m edges and k ≥ 2 be an integer. We define Γ such that the graph G = (V , E ) = Γ (G) is as follows (see Figure 5.5 for an illustration): • for all e ∈ M and all u ∈ N , the edge (e, u) ∈ E if and only if u / ∈ e;

• V := L∪M ∪N ,
• for all e ∈ M and all v ∈ L, the edge (e, v) ∈ E ;

Notice that in Definition 5.28, G is bipartite as there are edges only between M and L ∪ N . Obviously, the construction can be done in polynomial time.

d C (e) |C| -1 ≥ + k -1 m + + k -1 ≥ + k -1 m + + k -1 = n -k -1 n -k ≥ n -k -1 n -k ≥ d C (e) |C| ,
we conclude that C is a community in G .

Let C be a community in G such that L ∪ M ⊂ C, L ∪ M = C. We claim that R := C ∩ N is an independent set of G of size at least k. Notice that since L ∪ M ⊂ C and L ∪ M = C, then R is not empty. As it follows from Definition 5.28, a vertex e ∈ M is not adjacent to exactly two vertices in N . Let u and v denote such two vertices. Since C is a community, the vertex e is satisfied if and only if at most one of u and v is in C. Thus at most one of the two endpoints u and v of the edge e = (u, v) ∈ E is in R, hence R is an independent set. Now we prove that

|R| = k ≥ k. Let u ∈ R and f ∈ M such that u ∈ f in G, then d C (f ) ≥ n -k -1. If d C (f ) = n -k then f is not satisfied in C. Therefore, d C (f ) = n -k -1. Assume by contradiction that k < k. Since C is a community and |C| > 1, we have d C (f ) |C| -1 ≥ d C (f ) |C| = n -k -1 n -k > n -k -1 n -k .
However, according to Lemma 5.27,

d C (f ) |C| -1 = + k -1 m + + k -1 < + k -1 m + + k -1 = n -k -1 n -k which is a contradiction. Hence k ≥ k.
In our reduction, the set L ∪ M can be a community or not, depending on the value of k and n. Indeed, L ∪ M is a community if and only if m+ -1 ≥ n-2 n which directly implies k ≤ n 2 . Therefore, we stress that deciding if a community is inclusion-wise maximal is co-NP-complete.

Corollary 5.30. Let G = (V, E) be a connected graph and C ⊂ V a community in G. Deciding if C is inclusion-wise maximal is co-NP-complete on bipartite graphs.

In the following we show that the class of graphs from Figure 5.3 has a set of only 5 vertices that cannot be extended into a community (see Figure 5.6). Proof. We denote by z and z the center vertices of the stars S and S respectively. Firstly, notice that P is not a community since neither z nor z is satisfied. Consider a set C ⊂ V such that P ⊂ C. Let λ := d C (z) and respectively λ := d C (z ). Without loss of generality, assume that λ ≤ λ . We have

|C| = (d -λ + 1) + (d -λ + 1) + 1 ≥ 2 • (d -λ + 1) + 1 and |C| = λ + λ ≤ 2λ . Suppose by contradiction that C is a community in G, then the vertex z is satisfied and 2λ • (d -λ ) ≥ |C| • (d -λ ) ≥ (|C| -1) • λ ≥ 2λ • (d -λ + 1)
, which is obviously impossible. Thus C is not a community.

Conclusions

We proved that Max Community is NP-hard even on split graph, whether the community is required to be connected or not. In addition, the problem is APX-hard and 2-approximable in polynomial time. On the other hand, we proved that all Hamiltonian cubic graphs (except two) have a community with a size that reaches the theoretical bound

|V |•(∆(G)-1)+1 ∆(G)
, and such community can be found in polynomial time. Finally, we showed that determining if a community is inclusion-wise maximal is co-NP-complete, even on bipartite graphs.

Several questions remain open around this problem. It is not known in which graph classes a community that reaches the previous theoretical bound exists, and if so, if such community can be found in polynomial time. In particular, an extension of our theorem for Hamiltonian cubic graphs to general cubic graphs could be interesting to investigate. Furthermore, it could be interesting to investigate the problem in trees. From the approximation point of view for Max Community, we do not know if there is a better approximation ratio than 2, or a better inaproximation ratio than (1 -).

Introduction

In this chapter, we investigate problems around s-clubs. In the context of community detection, the first intuitive way to define a cohesive group of people that constitutes a community is to look for a group of people where everybody knows each other, which corresponds to search for a clique in a graph.

However, as discussed in Chapter 3, considering communities as cliques is too restrictive: a subgraph with all possible internal edges except one would not be considered as a community under this assumption, even if it probably should be in real world social networks.

We can consider a less restrictive condition which still reflects cohesion. In this way, a community can be defined as a group of people such that every two members have a 'chain' of relationship between them: the first person knows someone who knows someone ... who knows the second member, with a restricted length for this chain. Given a graph, Mokken introduced in [START_REF] Mokken | Cliques, clubs and clans[END_REF]] the notion of s-club which is a vertex set such that the subgraph induced by the vertex set has diameter at most s. Recent studies have been made around finding s-clubs in real networks [START_REF] Laan | Close communities in social networks: boroughs and 2-clubs[END_REF][START_REF] Mokken | Close communication and 2-clubs in corporate networks: Europe 2010[END_REF].

Problems around s-clubs have been well studied in the literature. A main one is, given a graph, to find an s-club of maximum size, which has been studied in [START_REF] Asahiro | Approximating maximum diameter-bounded subgraphs[END_REF][START_REF] Chang | Finding large k-clubs in undirected graphs[END_REF][START_REF] Golovach | Finding clubs in graph classes[END_REF][START_REF] Hartung | Parameterized algorithmics and computational experiments for finding 2-clubs[END_REF][START_REF] Hartung | On structural parameterizations for the 2-club problem[END_REF][START_REF] Schäfer | Parameterized computational complexity of finding small-diameter subgraphs[END_REF].

Another problem consists in finding a partition into k parts of vertices that are all s-clubs, that we discuss in this paper. This problem has been studied in [START_REF] Abbas | Clustering bipartite, chordal graphs: Complexity, sequential, parallel algorithms[END_REF][START_REF] Chang | On the complexity of graph clustering with bounded diameter[END_REF][START_REF] Deogun | An approximation algorithm for clustering graphs with dominating diametral path[END_REF][START_REF] Parley | Partitioning trees: Matching, domination, and maximum diameter[END_REF]. The problem has been showed linear time solvable in trees by Parley et. al. in [138]. In [START_REF] Deogun | An approximation algorithm for clustering graphs with dominating diametral path[END_REF], Deogun et. al. proved that the problem is NP-hard for any k ≥ 3 and s ≥ 2 even in the case where the graph is both split and undirected path. Moreover, it is proved in [START_REF] Deogun | An approximation algorithm for clustering graphs with dominating diametral path[END_REF] that for s = 2 the minimum number of parts is bounded by the domination number of a graph and is equal to the domination number on strongly chordal graphs. Abbas et. al. [START_REF] Abbas | Clustering bipartite, chordal graphs: Complexity, sequential, parallel algorithms[END_REF] proved that minimizing the number of parts in a partition of a graph into s-clubs is NP-hard for any s ≥ 2 for bipartite graphs, NP-hard on chordal graphs, and also NP-hard for split graphs with s = 2 and any k ≥ 3.

It is interesting to also study dynamic versions of community detection. In fact, real social network are constantly changing and links between members can either appear or disappear. In this way, we also study problems related to s-clubs around adding and removing edges. In [START_REF] Plesnik | The complexity of designing a network with minimum diameter[END_REF], Plesnik studied the following problem: given a graph G, a cost function c on the edges and an integer B, finding a spanning subgraph G of G with cost e∈G c(e) < B and with minimum diameter. The associated decision problem has been proved NP-complete. In [START_REF] Bilò | Improved approximability and nonapproximability results for graph diameter decreasing problems[END_REF], Biló et al. studied the two following problems. Given a graph G = (V, E), and two positive integers D and B, find a minimum-cardinality set E of edges to be added to G in such a way that the diameter of G = (V, E ∪ E ) is less than or equal to D. Given a graph G = (V, E), find a set E of B edges to be added to G in such a way that the diameter of G = (V, E ∪ E ) is minimized. Both are known to be NP-hard. Deleting at most t edges to a graph in order to obtain a graph of diameter at least s was proved NP-hard for k = |E| -|V | + 1 and s = |V | -1 by Schoone et al. in [START_REF] Schoone | Diameter increase caused by edge deletion[END_REF].

The chapter is organized as follows. In Section 6.2, we introduce formally the problems around 2-clubs we studied. In Section 6.3, we discuss a wrong result from [START_REF] Chang | On the complexity of graph clustering with bounded diameter[END_REF] and show that the problem of finding a partition into two 2-clubs is NP-hard, even in split graphs. In Section 6.4.1, we discuss the problem of adding a minimum number of edges in a graph in order to become of diameter at most 2. In Section 6.4.2, we study the problem of finding the minimum number of edges to keep in a graph while maintaining its diameter. Conclusion and open problems are given in Section 6.5.

Preliminaries

In this section we define the notions and the problems studied in this chapter. We are interested in the following decision problem :

In Section 6.3, we investigated the following problem: k-Partition into s-clubs Input : A graph G = (V, E), two integers k, s. Question : Is there a partition {P 1 , P 2 , . . . , P k } of V such that P i is an s-club, for each i ∈ {1, . . . , k}?

In Section 6.4.1, we investigate the following problem:

s-Club Edges Adding

Input : A graph G = (V, E), two integers s, t. Question : Is there a set of edges E of size at most t such that V is an s-club in the graph G = (V, E ∪ E ) ?

In Section 6.4.2, we investigated the following problem:

Spanning s-club Input : A graph G = (V, E), an integer k. Question : Is there a set of edges E ⊂ E of size at most k such that the graph G = (V, E ) is of diameter s ?

In order to prove some NP-hardness results, we use the following problem proved NPhard in [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]:

Dominating Set

Input : A graph G = (V, E), an integer t. Question : Is there a set of vertices S ⊂ V of size at most t such that S is a dominating set ? Since we have several results in this class of graphs, we introduce some notation for an easier reading. For any split graph G = (V = S ∪ K, E), S always corresponds to the independent set and K to the clique. Moreover, for any dominating set D of G, we always consider that D is included in K. Indeed, if a vertex v of D belongs to S, we can take any neighbor v of v from K in D instead of v from S without compromising the fact that D is a dominating set.

Partition into two 2-clubs

In this section, we first discuss that for bipartite graphs, partitioning a graph into two 2-clubs can be done in polynomial time whereas partitioning a graph into k 2-clubs, for any fixed k ≥ 3, is NP-hard. Then, we show that partitioning a graph into two 2-clubs is NP-hard even on split graphs. Since a 2-club in a bipartite graph is a biclique, then for bipartite graphs, partitioning a graph into k 2-clubs is equivalent to partition a graph into k bicliques. Since partitioning a bipartite graph into two bicliques is polynomial time solvable, [GT15] in [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF], and partitioning a bipartite graph into k bicliques for any fixed k ≥ 3 is NP-hard [START_REF] Fleischner | Covering graphs with few complete bipartite subgraphs[END_REF], we can conclude that that for bipartite graphs, partitioning a graph into two 2-clubs can be done in polynomial time whereas partitioning a graph into k 2-clubs, for any fixed k ≥ 3 is NP-hard. Now notice that an interesting approach to detect s-clubs in graphs is to consider the power graph of the initial graph (see [START_REF] Chang | On the complexity of graph clustering with bounded diameter[END_REF][START_REF] Golovach | Finding clubs in graph classes[END_REF]). In [START_REF] Chang | On the complexity of graph clustering with bounded diameter[END_REF], Chang et al. claimed that the minimum number of parts in a partition into 2-clubs in a graph G equals the minimum number of cliques in a partition into cliques in G 2 . Actually, there exist graphs (even split graphs) in which there is no partition into two 2-clubs but the squared graph contains a partition into two cliques. We can consider the graph in Fig. 6 In order to prove that partitioning a graph into two 2-clubs is NP-hard on split graphs, we introduce Monotone 3-Sat that has been proved NP-hard in [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. For each positive clause c i of C 1 , introduce two vertices c i,1 , c i,2 in a subset S p . For each negative clause c i of C 0 , introduce two vertices c i,1 , c i,2 in a subset S n . For each variable x i ∈ X we introduce a vertex x i in a subset K x . Notice that |K x | = |X|. All vertices c i,1 , c i,2 ∈ S p ∪ S n which correspond to a clause c i ∈ C are joined by an edge in E to a vertex x i ∈ K x that corresponds to a variable x i ∈ X either if it appears in a negative or a positive way in c i ∈ C. Moreover, for each two vertices c i, , c j,t in S p (resp. S n ) corresponding to two different positive clauses (resp. negative clauses), i = j and , t ∈ {1, 2} such that both clauses do not contain any common variable, introduce a new vertex z in a subset K p (resp. K n ) and introduce c i,l z, c j,t z in E. Notice that

|K p | = O(|C 1 | 2 ) (resp. |K n | = O(|C 0 | 2 )).
|K n | = O(|C 0 | 4 ). Let S = S p ∪ S n ∪ S p ∪ S n and K = K p ∪ K p ∪ K x ∪ K n ∪ K n and
S p S n S p S n K p K n K p K n K x Figure 6.2: The split graph G defined from the instance I = (X, C) with X = {x 1 , x 2 , x 3 , x 4 , x 5 , x 6 } and C = {x 1 ∨ x 2 ∨ x 3 , x 4 ∨ x 5 ∨ x 6 , x 3 ∨ x 5 ∨ x 6 , x 1 ∨ x 2 ∨ x 3 , x 1 ∨ x 3 ∨ x 5 , x 4 ∨ x 5 ∨ x 6 , }
Now we show that there is an assignment for the variables of X such that every clause of C is satisfied if and only if there is a partition of V into two 2-clubs.

Suppose that there is a assignment satisfying all clauses from C. Then, we define the

Edge adding

The s-Club Edges Addition problem has been proved NP-hard for s = 3 by Schoone et al. in [START_REF] Schoone | Diameter increase caused by edge deletion[END_REF] and NP-hard for s = 2 by Li et al. in [START_REF] Li | On the minimum-cardinality-boundeddiameter and the bounded-cardinality-minimum-diameter edge addition problems[END_REF]. The case s = 1 is trivial since it corresponds to adding edges between every pair of nonadjacent vertices. Gao et al. [START_REF] Gao | The parametric complexity of graph diameter augmentation[END_REF] proved the W [START_REF] Abello | Massive quasi-clique detection[END_REF]-hardness of the problem for any s ≥ 2 by establishing a reduction from Dominating Set.

We prove that 2-Club Edges Addition is W [START_REF] Abello | Massive quasi-clique detection[END_REF]-hard even on split graphs. Notice that even if a solution is not required to be a split graph, we show in Theorem 6.2 that it is always possible to obtain a split graph of diameter 2 with less edges than any solution. Theorem 6.2. 2-Club Edges Adding is W [START_REF] Abello | Massive quasi-clique detection[END_REF]-hard even on split graphs.

Proof. We reduce Dominating Set on split graphs of diameter 2, which has been proved W [START_REF] Abello | Massive quasi-clique detection[END_REF]-hard by Lokshtanov et. al. in [119], to 2-Club Edges Addition on split graphs. Let G = (V = S ∪ K, E) be a split graph of diameter 2, instance of Dominating Set, where S corresponds to the independent set and K to the clique. We construct an instance G = (V , E ) of 2-Clubs Edges Addition as follows. Consider a copy of G and add two new vertices s 0 , k 0 . The graph G is a split graph with V = S ∪ K where S = S ∪ {s 0 } and K = K ∪ {k 0 }. Set E is obtained from E by adding edges between k 0 and every vertex v ∈ K and the edge k 0 s 0 (see Figure 6.3). We show now that there is a dominating set of size at most t in G if and only if we can add at most t edges to G such that G has diameter 2. Suppose that D is a dominating set of size t in G. We assume that D ⊆ K. The graph (V , E ∪ D ) where D = {s 0 x : x ∈ D} has diameter 2 since any vertex from S has a neighbor in D and then s 0 is at distance two from any vertex from S.

Suppose now that D is a set of non edges of G of size t such that G = (V , E ∪ D ) has diameter 2. We first show that we can assume that all edges in D are between s 0 and K. Let xy ∈ D . If x = s 0 and y ∈ S, let y be a neighbor of y in K and the graph G = (V , E ∪ D ∪ {s 0 y } \ {xy}) is still of diameter 2. If both x and y are different from s 0 and x ∈ S, y ∈ K, then the graph G = (V , E ∪ D \ {xy}) is still of diameter 2 since G has diameter 2. If now both x and y are different from s 0 and x ∈ S, y ∈ S, then the graph G = (V , E ∪ D \ {xy}) is still of diameter 2 since G has diameter 2. Thus, we can assume that all edges in D are between s 0 and K (by updating D if necessary) and |D | ≤ t. Then, the set of vertices adjacent to s 0 by an edge in D is necessarily a dominating set of G since s 0 and any vertex of S must be at distance 2. Thus, we obtain a dominating set in G of size at most t.

Edge deletion

In this section, we discuss the hardness of Spanning s-club in split graphs and of Spanning s-club for any odd s ≥ 3 in general graphs.

First, we observe that Spanning s-club is easy to solve for any s ≥ 4 in split graphs. Indeed, for any split graph G = (S ∪ K, E), define the spanning tree G = (V , E ) such that for any v ∈ S, choose a unique edge e ∈ E adjacent to v in G and let e be in E . Then choose any vertex x ∈ K and for any x ∈ K such that x = x , let xx be in E . The remaining graph G has diameter 4 and the number of edges in E is minimum since G is a tree (see Figure 6.4). Several observation makes us think that this conjecture is true. Let G = (V = S ∪K, E) be a split graph and D be a minimum dominating set of G. Let G = (V, E ) be a spanning subgraph of G of diameter 3.

First of all, consider any vertex s ∈ S. Since such vertex must be at distance 3 of any other vertex from S in the subgraph G , q∈N (s) d(q) ≥ |D|. This shows that the number of edges in G is strongly related to the size of the minimum dominating set.

Moreover, we can show that the conjecture is true if |D| = |S|. Indeed, if |D| = |S| then any vertex d from D covers exactly one vertex in S. This implies that there is no s 1 , s 2 in S which have a common neighbor in G since we would have |D| < |S|. Let s 1 , s 2 , . . . , s p+1 be the vertices of S. For each s i , 1 ≤ i ≤ p + 1, we note S i the set of its neighbors in G . Since G has diameter 3, we know that any s i , 1 ≤ i ≤ p + 1, must be at distance 3 from any other s j , j = i, which implies that there must exist at least one edge in G between any S i and S j , i = j. Thus, E contains at least |S|(|S|-1) 2 edges between all S i and S j , i = j. Moreover, E also contains all edges between {s i } and S i for 1 ≤ i ≤ p + 1 by definition of S i . Finally, any vertex from K which has no neighbor in S must have at least one adjacent edge in E since G must be connected. Thus, we obtain

|E | ≥ |S|(|S|-1) 2 + p+1 j=1 |S j | + |K| -p+1 j=1 |S j | = |S|(|S|-1) 2 + |K| = |D|(|D|-1) 2 + |V | -|D|, since |D| = |S|.
Showing this conjecture would allow us to prove the following: Proposition 6.4. If Conjecture 6.3 is true, then Spanning 3-club is NP-complete even on split graphs.

Proof. Suppose that Conjecture 6.3 is true. We reduce Dominating Set on split graphs, which has been proved NP-complete in [START_REF] Bertossi | Dominating sets for split and bipartite graphs[END_REF], to Spanning 3-club on split graphs. Notice that Spanning 3-club is obviously in NP. Let G = (V = S ∪ K, E) be a split graph as an instance of Dominating Set, where S corresponds to the independent set and K to the clique, and we also consider G as an instance of Spanning 3-club. We show that there is a dominating set of size at most b in G if and only if there is a spanning subgraph containing at most b(b-1) In order to go a little further, it is now interesting to notice that the latter conjecture would imply that Spanning (2s + 1)-club is NP-complete in general graphs for any s ≥ 1. In order to prove that, we introduce the concept of graph almost split of length s. For any s ≥ 1, a graph G is said to be almost split of length s if we can construct G by considering a split graph and for each vertex of G we add a path of length s -1 linked to this vertex (see Figure 6.5). For a given graph almost split of length s, we note S i the set of all vertices from the added paths which are at distance i from a vertex of the induced split graph. Notice that a split graph is a graph almost split of length 0.

2 + |V | -b in which V is a 3-club. Let D be a dominating set of size b in G, D ⊆ K. Define the following spanning subgraph G = (V, E ) with E ⊂ E.
For any s ≥ 1, we reduce Spanning (2s + 1)-club in graphs almost split of length s -1 to Spanning (2s + 3)-club in graphs almost split of length s. Proposition 6.5. If Conjecture 6.3 is true, then Spanning (2s + 1)-club is NP-complete on general graphs for any s ≥ 1. Proof. We suppose that Conjecture 6.4 is true. Let s ≥ 1 be any integer. Since Spanning 3-club is supposed to be NP-complete from Conjecture 6.4, we reduce Spanning (2s +1)club in graphs almost split of length s -1 to Spanning (2s + 3)-club in graphs almost split of length s for any s ≥ 1 and show the property by polynomial reduction transitivity.

Let G = (V, E) be an instance of Spanning (2s + 1)-club in graphs almost split of length s -1 where

V := S 0 ∪ S 1 ∪ • • • ∪ S s-1 ∪ K.
We construct an instance G = (V , E ∪ E ) of Min spanning (2s + 3)-club in graphs almost split of length s where V := S 0 ∪ S 1 ∪ • • • ∪ S s ∪ K as follows. For any i ∈ {1, . . . , s -1}, let S i be a copy of S i . Let K be a copy of K. There is an edge in E between two vertices of S 0 ∪ S 1 ∪ • • • ∪ S s-1 ∪ K if and only if there is an edge in E between the corresponding copies in S 0 ∪S 1 ∪• • •∪S s-1 ∪K . Finally, let S s be a set of |V | vertices, and let E be a perfect matching between S s and S s-1 .

We show now that there is a spanning subgraph with k edges in G of diameter 2s + 1 if and only if there is a spanning subgraph with k + |S 0 | edges in G of diameter 2s + 3. Obviously, if G has a spanning subgraph of diameter 2s + 1 with k edges, considering the corresponding edges in G and adding all edges from E between S s-1 and S s , we obtain a spanning subgraph of diameter 2s + 3. Now suppose that G has a spanning subgraph G 0 of diameter 2s+3 with k +|S 0 | edges. Since any vertex from S s must have an adjacent edge in G 0 (otherwise the subgraph would not be connected), the spanning subgraph contains k edges between two vertices of V \ S s . Consider the spanning subgraph G 0 of G containing those corresponding k edges. Since G 0 has diameter 2s + 3, any two vertices from S s-1 must be at distance 2s + 1, and then G 0 has diameter 2s + 1.

We believe that Spanning 2-club must also be NP-complete. We give the following conjecture: Conjecture 6.6. Spanning 2-club is NP-complete even on split graphs.

Using a similar reduction from Proposition 6.5, assuming that Conjecture 6.6, we can derive the following proposition: Proposition 6.7. If Conjecture 6.3 is true, then Spanning (2s)-club is NP-complete on general graphs for any s ≥ 2.

In that way, we obtain the following proposition: Proposition 6.8. If Conjectures 6.3 and 6.6 are true, then Spanning s-club is NPcomplete on general graphs for any s ≥ 2.

Conclusions

In this chapter, we proved that partitioning a graph into two 2-clubs is NP-hard, even on split graphs. Moreover, we proved that 2-Club Edges Adding is W[2]-hard even on split graphs. We also discussed the possible NP-hardness of Spanning 2-club and Spanning 3-club on split graphs, and of Spanning s-club on general graphs for any integer s ≥ 1.

On the other hand, in addition to our conjectures, some open questions remain open. In Section 6.3, we saw that partitioning a graph into two 2-clubs is harder than expected in [START_REF] Chang | On the complexity of graph clustering with bounded diameter[END_REF]. However, we would expect that a graph of diameter 2 has always such a partition, but this problem remains open. On the other hand, investigating the complexity of 2club Adding Edges and Spanning 2-club in bipartite graphs would give a better understanding of s-clubs in graphs.

Introduction

With the recent development of social networks and particularly online meet-up services like Couchsurfing or Meetup.com, it could be interesting to investigate the detection of some group of people who do not know each other, but are related by their other relationships. Such a group could be considered as a 'potential' community since it does not form a community in the first place, but could become one due to their proximity. This may find various applications in online dating and meet-up services in which members expect not to know the other members.

More precisely, considering a graph G, we want to define potential communities by looking at independent sets in which any two members are related within a specified distance in G. Contrary to a k-club, the distance between two vertices must be realized via vertices outside of the subgraph. We call such a subset of vertices an independent k-clique, where k is the largest distance between vertices of S in the original graph. In this paper, we study the problem of finding an independent 2-clique of maximum size.

We investigate the complexity of the problem in several graph classes. Since this problem is close to finding an independent set of maximum size, we also compare the hardness of the two problems. Figure 7.1 summarizes the results we prove in this chapter.

This chapter is structured as follows. In Section 7.2 we introduce formally some notation and definitions. In Section 7.3 we show that the complexity of Max Independent 2-Clique jumps from polynomial-time solvable to NP-hard when the input class is extended from planar graphs to apex graphs. In Section 7.4 we present polynomial algorithms to solve Max Independent 2-Clique in some graph classes. In Section 7.5 we show NPhardness and non-approximability of Max Independent 2-Clique in some other graph classes. Conclusions and open problems are given in Section 7.6.

Preliminaries

An independent 2-clique is defined as a subset of vertices which is an independent set and a 2-clique at the same time. We recall from Chapter 3 that a 2-clique is a subset of vertices in which any two vertices are at distance at most 2 in the graph.

In this paper we are interested in the following optimization problem:

Max Independent 2-Clique Input: A graph G = (V, E). Output: A subset S ⊂ V which is an independent 2-clique of maximum size.
The Max Independent 2-Clique problem is closely related to the well known problem of finding an independent set of maximum size, named Max Independent Set.

Given a graph G, the standard notation for the maximum size of an independent set in G is α(G). The maximum number of vertices in an independent 2-clique of G will be denoted by α =2 (G). The subscript '=2' intends to express that the distance between any two vertices of the independent set is exactly 2. Note that α =2 (G) ≥ 2 whenever at least one connected component of G is not a complete graph. Indeed, any such component contains two vertices at distance exactly two, hence forming an independent 2-clique of size 2. Moreover, if G is disconnected and has components G 1 , . . . , G k then

α =2 (G) = max 1≤i≤k α =2 (G i )
For these reasons we assume in this chapter that G is a non-complete, connected graph (although some of the algorithms also need to handle disconnected graphs temporarily). Independent 2-cliques might have several forms. Indeed, the 2-clique property of an independent 2-clique S can be ensured either by only one vertex or a lot: if each pair of vertices have a common neighbor that is different for every pair, the number of vertices out of S that are useful to insure the 2-clique property can reach |S|•(|S|-1)

2

. See Figure 7.2 as an illustration.

From the parametrized complexity point of view, it is interesting to notice the following fact. by vertices within distance at most 3 from v in G -x. Then, in G, considering any vertex v belonging to an independent 2-clique S, the 2-clique property is ensured by vertices within distance at most 3 from v in V \ {x} and x and in its neighborhood N (x). For this reason, for each vertex v ∈ V , we consider the subgraph induced by the set of all vertices at distance at most 3 from v and include {x} ∪ N (x). This subgraph has treewidth at most 12 + |N (x)| < 12 + 4k. Since any problem parameterized by q expressible in Monadic Second-Order Logic is in FPT with respect to q on graphs of treewidth bounded by q [47], a polynomial-time algorithm can be designed by solving the problem for all such subgraphs defined from each vertex v of G, and answer yes if at least one such problem answers yes and answer no otherwise.

Graph classes with polynomial-time algorithms

In the following we identify some graph classes on which Max Independent 2-Clique is computable in polynomial time, while Max Independent Set is not always polynomialtime solvable.

Graph classes related to the degree

First, it is interesting to notice that, according to the next propositions, Max Independent 2-Clique is polynomial-time solvable on graphs of bounded degree and also on complements of graphs of bounded degree, while Max Independent Set is NP-hard on graphs of bounded degree [START_REF] Garey | Some simplified NP-complete graph problems[END_REF] but polynomial-time solvable on their complements (using exhaustive search in the non-neighborhood of each vertex, which can be done in linear time). Proposition 7.7. Max Independent 2-Clique is linear-time solvable on graphs with bounded maximum degree.

Proof. The proof consists in computing, for each vertex v of a graph G = (V, E), the largest size of an independent 2-clique v can belong to. Since the maximum degree is bounded, also the number of vertices at distance 2 from v is bounded, thus the largest independent 2-clique among them can be determined in constant time. Performing this for all vertices of the graph can be done in O(|V |) steps. Proposition 7.8. Max Independent 2-Clique is linear-time solvable on graphs of minimum degree at least (n -d), where d is constant.

Proof. Since every vertex is non-adjacent with fewer than d vertices, the size of a solution cannot exceed d. Then using an exhaustive search in the non-neighborhood of each vertex, we can find an optimal solution in linear time.

Finding an independent 2-clique in the neighborhood of a vertex

Now, notice that a natural way to find an independent 2-clique is to take an independent set included in the neighborhood of one vertex. First, this principle can be applied easily on trees.

Proposition 7.9. Every tree T satisfies α =2 (T ) = ∆(T ). Thus, Max Independent 2-Clique is linear-time solvable on trees without using Monadic Logic.

Proof. Any two vertices v, w of an independent 2-clique S share a neighbor, say u, which is unique in any tree. Non-neighbors of u cannot belong to S because they are at distance at least 3 from v or w (or both). On the other hand, all neighbors of u have mutual distance 2, so that |S| is largest if S is the neighborhood of a vertex of maximum degree.

In this way, it is interesting to investigate the properties of a graph in which an independent 2-clique is not included in the neighborhood of one vertex. We show in Lemma 7.10 that such a graph necessarily contains a cycle of length 3 or 6, and cannot be a cactus if such an independent 2-clique has a certain size. Such properties allow us to get an easy polynomial-time algorithm for Max Independent 2-Clique on (C 3 , C 6 )-free graphs, while Max Independent Set is NP-hard1 on this class of graphs (see [5]). From Theorem 7.4 we already know that Max Independent 2-Clique is linear-time solvable on cactus graphs, but the property of Lemma 7.10 allows us to give a simpler algorithm for this class of graphs. Lemma 7.10. Let G = (V, E) be a graph. Suppose that there exists an independent 2clique S not contained in the neighborhood of a single vertex. Then G contains an induced cycle of length 3 or 6. Moreover, if |S| ≥ 4, G is not a cactus.

Proof. Let S be an independent 2-clique in G such that all vertices of S do not have a common neighbor. Let u be a vertex in V \S which has the maximum number of neighbors in S, and N u be the neighborhood of u in S. Then there exists a vertex z in S which is not a neighbor of u. Let v be any vertex of N u , and w be a common neighbor of z and v. Let v be a vertex in N u non-adjacent to w (it exists by the choice of u). Since S is a 2-clique, v and z have a common neighbor, say w (notice that w can be neither u nor w). Thus, C := (u,v,w,z,w ,v ,u) is a cycle in G (see Figure 7.3).

If C has no chord, then it is an induced 6-cycle of G; and otherwise any chord of C lies inside {u, w, w } and thus it creates a 3-cycle in G. This proves the first assertion.

Suppose now that |S| ≥ 4. Then there are three options:

• u has only two neighbors in S. Then any two vertices of S must have a different common neighbor in V \S (by the choice of u), moreover there exists z in S \{N u , z}.

of v i in G and construct S i as an independent set of maximal2 size in the subgraph induced by N i in linear time. Notice that S i is actually an independent set of maximum size in the subgraph induced by N i since any vertex of N i may only have at most one neighbor in N i since G is a cactus. Let S be one of the sets S i , i = 1, . . . , n, of maximum size. By construction, S is an independent 2-clique of maximum size among all independent 2-cliques in G in which every vertices have a common neighbor in V . Moreover, S can be found in linear time. Now we prove that S is an independent 2-clique of maximum size in G. If |S| ≤ 3, by Lemma 7.10 we know that α =2 (G) ≤ 3. Indeed, if α =2 (G) ≥ 4 then G would not be a cactus since S is an independent 2-clique of maximum size among all independent 2-cliques in G in which every vertices have a common neighbor. Then, if |S| = 3, S is already an independent 2-clique of maximum size. Now suppose that |S| = 2. Then α =2 (G) = 2. Indeed, if α =2 (G) = 3, since |S| = 2 any independent 2-clique of size 3 would be included in an induced cycle C 6 (as in Figure 7.3) without chord (since G is a cactus) and we note such a cycle c. Since G is not isomorphic to a cycle of length 6, one of the vertices (say v) of the cycle c has a neighbor out of c. Then since G is a cactus, the two neighbors of v in c and one neighbor of v in V \ c is an independent 2-clique of size 3, which is a contradiction since |S| = 2. Thus, S is an independent 2-clique of maximum size. If |S| ≥ 4, by Lemma 7.10, any independent 2-clique in G is included in the neighborhood of a vertex in V , then S is an independent 2-clique of maximum size in G.

Other graph classes in which both problems are polynomialtime solvable

We focus now on classes of graphs on which both Max Independent 2-Clique and Max Independent Set are polynomial-time solvable. We first investigate a subclass of split graphs, namely threshold graphs. It follows from the definitions that a threshold graph G = (V, E) is a split graph with the following property: the vertices of the independent set S can be ordered as v

1 , . . . , v p such that N G (v 1 ) ⊆ N G (v 2 ) ⊆ . . . ⊆ N G (v p ).
We denote by u 1 , . . . , u q the vertices of the clique K, and we suppose that

d G (u 1 ) ≤ d G (u 2 ) ≤ . . . ≤ d G (u q )
. Without loss of generality, we assume that there is no isolated vertex in G. Note that a threshold graph can be recognized in linear time (see [START_REF] Heggernes | Linear-time certifying recognition algorithms and forbidden induced subgraphs[END_REF]).

(G) = α(G).
Proof. Let G = (V, E) be a threshold graph with the previous decomposition into S and K.

Let N G (v p ) = {u r , u r+1 , . . . , u q }, for some r ≥ 1. Then a maximum independent 2-clique in G is S if K \ N G (v p ) = ∅, and otherwise it is S ∪ {z} with any z ∈ K \ N G (v p ), since in both cases the common neighbor of all these vertices is u q . Since Max Independent

Set can be solved in linear time in threshold graphs [START_REF] Frank | Some polynomial algorithms for certain graphs and hypergraphs[END_REF], Max Independent 2-Clique can be solved in linear time.

The previous result can be extended in two directions, for interval graphs and for cographs.

Using the results of Booth and Lueker [START_REF] Booth | Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms[END_REF] it can be tested in linear time whether a graph G is an interval graph; and if it is, then an interval representation I 1 , . . . , I n of G can also be generated.

Proposition 7.14. Max Independent 2-Clique is polynomial-time solvable on interval graphs.

Proof. Consider any G = (V, E) and let I 1 , . . . , I n be an interval representation of G. In order to determine α =2 (G), first notice that all vertices of an independent 2-clique S of G must have a common neighbor. Indeed, if I and I are the leftmost and the rightmost intervals of S then any of their common neighbors intersects all intervals located between them, and therefore is a common neighbor of all members of S. Then, for every vertex I, we compute a maximum independent set in the subgraph induced by the neighborhood of I. An optimal solution is such an independent set with maximum size. Since Max Independent Set is polynomial-time solvable on interval graphs [START_REF] Gupta | Efficient algorithms for interval graphs and circular-arc graphs[END_REF], the result follows.

We consider now the class of cographs, that contains all threshold graphs, and we show that Max Independent 2-Clique is linear-time solvable on this class. In [START_REF] Courcelle | Linear time solvable optimization problems on graphs of bounded clique-width[END_REF], Courcelle et. al. proved that any problem expressible in Monadic Second-Order Logic is lineartime solvable for graphs of bounded clique-width. Since cographs are exactly the graphs with clique-width at most 2 [START_REF] Courcelle | Upper bounds to the clique width of graphs[END_REF], Max Independent 2-Clique is linear-time solvable on cographs. We give an alternative proof which is more constructive.

To each cograph G with n vertices, we can associate a rooted tree T , called the cotree of G. Leaves of T correspond to vertices of the graph G, and internal nodes of T are labeled with either '∪' (union-node) or '×' (join-node). A subtree rooted at node '∪' corresponds to the vertex-disjoint union of the subgraphs defined by the children of that node, and a subtree rooted at node '×' corresponds to the complete join of the subgraphs defined by the children of that node; that is, we add an edge between every two vertices corresponding to leaves in different subtrees under the join-node in question. Cographs can be recognized in linear time and the cotree representation can be obtained efficiently [START_REF] Corneil | A linear recognition algorithm for cographs[END_REF][START_REF] Habib | A simple linear time algorithm for cograph recognition[END_REF]. Moreover, any cotree can easily be transformed in linear time to a binary cotree with O(n) nodes. Let x 1 , . . . , x t be the nodes of T where x r is its root and t is in O(n). For i = 1, . . . , t, denote by T i the subtree rooted at x i , G i the subgraph induced by the vertices corresponding to the leaves of T i , and V i the set of these vertices.

For each i, we compute α =2 (G i ) 'bottom-up' in the cotree. We start by computing values of leaves, and after that the value of an internal node if the values of its two children are already computed. Together with α =2 (G i ) we also determine the independence number α(G i ), which is well known to admit an easy recursion (which follows immediately by the constructive definition of cographs).

Given a node x i of the cotree, the corresponding values are obtained as follows:

• If x i is a leaf then α =2 (G i ) = |V i | = 1. Also, α(G i ) = 1.
• If x i is a union-node with two children x and x r , we have no edges between G and G r . Then any maximum independent 2-clique of G i is entirely contained either in G or in G r . So, α =2 (G i ) = max{α =2 (G ), α =2 (G r )}. On the other hand, clearly, α(G i ) = α(G ) + α(G r ).

• If x i is a join-node with two children x and x r , every vertex in V is adjacent to every vertex in V r . Then a maximum independent 2-clique in G i is a maximum independent set entirely contained either in G or in G r . So, α =2 (G i ) = α(G i ) = max{α(G ), α(G r )}.

Since each step can be performed in constant time, moreover postorder traversal requires linear time, the algorithm runs proportionally to the size of the cotree, which is O(n).

Notice that since Max Independent Set is linear-time solvable on chordal graphs [START_REF] Frank | Some polynomial algorithms for certain graphs and hypergraphs[END_REF], it is also linear-time solvable on interval graphs and threshold graphs. Moreover, Max Independent Set is also linear-time solvable on cographs by bottom-up tree computation [START_REF] Corneil | Complement reducible graphs[END_REF].

NP-hardness and non-approximability

We investigate graph classes in which Max Independent 2-Clique is NP-hard and, in some case, non approximable in polynomial time. Using the reduction from the proof of Theorem 7.2, we can conclude:

• Max Independent 2-Clique is NP-hard on dense (resp. everywhere dense) graphs, since Max Independent Set is NP-hard on dense (resp. everywhere dense) graphs. Moreover, Max Independent 2-Clique is not n 1-ε -approximable for any ε > 0, if P = NP, on everywhere dense graphs (and respectively dense graphs) since the same result holds for Max Independent Set on everywhere dense graphs (and respectively dense graphs). In order to get this last result, we use the same inaproximability result for Max Independent Set on general graphs [START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF] and a reduction preserving approximation from general graphs to everywhere dense graphs Since it has been proved in [START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF] that Max Clique is not n 1-ε -approximable in polynomial time unless P = NP, Max Independent 2-Clique is not n 1-ε -approximable in polynomial time on split graphs unless P = NP.

Bipartite graphs

We prove now that Max Independent 2-Clique is NP-hard (and even not n 1/2-approximable, unless P = NP) on bipartite graphs while Max Independent Set is polynomial-time solvable since the number of vertices in a maximum independent set equals the number of edges in a minimum edge covering.

Proposition 7.19. Max Independent 2-Clique is NP-hard on bipartite graphs.

Proof. Max Independent Set is known to be NP-hard on 3-regular graphs [START_REF] Garey | Some simplified NP-complete graph problems[END_REF], so Max Clique is also NP-hard on (n -4)-regular graphs (where n is the number of vertices), by considering its complement. We reduce Max Clique on (n -4)-regular graphs to Max Independent 2-Clique on bipartite graphs. Let G = (V, E) be an (n -4)-regular graph.

We construct an instance of G = (V , E ) of Max Independent 2-Clique on bipartite graphs as follows (see Figure 7.4). Let V 1 , V 2 , V 3 , V 4 be four copies of V . Let E 1 be a set of |E| vertices corresponding to the edges in E, and define V := V 1 ∪V 2 ∪V 3 ∪V 4 ∪E 1 . Let there exist an edge in E between a vertex v in V i , i ∈ {1, 2, 3, 4} and a vertex e in E 1 if and only if the corresponding vertex v in V is incident with the corresponding edge e in E. Given a clique C ⊆ V of size at least k in G, the union of the four copies of C in G is an independent 2-clique of size at least 4k.

V 1 E 1 V 2 V 3 V 4
For the other direction, notice first that the value of a maximum independent set in a 3-regular graph is at least n 4 . Then, the value of a maximum clique in an (n -4)-regular graph is also at least n 4 . Thus the size of a maximum independent 2-clique in G is at least n.

We consider now a solution C of Max Independent 2-Clique in G with at least 4k ≥ n vertices (this restriction is always possible because of the previous comment). Notice that C cannot contain both a vertex from E 1 and a vertex from V \ E 1 since the distance between any two vertices of C must be 2. A solution which is a subset of E 1 would mean pairwise intersecting edges in G, hence would have size at most max(3, n -4) < n. Therefore C must be a subset of V \ E 1 . Notice that for any i ∈ {1, 2, 3, 4}, C ∩ V i must be a copy of a clique in G. Then C is a union of copies of four cliques in G, and |C | ≥ 4k. Let C 0 be the copy of largest size, which thus has |C 0 | ≥ k. Then C 0 is the copy of a clique C of G of size at least k. Theorem 7.20. Max Independent 2-Clique is not n 1/2-ε -approximable in polynomial time on bipartite graphs, unless P = NP.

Proof. We construct an E-reduction from Max Clique. Let I = (V, E) be an instance of Max Clique. Consider a reduction similar to the one in the proof of Proposition 7.19, except that we now consider = |V | copies V 1 , . . . , V instead of four copies of V ; adjacencies are defined in the same way as before. We denote by I = (V , E ) the corresponding instance of Max Independent 2-Clique from the reduction. As in Proposition 7.19, starting with a clique of size opt(I), we can construct an independent 2-clique of size

• opt(I) in G and thus opt(I ) ≥ • opt(I). Let S be any independent 2-clique in I of size at least (it always exists, take e.g. the copies of the same vertex, one copy in each V i ). As before S cannot contain both a vertex of E 1 and a vertex from V \ E 1 since two vertices of S must have distance 2 in G , and S cannot contain only vertices from E 1 since any independent 2-clique included in E 1 is of size at most max(3, ∆(G)) ≤ -1. Moreover, each subset V i ∩ S corresponds to a clique in G. Let S be the subset V i ∩ S of largest size. • opt(I) with a polynomial p, the reduction is an E-reduction. Then, since Max Clique is not 1-ε -approximable unless P=NP [START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF], the same property holds for Max Independent 2-Clique. Thus Max Independent 2-Clique is not n 1/2-ε approximable where n = |V | since n = 2 + |E|.

Line graphs

Finally we prove that Max Independent 2-Clique is NP-hard (and even APX-hard) on line graphs, while Max Independent Set is polynomial-time solvable since it consists in a maximum matching in the original graph.

Proof. We establish a reduction from the Max Clique problem on general graphs. Consider an instance G = (V, E) of Max Clique with |V | = n. We construct a graph G = (V , E ) (see Figure 7.5) as follows. Let G 0 = (V 0 , E 0 ) be a copy of G. Let V be V 0 ∪A∪B∪C where A, B, C are three sets of n vertices. Then, let E = E 0 ∪E 1 ∪E 2 ∪E 3 ∪E 4 such that E 1 is a perfect matching between V 0 and A, E 2 is the set of all possible edges (i.e., a complete bipartite graph) between the vertices of A and the vertices of B, E 3 is a perfect matching between B and C, and E 4 is the set of all possible edges between any two vertices of C (a complete subgraph). The line graph of G , denoted by L(G ), is an instance of Max Independent 2-Clique. Notice that an independent 2-clique in L(G ) corresponds to a set of edges in G such that, for each pair of edges {e 1 , e 2 } in the set, e 1 and e 2 are not adjacent but are joined by an edge. We show that G contains a clique of size at least k if and only if L(G ) contains an independent 2-clique of size at least k + n. Consider a clique S of size k in G, and let S 0 be its copy in G . We define a set of edges S of size at least k + n in G as follows. For any vertex v ∈ S 0 , add in S its adjacent edge in E 1 . Moreover add the entire E 3 to S . We show now that any pair of edges in S have an adjacent edge in common. Two edges of S ∩ E 1 have a common adjacent edge in E 0 since the subgraph induced by S 0 is a clique. Similarly, two edges of E 3 have a common adjacent edge in E 4 . Moreover, an edge of S ∩ E 1 and an edge of E 3 have a common adjacent edge in E 2 since the subgraph induced by A ∪ B is K n,n . Then, the corresponding set of vertices in L(G ) is an independent 2-clique of size k + n.

In the other direction, consider an independent 2-clique in L(G ) of size k + n. Notice that it is always possible to take the set of vertices in L(G ) corresponding to E 3 in G and two edges in E 1 whose vertices in V 0 are neighbors in G , hence we can suppose that k ≥ 2. Let S be the set of all corresponding edges in G . Suppose first that there is exactly one edge from E 0 in S . Then, there are at most n -2 edges from E 1 in S , and there are at most 2 edges from E 2 in S , due to the constraints of an independent 2-clique. There cannot be edges from E 3 ∪ E 4 in S since they would not be joined to the edge of E 0 ∩ S by any edge. Then, S contains at most n + 1 edges in S , which contradicts k ≥ 2. Suppose now that there are at least g ≥ 2 edges from E 0 in S . Name two of them e 0,1 and e 0,2 . Then, there are at most n -2g edges from E 1 in S but there is no edge from E 2 in S . Indeed, an edge e 2 from E 2 in S can be joined by an edge to at most one of e 0,1 and e 0,2 . Then the size of S does not exceed n, which contradicts k ≥ 2. Thus, we can assume that there is no edge from E 0 in S . Similarly, there is no edge from E 4 in S . Now, notice that |S ∩ (E 2 ∪ E 3 )| ≤ n since if S ∩ (E 2 ∪ E 3 ) contained n + 1 edges then at least two of these edges would have a common endpoint. Consequently, |S ∩ E 1 | ≥ k. Moreover, any two edges from S ∩ E 1 must have a common adjacent edge in E 0 since they cannot have a common adjacent edge in E 2 . Then, the subgraph of G induced by the set of vertices in V 0 which are the endpoints of the edges in S ∩ E 1 must be a clique whose size is at least k. Proof. We construct now an L-reduction from Max Clique to Max Independent 2-Clique on line graphs. Let I be an instance of Max Clique on graphs of degree at least n -4 and I the corresponding instance of Max Independent 2-Clique on line graphs from the previous reduction. We prove that this reduction is an L-reduction. We proved in Proposition 7.21 that any independent 2-clique in I has a size at most 2n. Then opt(I ) ≤ 2n = 8 • n 4 ≤ 8 • opt(I) follows since opt(I) ≥ n 4 in graphs of degree at least n -4. Moreover, starting with a clique of size opt(I), we can construct an independent 2-clique of size opt(I) + n and therefore opt(I ) ≥ n + opt(I). Let S be an independent 2-clique in I of size at least n + 2 (we proved in Proposition 7.21 that it always exists and that such a set must be included in E 1 ∪ E 2 ∪ E 3 ). Let S be the set of vertices in V 0 which are incident with edges in Since Max Independent Set is APX-hard on the class of graphs of maximum degree 3 [6], Max Clique is also APX-hard on the class of graphs of minimum degree at least n -4. Thus, Max Independent 2-Clique is APX-hard on line graphs.

Conclusions

Despite that Max Independent 2-Clique and Max Independent Set are similar problems, their complexity can be very different depending on the graph class we try to solve the problem in. We mainly showed that Max Independent 2-Clique is NP-hard on apex, dense and everywhere dense, K 4 -free, split, bipartite and line graphs while it is polynomial-time solvable on bounded treewidth, planar, bounded degree (and complement of bounded degree), (C 3 , C 6 )-free, interval graphs and cographs. Many further types of graphs may be of interest, concerning separation of graph classes in which the problem is NP-hard from the ones where the problem is solvable in polynomial time.

Conclusions

The development of social networks and online meet-up services have made the study of community detection a major recent stake. In this thesis, we studied four particular definitions which are relevant for different reasons. Since the definitions for a community can be various and have different interests depending on the aspect of the cohesion we want to capture, it might be interesting to investigate other definitions.

On the other hand, we suggest some research directions for future work. For instance, in Chapter 4, we investigate the notion of community structure, in which each member has a greater proportion of neighbors in its part than in any other part. We saw that there exist graphs in which there is no 2-community structure, and the existence of k-community structure in a graph remains open for general values of k. An interesting relaxation of the problem would be to consider that each member has only to have a larger proportion of neighbors in its part than outside of its part. This definition is equivalent to the notion of k-community structure for k = 2, but becomes less restrictive for higher values of k. Furthermore, the definition of a community structure can take some robustness into account by asking, given a partition, for each vertex to satisfy the proportion condition even if we remove a certain constant q of their neighbors from the graph.

In the context of meet-up services, we investigate in Chapter 7 the notion of independent 2-clique in which any two members of such potential community has a common acquaintance. The vertices that ensure this property between two vertices in an independent 2-clique is the heart of the problem which makes the difference with the problem of just finding an independent set. Given an independent 2-clique S, we call the set of vertices that have at least two neighbors in S the support of S. Then, an interesting problem that we can study is, given a graph and some integer k, to find an independent set of size k such that the size of its support is maximized. This problem makes sense since the size of the support gives a good natural quality function of the cohesion of such potential community.

In further research around meet-up services, it might be interesting to define even other aspects of potential communities. In particular, signed graphs, in which labels "+" and "-" represent good and bad relationships, could be used in order to capture good potential communities. For instance, an induced path (x, y, z) of length 2 with two labels "+" reveal a good potential relationship between x and z, and such path with both labels "+" and "-" reveals some incompatibility between x and z. New problems could arise from this paradigm. Notice that is also possible to consider directed signed graphs in which there is an edge from a vertex x to a vertex y if the member x has some (positive or negative) judgment about y. We can then discuss several situations that often occur in real life: if x likes y and y like z, it is likely that x should like z, independently from the fact that y likes x or not. Directed graphs could then be worth of interest to modelize such situation. Given one of these paradigms, it could be interesting to find a community of a fixed size k that maximize the quality of cohesion. Such quality could be evaluated according to real life observations as we suggested previously.

List of Figures

Résumé

Cette thèse étudie la détection de communautés dans le contexte des réseaux sociaux. Un réseau social peut être modélisé par un graphe dans lequel les sommets représentent les membres et les arêtes représentent les relations entre les membres. En particulier, nous étudions quatre différentes définitions de communauté. D'abord, une structure en communautés peut être définie par une partition des sommets telle que tout sommet a une plus grande proportion de voisins dans sa partie que dans toute autre partie. Cette définition peut être adaptée pour l'étude d'une seule communauté. Ensuite, une communauté peut être vue comme un sousgraphe tel que tout couple de sommets sont à distance 2 dans ce sousgraphe. Enfin, dans le contexte des sites de rencontre, nous proposons d'étudier une définition de communauté potentielle dans le sens où les membres de la communauté ne se connaissent pas, mais sont liés par des connaissances communes. Pour ces quatre définitions, nous étudions la complexité et l'approximation de problèmes liés à l'existence ou la recherche de telles communautés dans les graphes.

Mots Clés

Graphes, réseaux sociaux, algorithme, complexité, approximation, structures en communautés, s-clubs, independent 2-cliques Abstract This thesis deals with community detection in the context of social networks. A social network can be modeled by a graph in which vertices represent members, and edges represent relationships. In particular, we study four different definitions of a community. First, a community structure can be defined as a partition of the vertices such that each vertex has a greater proportion of neighbors in its part than in any other part. This definition can be adapted in order to study only one community. Then, a community can be viewed as a subgraph in which every two vertices are at distance 2 in this subgraph. Finally, in the context of online meetup services, we investigate a definition for potential communities in which members do not know each other but are related by their common neighbors. In regard to these proposed definitions, we study computational complexity and approximation within problems that either relate to the existence of such communities or to finding them in graphs.

Figure 1 :

 1 Figure 1: Comparaison des complexités de Max Independent Set et Max Independent 2-Clique

2 Contents 2 . 1 25 2. 1 . 1 27 2. 1 . 3 28 2. 2 29 2. 2 . 1 29 2. 2 . 2 31 2. 2 . 3

 22125112713282292129223123 Preliminaries Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Basics of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Graph classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Computational complexity . . . . . . . . . . . . . . . . . . . . . Decision and optimization problems . . . . . . . . . . . . . . . . Approximation and approximation-preserving reductions . . . . . Parameterized complexity . . . . . . . . . . . . . . . . . . . . . . 32

  and for any two vertices x, y ∈ V k , xy ∈ E k if and only if d(x, y) ≤ k in G. For k = 2, we name such graph as a squared graph.

Figure 3 . 2 :

 32 Figure 3.2: Graph illustrating s-cliques, s-clubs for s = 2. {1, 2, 3, 4, 5}, {2, 3, 4, 5, 6} are 2-cliques meanwhile {1, 2, 3, 4}, {1, 2, 3, 5}, {2, 3, 4, 5, 6} are 2-clubs.

Figure 3 . 3 :

 33 Figure 3.3: The minimum (x, y)-cut gives an alliance containing x

Figure 3 . 4 :

 34 Figure 3.4: A graph in which all LS sets (H 1 , H 2 , H 3 , H 4 ) are framed except trivial ones (singletons and the set of all vertices)

Figure 3 . 7 :

 37 Figure 3.7: Structural balance: Each labeled triangle must have 1 or 3 positive edges

  refers to a p-tuple of cliques of size k such that C i and C i+1 are adjacent for any i ∈ {1, • • • , p -1}. Then, Palla et. al. defined in [136] a k-clique community as a maximal union of cliques of size k such that for any two cliques C 1 , C 2 of this union, there exists a chain of adjacency between C 1 and C 2 . Building all k-clique communities gives an overlapping partition of the graph into communities that may share some members. To put it in another way, the overlapping partition corresponds to the connected component of the clique graph in which the vertices correspond to the cliques of size k in the original graph, and two cliques are linked by an edge if they are adjacent in the original graph (see Figure 3.8 as an illustration).

Figure 3 . 8 :

 38 Figure 3.8: Example of an overlapping partition with 4-clique communities.

Figure 3 . 9 :

 39 Figure 3.9: Dendrogram of the communities found in the Zachary Karate Club Network with the algorithm of Girvan and Newman in [82]. Each horizontal line gives a partition into communities.

C 2 C 1 Figure 3 . 10 :

 1310 Figure 3.10: In this graph, the edge in the middle has a greater edge-betweenness than all other edges since all shortest paths connecting vertices from C 1 to C 2 run through it.

4 Two-Community Structures Contents 4 . 1 56 4. 2 57 4. 2 . 2 59 4. 2 . 3 60 4.3 2 - 62 4. 3 . 1 63 4. 3 . 2 83 4. 4 85 4. 4 . 1 88 4. 5 90 4. 6

 44156257225923602623163328348541885906 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.2.1 k-community structures . . . . . . . . . . . . . . . . . . . . . . . Studied problems . . . . . . . . . . . . . . . . . . . . . . . . . . . General observations . . . . . . . . . . . . . . . . . . . . . . . . . community structures in graph classes . . . . . . . . . . . . Some graph classes in which the problem is easy to handle in linear time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cubic graphs and graphs of maximum degree 3 . . . . . . . . . . 65 4.3.3 Dense graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Balanced 2-community structures . . . . . . . . . . . . . . . . General graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.4.2 Balanced 2-community structures in graphs with low density . . About graphs without 2-community structures . . . . . . . . Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

Figure 4 .Figure 4 . 1 :

 441 Figure 4.1: Two different 2-partitions for the same graph (given by the black and white colors) in which each part has at least 2 vertices. In the first partition, x does not satisfy the proportion condition of a community structure since the proportion of neighbors in the white part is1 3 but the proportion of neighbors in the black partition is 2 3 . The second partition gives a 2-community structure.

  v

Figure 4 . 2 :

 42 Figure 4.2: A weak 2-community structure of a graph (presented by the colors black and white) in which the vertex v does not satisfy the proportion condition of a 2-community structure but satisfies the weak proportion condition of a weak 2-community structure from Definition 4.2.

Figure 4 . 3 :

 43 Figure 4.3: A complete graph in which a 3-community structure is given by the colors black, gray and white.

Figure 4 . 4 :

 44 Figure 4.4: A disconnected graph with an isolated vertex in which there is no community structure.

Theorem 4 . 8 .

 48 Every 3-regular graph has a 2-community structure. Moreover it can be found in polynomial time. Proof. Let G = (V, E) be a 3-regular graph of size n. The algorithm runs in two stages. Stage 1: The algorithm finds a partition {C 1 , C 2 } of V such that |C 1 | = n-1 3 and at most two vertices from C 1 have more than one neighbor in C 2 .

3 .Stage 2 :Case 1 : 3 equals n 3 or n 3 Case 2 : 3 + 3 -

 32133233 ) If there is no such vertex w, the degree of each vertex in the subgraph induced by C 1 is 2 or 3. In such a case let u be any vertex of degree 2 in the subgraph induced by C 1 .It is clear that at the end of the first stage the algorithm finishes with a set C 1 such that |C 1 | = n-1 If it is not possible to apply (S1) and (S2) and |C 1 | < n-1 3 then all vertices in C 1 must have all neighbors in C 1 which means that G is not connected.Furthermore at most two vertices (u and v) from C 1 may have more than one neighbor outside C 1 and the subgraph induced by C 1 is connected. Define C 2 = V \ C 1 . We distinguish two major cases: If ∀w ∈ C 2 , d out (w) ≤ 1 then all vertices in G except u and v have at most one neighbor out of its part. Using Lemma 4.7, these vertices fulfil the proportion condition. Moreover, n-1 and according to Lemma 4.7, the proportion condition is also true if u or v have two neighbors out of C 1 . Hence, {C 1 , C 2 } is a 2-community structure. There exists a vertex w ∈ C 2 , such that d out (w) ≥ 2. Now we distinguish several subcases:(A) ∀x ∈ C 1 , d out (x) ≤ 1 (B)All vertices from C 1 which have more than one neighbor outside C 1 are adjacent to w (only u, v ∈ C 1 are possible candidates). (C) No vertex from C 1 which has more than one neighbor outside C 1 is adjacent to w (only u, v ∈ C 1 are possible candidates). (D) Both vertices u, v ∈ C 1 have more than one neighbor outside C 1 , but only one of them is adjacent to w. Case 2(A): Repeat the update step while it is possible before returning {C 1 , C 2 } as a 2-community structure: • if ∃z ∈ C 2 , d out (z) ≥ 2, update C 1 and C 2 as follows: C 1 := C 1 ∪ {z}, C 2 := C 2 \ {z}. After each update step, two neighbors of z in C 1 have degree three by assumption of Case 2(A) (See Figure 4.5). After repeating the update step k times, C 1 has n-1 k vertices and at least 2k vertices in C 1 have degree three in the subgraph induced by C 1 . Hence, we can repeat the update step at most n-1 1 times. Otherwise the degree of each vertex in

Figure 4 . 5 :

 45 Figure 4.5: Applying one step in Case 2(A) on the gray vertex decreases the size of the cut by one and creates two vertices in C 1 with 3 in-neighbors.

3 - 1 3 - 2 3 - 1 ) = n 3 . 3 ,

 31323133 and there is no such vertex z ∈ C 2 such that d out (z) ≥ 2, then each vertex in G has at most one neighbor out of its own part. Obviously, |C 1 | ≤ n -n-1 3 and due to Lemma 4.7, {C 1 , C 2 } is a 2-community structure. (ii) |C 1 | = 2 n-1 and ∃z ∈ C 2 such that d out (z) ≥ 2: the update step has been repeated n-1 times and in each step the number of vertices x ∈ C 1 with d out (x) = 1 is decreased by at least 2 (the neighbors of z in C 1 ). It means every vertices in V has all neighbors in its own part, except at most three vertices, each having one neighbor out of its part. -If n ≡ 2 mod 3, then the size of |C 2 | = n-(2 n-1 Because |C 1 | ≤ n-n-1 due to Lemma 4.7, all vertices with at most one neighbor out of its own part fulfil the proportion condition. If a vertex of C 2 is adjacent to exactly two vertices from C 1 then the proportion condition is true according to Lemma 4.7. A vertex of C 2 cannot be adjacent to all three vertices in C 1 , otherwise C 1 ∪ {w} is a disconnected part of G. Hence, {C 1 , C 2 } is a 2-community partition.

Theorem 4 . 10 .Stage 1 : 1 3 2 :

 410112 Every 3-regular graph has a connected 2-community structure. Moreover it can be found in polynomial time. Proof. The algorithm runs in two stages similarly to the algorithm in Theorem 4.8. The algorithm finds either a connected partition {C 1 , C 2 } such that |C 1 | = n-and at most two vertices from C 1 have two neighbors in C 2 or ends up with a connected 2-community structure. Stage Apply directly Stage 2 from Theorem 4.8.

Stage 1 : 1 3 3 . 1 3

 1131 (for a connected partition) Choose any vertices u, v ∈ V such that {u, v} ∈ E and the subgraph induced by V \{u, v} is connected. Label the vertices u, v and define C 1 := {u, v}, C 2 := V \{u, v}.The initial construction:While |C 1 | < n-and one of the updates (S1), (S2) (in this order) can be applied do: (S1) If there exists a vertex x ∈ C 2 such that d out (x) = 2, then updateC 1 := C 1 ∪ {x}, C 2 := C 2 \{x}. Ifall labelled vertices have three neighbors in C 1 , then removes all labels and label one vertex in C 1 which has one neighbor in C 2 . (S2) If there exists a vertex x ∈ C 2 such that x is a neighbor of a labelled vertex w in C 1 and C 2 \{x} remains connected then update C 1 := C 1 ∪ {x}, C 2 := C 2 \{x}, label the vertex x and remove label from w. If all labelled vertices have three neighbors in C 1 , then removes all labels and label one vertex in C 1 which has one neighbor in C 2 . Obviously after each update we can have at most two labelled vertices in C 1 . Now there are two possibilities how the initial construction can finish: (1) The algorithm finishes with |C 1 | = n-1 Due to the properties of the construction, the partition {C 1 , C 2 } is connected and at most two vertices from C 1 may have two neighbors in C 2 . In such a case we can move directly to Stage 2. (2) If none of the updates (S1), (S2) can be applied and |C 1 | < n-then we redefine the partition {C 1 , C 2 } using the major update construction to obtain a new partition which leads to a connected 2-community structure.

Figure 4 . 6 :

 46 Figure 4.6: Splitting C 2 when |N | = 4 (vertices in N are in gray)

C 1 : 3 :(

 13 = C 1 ∪ {z}. Now we repeat the following steps (S1) and (S2) until|C 1 | ≥ n-1 S1) Let w be a neighbor of u (or v) which is not in C 1 , put C 1 := C 1 ∪{w}, C 2 := C 2 \{w},and relabel u := w (or v := w). If there exist vertices in C 2 which have all of their neighbors in C 1 , transfer them into C 1 . Notice, that these must be neighbors of w, hence at most two additional vertices are transferred to C 1 .

Theorem 4 . 14 .

 414 Let G be a connected graph of maximum degree 3 on n vertices, n ≥ 4, except S 4 . Then G has a 2-community structure which can be found in a polynomial time.Proof. Let n = 4. Since G is not isomorphic to S 4 , any partition with an edge in each part has obviously a 2-community structure. If n = 5, then either G has a partition consisting of a cycle of length 3 and an edge (which has clearly a 2-community structure), or G must be isomorphic to one of the cases in Figure4.7.

Figure 4 . 7 :

 47 Figure 4.7: A 2-community structure {C 1 , C 2 } (C 1 in white, C 2 in black) for other graphs on 5 vertices.

  (b) If there exists a vertex v in C 2 with only out-neighbors, then update C 1 := C 1 ∪ {v} and C 2 := C 2 \ {v}.

2

 2 and there exists a vertex u of degree 2 in C 2 with one neighbor in C 1 : (a) Update C 1 := C 1 ∪ {u}, C 2 := C 2 \ {u}. (b) If there exists a vertex v in C 2 with only out-neighbors, then update C 2 := C 2 ∪ {v} and C 1 := C 1 \ {v}.

Lemma 4 . 15 .

 415 Every connected graph of maximum degree 3 on n vertices, n ≥ 4, has a connected partition {C 1 , C 2 } such that n-1 3

  Notice that each iteration of Stage 1 decreases the size of the cut by at least one. The Improvement Procedure: Stage 2 (Category (A) vertices) Similarly to Stage 1, in Stage 2 we handle vertices in C 1 of degree 3 with two out-neighbors by transferring them into C 2 , keeping the size of C 2 smaller than n -n-1 3 and ensuring connectivity of the partition {C 1 , C 2 }.

Theorem 4 . 20 .

 420 is a clique. Moreover, any two vertices in C 1 are neighbors except v i and its neighbour in G[O i,1 ] for all i, 1 ≤ i ≤ p. If B 1 = ∅, such two vertices must have a common neighbor in B 1 . If B 1 = ∅, then either |O 1,1 | ≥ 3 or p ≥ 2 (due to assumptions on G), and such two vertices have a common neighbor either in O 1,1 or O j,1 , j = i. Hence, G[C 1 ] is also connected. Let G = (V, E) be a graph with minimum degree (c-1).|V | c where c is the size of an inclusion-wise maximal clique in G, i.e. such a clique is not a subgraph of another clique. Then, G has a connected 2-community structure which can be found in polynomial time. Proof. If c ≥ |V | -1, then for any vertex u ∈ V , d(u) ≥ (|V |-2).|V | |V |-1 ≥ |V | -3 and the rest follows from Theorem 4.19.

Remark 4 . 24 .Lemma 4 . 25 .

 424425 Notice that the third assertion in Lemma 4.23 is the proportion condition of a 2-community structure. Let G = (V, E) be a graph with an even number n of vertices and {C 1 , C 2 } be a balanced partition of V . Then for any vertex

Remark 4 . 26 .Proposition 4 . 27 .

 426427 Let {C 1 , C 2 } be a balanced partition of G and v ∈ C 1 be a vertex of degree n-1. Since v has n 2 -1 neighbors in its own part and n 2 in other part, v does not satisfy the condition of Balanced Satisfactory Partition. However, v satisfies the Balanced 2-Community condition since d in (v) |C 1 |-1 = 1. For any graph with n vertices and maximum degree (n-2) the problems Balanced Satisfactory Partition and Balanced 2-Community are equivalent.

Theorem 4 . 28 .

 428 Connected Balanced 2-Community is NP-complete.

Figure 4 . 9 :Remark 4 . 29 .

 49429 Figure 4.9: An example of a graph in which all 2-community structures are balanced

Figure 4 .

 4 Figure 4.10: A cross gadget and a graph of maximum degree 3 without balanced 2community structure.

Remark 4 . 31 .

 431 Notice that Theorem 4.30 cannot be extended to a connected case. There exist graphs of maximum degree 3 in which every balanced weak 2-community structures is disconnected, see Figure4.11 as an example.

Figure 4 .

 4 Figure 4.11: A tree of maximum degree 3 in which any balanced 2-community structure (or even balanced weak 2-community structure) is disconnected (an example of a balanced 2-community structure is presented by the black and white colors) .

Theorem 4 . 32 .

 432 Balanced 2-community (hence also Balanced Weak 2-community) is polynomially solvable for graphs with bounded treewidth.

Figure 4 .

 4 Figure 4.12: A graph with 10 vertices that does not contain any 2-community structure

Figure 4 .Theorem 4 . 34 .

 4434 Figure 4.13: A schematic representation of a graph in G.

  and then |A 2 | ≥ k, a contradiction since B 2 = ∅. * If u ∈ N (y) \ N (x), then both d A (u) and d(u) decrease by one. Similarly to the previous case, we obtain that |A 2 | ≥ k + 1 k+2 and then |A 2 | > k, a contradiction. * If u ∈ N (x) \ N (y), then:

  then both d A (u) and d(u) decrease by one. Similarly to the previous case, we obtain |A 2 | ≥ k, a contradiction since |B 2 | = ∅. • If B 2 = W 2 , then either B = {x, y, z} ∪ W 2 , and we have |A| + 2 = |B| but d A (x) = d B (x) thus x is not satisfied, or B = {y, z} ∪ W 2 , and since |A| = |B| we have:

Figure 1

 1 Figure 1 Example of the transformation .

  Since e is unsatisfied, then e oe M \ C 1 and at most |M \ C 1 | transfers are needed to satisfy all the vertices in C 2 . Thus |C 2 | Ø |C 1 | holds true. Furthermore, observe that for any vertex w oe C 1 , the condition d C 2 (w) Ø |C 2 | ≠ 2 stays true after the transfer of u, hence according to Lemma 3 w remains satisfied. Also, since C 2 * N and C 2 + N then C 2 " = V . Therefore, all vertices of C 2 are satisfied, and |C 2 | Ø |C 1 |. Obviously, C 2 can be found in polynomial time. JWe give a reduction from the decision version associated to Max Independent Set which was proved NP-hard in[7]:

Figure 5 . 1 :Lemma 5 . 4 .

 5154 Figure 5.1: Example of the transformation Γ.

  is unsatisfied, then e ∈ M \ C 1 and at most |M \ C 1 | transfers are needed to satisfy all the vertices in C 2 . Thus |C 2 | ≥ |C 1 | holds true. Furthermore, observe that for any vertex w ∈ C 1 , the condition d C 2 (w) ≥ |C 2 | -2 stays true after the transfer of u, hence according to Lemma 5.3 w remains satisfied. Also, since C 2 is not included in N and C 2 is not included in N then C 2 = V . Therefore, all vertices of C 2 are satisfied, and |C 2 | ≥ |C 1 |. Obviously, C 2 can be found in polynomial time.

z 2 }

 2 are obviously satisfied in C as they only have neighbors in C. Hence, the only possible unsatisfied vertices are from the set M . Consider a vertex e ∈ M . Since R is an independent set of G, then for each edge e = (u, v) ∈ E at most one of the vertices u and v belongs to R. Hence, the vertex e ∈ M is not adjacent to at most one vertex in C and thus d C (e) ≥ |C| -2. According to Lemma 5.3, e is satisfied. Thus C is a community of size at least |M | + 2 + k. Let C be a community in G of size at least |M | + 2 + k. According to Lemma 5.4, there exists a community C of G such that |C | ≥ |C| and {z 1 , z 2 } ∪ M ⊆ C . We claim that R := C ∩ N is an independent set of G of size at least k. Obviously |R | ≥ k. Moreover, Lemma 5.3 states that for all satisfied vertices w ∈ C , d C (e) ≥ |C | -2. Hence for each vertex e ∈ M there is at most one vertex u ∈ C that is not adjacent to e. Since a non-edge between vertices e ∈ M and u ∈ N in G implies u ∈ e in G, then the edge e ∈ E has at most one endpoint u ∈ R in the graph G. Thus, R is an independent set of size at least k.

Figure 5 . 2 :

 52 Figure 5.2: A cubic graph where the community of maximum size (in gray) is disconnected.

Figure 5 . 3 :

 53 Figure 5.3: A caterpillar T = (V, E) constructed by two stars S d for some integer d such that their center are joined by a path of length 2. The community in gray is a disconnected community of maximum size, whereas a connected community of maximum size have no more than |V | 2 vertices.

  10 • opt(I) ≤ 11 • opt(I). Moreover, for any community S in G we can construct an independent set S in G of size |S| = |S |-|E|-2. Since opt(I ) ≥ |S | = |S|+|E|+2, in particular, when S is an optimum independent set, opt(I ) ≥ opt(I) + |E| + 2. In addition, opt(I) ≥ |S| = |S | -|E| -2, in particular, when S is an optimum community, opt(I) ≥ opt(I ) -|E| -2. Thus we obtain opt(I) = opt(I ) -|E| -2 and opt(I) -|S| = opt(I ) -|S |.

• Case 2 :

 2 n is even. Notice that Algorithm 1 starts with |C| = n 2 . If C is not a community in G, then due to Lemma 5.8, it exists a vertex v ∈ C such that d C (v) < d C (v). The selection of the vertex u ∈ C inside the loop ensures that the size of the cut between C and C strictly decreases at the end of the loop. Now observe that after the first loop, |C| = n 2 + 1. If C is not a community, according to Lemma 5.8, there exists a vertex v ∈ C such that d C (v) ≤ d C (v). Therefore the vertex u inside the loop has d C (u) ≤ d C (u). Obviously, after the second loop, |C| = n 2 . Since after each loop |C| alternates between n 2 and n 2 + 1, the cut between C and C strictly decreases every two loops, and the algorithm terminates. Thus the algorithm enters while-loop at most O(|E|) times and terminates when C is a community. Algorithm 1 implies several consequences. Firstly, it gives a 2-approximation algorithm since any community has size at most |V | -1. Besides, it shows that the decision version associated to Max Community is in FPT when parameterized by the natural parameter k (i.e. the size of the solution). Indeed, if the parameter k ≤ |V | 2 , then a community of size greater than k can be found in polynomial time using Algorithm 1. On the other hand, if k > |V | 2 , then we have |V | < 2k and an exhaustive research can be done in O(2 2k ) operations.

H 1 H 2 Figure 5 . 4 :

 254 Figure 5.4: Two Hamiltonian cubic graphs H 1 and H 2 with 8 vertices in which there is no community of size 2•8+1 3

Definition 5 . 15 .

 515 Let G = (V, E) be a Hamiltonian cubic graph and k := |V |-1 3

3 .Definition 5 . 16 .

 3516 Due to the structure of the graph, we can highlight specific sets of vertices of a Hamiltonian cubic graph: Let G = (V, E) be a Hamiltonian cubic graph, and k := |V |-1 3

Lemma 5 . 23 .

 523 Let G = (V, E) be a Hamiltonian cubic graph with no good shift and k := |V |-1 3

Proof. 3 = 5 . 3 .

 353 Let d := gcd(k + 1, |V |). Since G has no good shift, according to Lemma 5.21 and Corollary 5.22, d ∈ {2, 4} and |V | = 3k -1 or |V | = 3k + 1. From Corollary 5.19, we know that each vertex in V belong to either L or R. • Case 1: G is of type RLRL. Since |V | is even, then |P | is even. Therefore, since two vertices i, i + 1 ∈ P do not both belong to L or R, then the vertex -k belongs to L. Then the set P := {0, 1, • • • , -k} fulfills the requirements. • Case 2: G is of type RRLL. Consider the set P := {1, 2, • • • , -k + 1}. According to Lemma 5.21, since d = 4, |V | = 3k -1. Hence, -k + 1 = 2 -(k + 1) ∈ < 2 >. Thus -k + 1 ∈ L and P fulfills the requirements. Recall that the graphs H 1 and H 2 with 8 vertices showed in Figure 5.4 have no community of size 2•|V |+1 We show in Theorem 5.25 that they are the only cubic Hamiltonian graphs in which there is no community of size 2•|V |+1 Before proving the main theorem, we first deal with small graphs (|V | < 20) that are particular cases that need to be treated independently. Proposition 5.24. Let G = (V, E) be a Hamiltonian cubic graph not isomorphic to H 1 or H 2 with |V | < 20. Then there is a community of size 2•|V |+1

3 . 3 .From Theorem 5 .Corollary 5 . 26 .

 335526 which implies c(k -3), c(k -2) ∈ P . We show that either c(k -1) ∈ P or c(k) ∈ P . Suppose that c(k) / ∈ P . Then since k ∈ L, we have c(k) = 0. Since k -1 ∈ L, we have c(k -1) ∈ {-1, 0, 1, • • • , k -3}. Since 0 = c(k) and -1 ∈ L, then c(k -1) = -1 and c(k -1) = 0. Thus c(k -1) ∈ {1, 2, ..., k -3} ⊂ P . Thus either c(k -1) ∈ P or c(k) ∈ P . Now, if c(k -1) ∈ P , then since c(k -3) ∈ P , the set P \ {k -2} is a community of size 2•|V |+1 Else, c(k) ∈ P and then since c(k -2) ∈ P , the set P \ {k -1} is a community of size 2•|V |+1 25 and using Lemma 5.10, we obtain the following corollary: Given a cubic graph G = (V, E) and a Hamiltonian cycle of G, a community of maximum size can be found in linear time.

  where L contains := m•(n-k-1)-k+1 vertices, M := {e : e ∈ E} and N := V .

Figure 5 . 5 : 3 . 5 . 29 .

 553529 Figure 5.5: Example of the transformation Γ with k = 3.

Figure 5 . 6 :Proposition 5 . 31 .

 56531 Figure 5.6: A caterpillar T = (V, E) where the 5 vertices in gray cannot be extended into a community.

1 Figure 6 . 1 :

 161 Figure 6.1: A split graph in which there is no partition into two 2-clubs but there is a partition into two cliques in the squared graph. Some edges are dotted in G 2 in order to highlight the partition into two cliques.

Monotone 3 -Theorem 6 . 1 . 2 -

 3612 Sat Input : A set X of variables, a collection C of clauses over X which contains either only negated variables or only positive variables such that for each clause c ∈ C, |c| = 3. Question : Is there a satisfying truth assignment for C ? Partition into 2-clubs is NP-hard even on split graphs. Proof. We reduce Monotone 3-Sat to 2-Partition into 2-clubs on split graphs. Let I = (X, C) be an instance of Monotone 3-Sat with X the set of variables and C the set of clauses of size three, each clause being either positive or negative. We denote C 1 the subset of C of positive clauses and C 0 the subset of C of negative ones. We define a split graph G = (V = S ∪ K, E) as an instance of 2-Partition into 2-clubs as follows (see Fig. 6.2).

  join any two vertices of K by an edge in E so the subgraph induced by K becomes a clique, and we obtain a split graph G = (S ∪ K, E). Notice that |S| = O(|C| 2 ) and |K| = O(|C| 4 + |X|), then the size of the instance G is polynomial in |X| and |C|.

x 1 x 2 x 3 x 4 x 5 x 6 .

 6

k 0 s 0 Figure 6 . 3 :

 063 Figure 6.3: The graph G and a set of edges (represented by dotted lines) of minimum size to add to make G having diameter 2 (a minimum dominating set is given in gray).

Figure 6 . 4 :Conjecture 6 . 3 . 2 +

 64632 Figure 6.4: A split graph and its spanning subtree of diameter 4

2 + 2 + 2 +

 222 For each pair of vertices {x, y} in D, xy belongs to E . Moreover, for each v / ∈ D, choose any edge vx with x ∈ D in E . Notice that |E | = b(b-1) |V | -b and it is easy to see that G is a spanning subgraph of diameter 3. Now let G = (V, E ) be a spanning subgraph of G of diameter 3 such that |E | ≤ b(b-1) |V | -b for some integer b and let D be a minimum dominating set of G. From Conjecture 6.3, |E | ≥ |D|(|D|-1) |V | -|D|. Thus, b(b -3) ≥ |D|(|D| -3). Since b, |D| ≥ 1, we obtain b ≥ |D|. Thus, there exists a dominating set of size less than b in G.

Figure 6 . 5 :

 65 Figure 6.5: A split graph, a graph almost split of length 1 and a graph almost split of length 2

Figure 7 . 1 :

 71 Figure 7.1: Relationship among some classes of (connected) graphs, where an arrow from a class to another indicates that the first class contains the second one. We compare the hardness of Max Independent 2-Clique and Max Independent Set in studied graph classes. Max Independent 2-Clique is NP-hard on graph classes at the top of the figure (hatched area) and is polynomial-time solvable on graph classes at the bottom (non-hatched area). Max Independent Set is NP-hard on graph classes on the left of the figure (dotted area) and is polynomial-time solvable on graph classes on the right (non-dotted area).

Proposition 7 . 15 .

 715 Max Independent 2-Clique is linear-time solvable on cographs.Proof. Consider a cograph G with n vertices v 1 , . . . , v n . Given a binary cotree representation T of G with O(n) nodes, we show in the following how to solve Max Independent 2-Clique recursively.

2 -

 2 clique of I of size at least 2 and let S be the set of all copies of vertices from V in S . Since opt(I) = opt(I ) -1 and |S| = |S | -1, we obtain opt(I) -|S| = opt(I ) -|S |.

Figure 7 . 4 :

 74 Figure 7.4: The bipartite graph G , an instance of Max Independent 2-Clique

  We have |S| ≥ |S | and then opt(I) ≥ |S| ≥ |S | = opt(I ) when S is an optimal solution. Using that opt(I ) ≥ • opt(I) we get opt(I ) = • opt(I) and we obtain: (I, S) = opt(I) |S| -1 ≤ • opt(I ) • |S | -1 = (I , S ) Since we clearly have opt(I ) ≤ p(|I|)

Figure 7 . 5 :

 75 Figure 7.5: The graph G for which the corresponding line graph L(G ) is an instance of Max Independent 2-Clique

Theorem 7 . 22 .

 722 Max Independent 2-Clique is APX-hard on line graphs.

E 1 ∩

 1 S . We have |S | -|S| ≤ n which implies n + |S| ≥ |S |. Then we obtain opt(I) -|S| ≤ opt(I ) -n -|S| = opt(I ) -(n + |S|) ≤ opt(I ) -|S |.

1 3 = 5 .

 35 Comparaison des complexités de Max Independent Set et Max Independent 2-Clique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Zachary's karate club given in [71]. . . . . . . . . . . . . . . . . . . . . . . 2.1 The construction of the boolean circuit C from G. . . . . . . . . . . . . . . 3.1 A social network partitioned into intuitive communities . . . . . . . . . . . 3.2 Graph illustrating s-cliques, s-clubs for s = 2. {1, 2, 3, 4, 5}, {2, 3, 4, 5, 6} are 2-cliques meanwhile {1, 2, 3, 4}, {1, 2, 3, 5}, {2, 3, 4, 5, 6} are 2-clubs. . .3.3 The minimum (x, y)-cut gives an alliance containing x . . . . . . . . . . . . 3.4 A graph in which all LS sets (H 1 , H 2 , H 3 , H 4 ) are framed except trivial ones (singletons and the set of all vertices) . . . . . . . . . . . . . . . . . . . . . 3.5 A graph in which the subset H is a lambda set but not an LS set. . . . . . 3.6 The black and white vertices form a satisfactory partition, but is not a community structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Structural balance: Each labeled triangle must have 1 or 3 positive edges . 3.8 Example of an overlapping partition with 4-clique communities. . . . . . . 3.9 Dendrogram of the communities found in the Zachary Karate Club Network with the algorithm of Girvan and Newman in [82]. Each horizontal line gives a partition into communities. . . . . . . . . . . . . . . . . . . . . . . . . . 3.10 In this graph, the edge in the middle has a greater edge-betweenness than all other edges since all shortest paths connecting vertices from C 1 to C 2 run through it. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Two different 2-partitions for the same graph (given by the black and white colors) in which each part has at least 2 vertices. In the first partition, x does not satisfy the proportion condition of a community structure since the proportion of neighbors in the white part is 1 3 but the proportion of neighbors in the black partition is 2 3 . The second partition gives a 2-community structure. 4.2 A weak 2-community structure of a graph (presented by the colors black and white) in which the vertex v does not satisfy the proportion condition of a 2-community structure but satisfies the weak proportion condition of a weak 2-community structure from Definition 4.2. . . . . . . . . . . . . . . . 4.3 A complete graph in which a 3-community structure is given by the colors black, gray and white. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 A disconnected graph with an isolated vertex in which there is no community structure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Applying one step in Case 2(A) on the gray vertex decreases the size of the cut by one and creates two vertices in C 1 with 3 in-neighbors. . . . . . 4.6 SplittingC 2 when |N | = 4 (vertices in N are in gray) . . . . . . . . . . . 4.7 A 2-community structure {C 1 , C 2 } (C 1 in white, C 2 in black) for other graphs on 5 vertices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.8 Sketch of the three stages of the algorithm to compute a 2-community structure in a graph of maximum degree 3. Candidates vertices to be moved are in gray. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.9 An example of a graph in which all 2-community structures are balanced . 4.10 A cross gadget and a graph of maximum degree 3 without balanced 2community structure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.11 A tree of maximum degree 3 in which any balanced 2-community structure (or even balanced weak 2-community structure) is disconnected (an example of a balanced 2-community structure is presented by the black and white colors) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.12 A graph with 10 vertices that does not contain any 2-community structure 4.13 A schematic representation of a graph in G. . . . . . . . . . . . . . . . . . 5.1 Example of the transformation Γ. . . . . . . . . . . . . . . . . . . . . . . . 5.2 A cubic graph where the community of maximum size (in gray) is disconnected.102 5.3 A caterpillar T = (V, E) constructed by two stars S d for some integer d such that their center are joined by a path of length 2. The community in gray is a disconnected community of maximum size, whereas a connected community of maximum size have no more than |V | 2 vertices. . . . . . . . . 5.4 Two Hamiltonian cubic graphs H 1 and H 2 with 8 vertices in which there is no community of size 2•8+1 . . . . . . . . . . . . . . . . . . . . . . . 5.5 Example of the transformation Γ with k = 3. . . . . . . . . . . . . . . . . 5.6 A caterpillar T = (V, E) where the 5 vertices in gray cannot be extended into a community. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 Independent 2-cliques

  7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Complexity jump from planar graphs to apex graphs . . . . . . . . . . . . 7.4 Graph classes with polynomial-time algorithms . . . . . . . . . . . . . . . . 7.4.1 Graph classes related to the degree . . . . . . . . . . . . . . . . . . 7.4.2 Finding an independent 2-clique in the neighborhood of a vertex . . 7.4.3 Other graph classes in which both problems are polynomial-time solvable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5 NP-hardness and non-approximability . . . . . . . . . . . . . . . . . . . . . 7.5.1 Split graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5.2 Bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5.3 Line graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	8 Conclusions

  and |C i | ≥ 4, the vertex i has no neighbor in C i except a center of C

i (otherwise i could establish a new set with such an additional neighbor and increase the number of parts without decreasing g). Then, there are at least two vertices in C i that are not neighbors of i (denote the corresponding two non-edges e , e ∈ E). Then, since there is at most one non-edge in E between {i} and C which is contributing in g(Π ), moving i from C i to C does not change the number of parts but increases the value of g by counting e and e , contradiction.

• If |C| ≥ 3,

similarly to the previous case, we can assume that i has a center of C and of C i as neighbors but does not have any other neighbors in C i or C. From (4.1), we obtain |C i | -1 > |C| and g would increase if i is moved to C, contradiction.

  and it is easy to check that {C 1 , C 2 } is a connected 2-community structure. Any complete split graph has a 2-community structure. Moreover, such community structure can be found in linear time.

	Proposition 4.5.

  2•|V |+1

  Let S p (resp. S n ) be a subset of |K p | (resp. (|K n |) vertices and introduce a perfect matching in E between K p (resp. K n ) and S p (resp. S n ). Moreover, for each couple {z 1 , z 2 } ⊂ S p ∪ S p (resp. S n ∪ S n ) such that they have no common neighbor in K p ∪ K x (resp. K n ∪ K x ), introduce an additional vertex w in a subset K p (resp. K n ) and introduce z 1 w, z 2 w ∈ E. Notice that |K p | = O(|C 1 | 4 ) and

1. Je remercie également Janka Chlebíková qui m'a accueilli chaleureusement à Portsmouth. Merci pour ton soutien, ton suivi (très) rigoureux, et surtout ta gentillesse.2. NB : tous les mots sont transparents.3. Je remercie Meriem, une amie sincère que j'espère continuer de voir après la thèse, ainsi que Yassine mon compatriote, merci pour ta gentillesse, ta spontanéité et ton honnêteté. Merci à vous deux qui m'ont donné une si bonne image de la Tunisie et qui m'y ont si bien accueilli (un grand merci à Raja pour sa traduction !).

Perfect graphs are graphs in which any subgraph satisfies that the minimum number of colors in a coloring equals the maximum size of a clique.

A unit disk graph is the intersection graph of some set of disks of diameter 1 in the euclidean plane.

networks with a low diameter.

and ensuring connectivity of the partition {C 1 , C 2 }.

< |C 1 |-1 n-1 d(v) that implies p < |C 1 |-1 n-1 d(v) < d in (v). Then necessarily d in (v) ≥ 1 2 d(v) for every vertex v ∈ V , that is G is a yes-instance of Balanced Satisfactory Partition.

in G.

It is proved in[5] that for a finite set H of connected graphs, Max Independent Set is NP-hard on the class of H-free graphs if no member of H is either a path or a tree with one vertex of degree 3 and the other vertices of degree at most

Vertices of N i are added to S i one by one until it is not possible to add a vertex from N i \ S i to S i without compromising the fact that S i is an independent 2-clique.

Proposition 7.21. Max Independent 2-Clique is NP-hard on line graphs.

Remerciements

Hardness results

In this section we prove two major results regarding the complexity of Max Community. We show that it is NP-hard and APX-hard, even for split graphs.

NP-hardness

We establish a reduction from the decision version associated to Max Independent Set which was proved NP-hard in [START_REF] Karp | Reducibility among Combinatorial Problems[END_REF]:

Max Independent Set Input: A graph G = (V, E). Output: A subset S of vertices of minimum size such that any edge in E is adjacent to a vertex in S.

In order to do so, we first introduce the transformation involved in the reduction and some lemmas that will be necessary for the main theorem. Definition 5.2. Let G = (V, E) be a connected graph. We define the construction Γ transforming the graph G into Γ(G) = G (V , E ) as it follows (see Figure 5. [START_REF] Abbas | Clustering bipartite, chordal graphs: Complexity, sequential, parallel algorithms[END_REF]

for an example):

• V := M ∪ N ∪ {z 1 , z 2 }, where M := {e : e ∈ E}, N := V and z 1 , z 2 are two new vertices;

• for all e ∈ M and all u ∈ N , the edge (e, u) ∈ E if and only if u / ∈ e;

• the subgraph G [{z 1 , z 2 } ∪ M ] is complete.

Notice that the construction from Definition 5.2 can be done in polynomial time. Moreover, Γ(G) yields a connected graph if and only if G is not isomorphic to a star. • opt(G). Theorem 5.12. Max Community is APX-complete.

Polynomial-time solvability in some graph classes

Some easy graph classes

First notice that the problem is easy to solve in graphs of maximum degree 2. Indeed, given a connected graph G = (V, E), any community C cannot have a size greater than

since of Lemma 5.10. Then, Algorithm 1 gives a community of maximum size.

Even if Max Community is NP-complete on split graphs, we show that Max Community can be solved easily on some particular split graphs, namely threshold graphs, by noticing that a community of any size can be found in linear time. Proof. Since G is a threshold graph, we can order the vertices of the independent set as Proof. Let G = (V, E) be a threshold graph. According to Proposition 5.13, a community of size |V | -1 can be found using the structure of threshold graphs. Since threshold graphs can be recognized in linear time [START_REF] Heggernes | Linear-time certifying recognition algorithms and forbidden induced subgraphs[END_REF], the result follows.

Hamiltonian cubic graphs

Now we prove that any Hamiltonian cubic graph G = (V, E) (except two graphs, see Figure 5.4) has a community of the maximum possible size A Hamiltonian cubic graph G = (V, E) can be described as a set of vertices V = {0, 1, . . . , |V | -1}, a Hamiltonian cycle and a set of edges between non-successive vertices useful to display an almost good shift P and a vertex to remove from P in order to obtain a community in G. This result comes from a basic property of the cyclic group Z/nZ that we recall on Lemma 5.20. Lemma 5.20. Let n ≥ 4 be some integer, k := n-1

Proof. First we prove that for any u ≥ d, u ∈< i > for some i ∈ {0, 1,

In order to prove the second part, we first show that

We prove that n = p by verifying that n divides p and p divides n . First, notice that u

The other cases can be proved using the same reasoning.

3

. Since G is cubic, its number of vertices is even. From Lemma 5.21, gcd(k + 1, |V |) ∈ {1, 2, 3, 4}. If gcd(k + 1, |V |) ∈ {1, 3}, then there exists a good shift from Corollary 5.22. We suppose then that gcd(k + 1, |V |) ∈ {2, 4}. The following cases remain: . In the second case, P \ {3} is a community of size partition {V 1 , V 0 } of V into two 2-clubs as follows. Let K 1 (resp. K 0 ) be the set of all vertices x i ∈ K x such that the corresponding variables x i ∈ X have been assigned to true (resp. false). Define

since z 1 and z 2 always have a common neighbor either in K p , K p or K 1 . Then, for any pair of vertices

The same reasoning can be done for V 0 by symmetry. Thus, {V 1 , V 0 } is a partition of V into two 2-clubs.

Suppose now that there is a partition {V 1 , V 0 } of V such that V 1 and V 0 are 2-clubs. First notice that for any vertex z 1 ∈ S p ∪ S p and any z 2 ∈ S n , d(z 1 , z 2 ) = 3. Then we can assume without loss of generality that (S p ∪ S p ) ⊂ V 1 and S n ⊂ V 0 . This implies that K p ∪ K p ⊂ V 1 since any two vertices of S p ∪ S p must have a common neighbor in V 1 . By symmetry, we can also conclude that S n ∪S n ∪K n ∪K n ⊂ V 0 . Then, we show that assigning all variables in X corresponding to the vertices in K x ∩ V 1 to true and all variables in X corresponding to the vertices in K x ∩ V 0 to false is an assignment satisfying all clauses in C. By contradiction, suppose that there is a clause in c i ∈ C which is false with respect to this assignment. Wlog we consider that the clause is a positive one. Then, all variables in c i are assigned to false and the corresponding vertices in K x are in C 0 whereas the two vertices c i,1 , c i,2 in S p corresponding to the clause c i are in V 1 . Then, by construction, c i,1 and c i,2 have no common neighbor in V 1 and thus V 1 is not a 2-club. Thus, the defined assignment for X satisfies all clauses in C.

In [START_REF] Chang | On the complexity of graph clustering with bounded diameter[END_REF], Chang et al. claimed that determining if the complement of the squared graph is bipartite allows to determine if there is a partition of a graph into two 2-clubs. Actually, this only allows to determine if there is a covering into two 2-clubs (i.e. a set {C 1 , C 2 } of subsets of V such that C 1 ∪ C 2 = V and C 1 , C 2 are 2-clubs). In fact, there is a covering into two 2-clubs if and only if the complement of the squared graph is bipartite. Indeed, if the complement of the squared graph is bipartite with the 2-partition (A, B), a covering into two 2-clubs can be determined by considering the partition (A, B) and for any two vertices which are not at distance 2 in the subgraph induced by one part, add a common neighbor of those two vertices into this part (without removing it from the original part). Notice that the existence of such bipartition ensures that such vertex always exists. In Figure 6.1, c would belong to both 2-clubs.

It can be observed that 2-Partition into 2-clubs is easy to solve on split graphs of diameter 2, since considering any vertex of the independent set in one part and the rest of the graph in the other part constitutes a 2-partition into two 2-clubs.

Edge editing

We now focus on problems in which edge adding or removal can ensure or maintain some distance between the vertices of the resulting subgraph.

S S

Complexity jump from planar graphs to apex graphs

According to [START_REF] Garey | Some simplified NP-complete graph problems[END_REF], Max Independent Set is known to be NP-hard in planar graphs, and thus also in apex graphs. On the other hand, we prove that Max Independent 2-Clique is polynomial-time solvable on planar graphs but NP-hard on apex graphs. This shows that inserting or removing a single vertex in a graph may dramatically change the complexity of Max Independent 2-Clique.

Theorem 7.2. Max Independent 2-Clique is NP-hard on apex graphs.

Proof. We establish a polynomial reduction from Max Independent Set on cubic planar graphs, which is proved to be NP-hard in [START_REF] Garey | Some simplified NP-complete graph problems[END_REF], to Max Independent 2-Clique on apex graphs. Let G = (V, E) be a cubic planar graph, an instance of Max Independent Set.

The instance G = (V , E ) of Max Independent 2-Clique is defined by inserting an additional vertex z that is adjacent to every vertex of V . It is easy to see that {z} itself is a one-element non-extendable independent 2-clique, while the independent 2-cliques of G not containing z are precisely the independent sets of G. Proof. Cubic graphs on n vertices have 3n/2 edges, thus the graph constructed in the proof of Theorem 7.2 is of order n+1 and has 5n/2 edges, yielding average degree less than 5.

In order to prove that Max Independent 2-Clique is polynomial-time solvable on planar graphs, we use a famous theorem introduced by Courcelle in [START_REF] Courcelle | The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues[END_REF] which states that any problem expressible in Monadic Second-Order Logic is linear-time solvable for graphs of bounded treewidth. This allows to show first the following: Theorem 7.4. Max Independent 2-Clique is linear-time solvable on graphs with bounded treewidth.

Proof. We observe that the problem is expressible in Monadic Second-Order Logic:

Since any problem expressible in Monadic Second-Order Logic is linear-time solvable for graphs of bounded treewidth (see [START_REF] Courcelle | The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues[END_REF]), α =2 can be determined in linear time in graphs of bounded treewidth.

Based on this result, we prove the following result. Proof. Let G = (V, E) be a planar graph and v ∈ V any vertex. Then all the other vertices in an independent 2-clique S containing v are at distance exactly 2 apart from v. Further, the 2-clique property for S \ {v} is ensured by vertices within distance at most 3 from v. Thus, the vertices relevant for S to be an independent 2-clique induce a subgraph G in G such that G belongs to the class of '4-outerplanar' graphs. Graphs which are 4-outerplanar have treewidth at most 11 (more generally, all k-outerplanar graphs have treewidth at most 3k -1, due to [START_REF] Bodlaender | A partial k-arboretum of graphs with bounded treewidth[END_REF]). Then, using Theorem 7.4, a polynomial-time algorithm for Max Independent 2-Clique in planar graphs consists in solving the problem for all subgraphs G (which have treewidth at most 11) defined from each vertex v of G and choose a solution of maximum size.

Concerning the parameterized complexity, we can show the following.

Theorem 7.6. The parameterized problem associated with Max Independent 2-Clique with the natural parameter is in FPT on apex graphs.

Proof. Let G = (V, E) be an apex graph and x ∈ V a vertex such that G -x is planar. Since any planar graph is 4-colorable [START_REF] Kenneth | Every planar map is four colorable : Part i. discharging[END_REF], the size of an independent set in G

4 , and so is the size of an independent 2-clique in G. Thus, considering the parameter k, if |N (x)| ≥ 4k, then the answer is yes.

If now |N (x)| < 4k, as discussed in the previous proof, considering any vertex v belonging to an independent 2-clique S in G, the 2-clique property for S \ {v} is ensured In this situation v, z, z with their three pairwise neighbors create a 6-cycle sharing the edge wz with C and thus G is not a cactus.

• u has at least 3 neighbors and w has only v as a neighbor in N u . Let z be a vertex of N u \ {v , v}. Then z and z must have a common neighbor x (which cannot be u or w but could be w ). Then wz is a common edge of C and the 6-cycle (u, z , x, z, w, v, u) and thus G is not a cactus.

• u has at least 3 neighbors and w has at least 2 neighbors in N u , say v and z . Then vw is a common edge of C and the 4-cycle (u, v, w, z , u) and thus G is not a cactus.

This lemma implies the following theorem:

Theorem 7.11. Any (C 3 , C 6 )-free graph G satisfies α =2 (G) = ∆(G) and Max Independent 2-Clique is linear-time solvable on it.

Proof. By Lemma 7.10, in (C 3 , C 6 )-free graphs any independent 2-clique is the neighborhood of some vertex. Then, an independent 2-clique of maximum size is given in linear time by taking the neighborhood of a vertex of maximum degree since two vertices in the neighborhood of any vertex are not adjacent in C 3 -free graphs.

Finally, Lemma 7.10 allows to give a polynomial-time algorithm for Max Independent 2-Clique on cactus. Proposition 7.12. Max Independent 2-Clique is linear-time solvable on cactus graphs.

Proof. Since all cactus graphs have a bounded treewidth, an implicit algorithm running in linear time follows from the proof of Theorem 7.4.

Being more constructive, let G = (V, E) be a cactus which is not isomorphic to C 6 . Let {v 1 , . . . , v n } be the set of vertices in G and for any i ∈ {1, . . . , n}, note N i the neighborhood (that consists of adding a clique of the same size as the size of the graph and joining every vertex from the original graph to all vertices in this clique).

• Max Independent 2-Clique is NP-hard on K 4 -free graphs, since Max Independent Set is NP-hard on K 3 -free graphs [5].

We now investigate graph classes in which Max Independent 2-Clique is NP-hard while Max Independent Set is polynomial-time solvable.

Split graphs

We first consider a graph class containing threshold graphs, namely the class of split graphs, for which Max Independent 2-Clique becomes NP-hard (and even not n 1-εapproximable). Since Max Independent Set is polynomial-time solvable on chordal graphs [START_REF] Frank | Some polynomial algorithms for certain graphs and hypergraphs[END_REF], it is also polynomial-time solvable on split graphs. Proposition 7.16. Max Independent 2-Clique is NP-hard on split graphs.

Proof. We reduce Max Clique on general graphs to Max Independent 2-Clique on split graphs. Let G = (V, E) be an instance of Max Clique. We define an instance G = (V , E ) of Max Independent 2-Clique on split graphs as follows: for every vertex v i ∈ V we consider a vertex v i ∈ V and for every edge e ∈ E we consider a vertex e in V . We also add an additional vertex z in V . Moreover, for any edge e = v 1 v 2 ∈ E we associate two edges in E , the edges v 1 e and v 2 e . Finally, the subgraph induced by vertices e ∈ V and z is defined to be a clique. Now it is easy to see that C is a clique of size at least k in G if and only if C = {v : v ∈ C} ∪ {z} is an independent 2-clique of size at least k + 1 in G . On the other hand, given an independent 2-clique S, if z / ∈ S and e ∈ S holds for some (only one) e ∈ E, then we can modify S to an independent 2-clique of the same size by replacing e with z. Hence, the maximum can always be attained by involving z. Theorem 7.17. Max Independent 2-Clique is W [START_REF] Abbas | Clustering bipartite, chordal graphs: Complexity, sequential, parallel algorithms[END_REF]-complete on split graphs.

Proof. From Theorem 7.1, we know that Max Independent 2-Clique belongs to W [START_REF] Abbas | Clustering bipartite, chordal graphs: Complexity, sequential, parallel algorithms[END_REF]. On the other hand, the reduction in Proposition 7.16 is an FPT-reduction. Since Max Clique is W[1]-hard on general graphs [START_REF] Downey | Fixed-parameter tractability and completeness II: On completeness for W[1[END_REF], then Max Independent 2-Clique is also W [START_REF] Abbas | Clustering bipartite, chordal graphs: Complexity, sequential, parallel algorithms[END_REF]-hard on split graphs. Theorem 7.18. Max Independent 2-Clique is not n 1-ε -approximable in polynomial time on split graphs unless P=NP.

Proof. We construct an E-reduction from Max Clique. Let I = (V, E) be an instance of Max Clique and let I = (V , E ) be the corresponding instance of Max Independent 2-Clique, considering the same reduction as in Proposition 7.16. First, notice that opt(I) = opt(I ) -1, thus we have opt(I ) ≤ 2 • opt(I). Now let S be an independent 6.1 A split graph in which there is no partition into two 2-clubs but there is a partition into two cliques in the squared graph. Some edges are dotted in G 2 in order to highlight the partition into two cliques. . . . . . . . . . . . . 6.2 The split graph G defined from the instance I = (X, C) with X = {x 1 , x 2 , x 3 , x , x 5 , x 6 } and C = {x 1 ∨x 2 ∨x 3 , x 4 ∨x 5 ∨x 6 , x 3 ∨x 5 ∨x 6 , x 1 ∨x 2 ∨x 3 , x 1 ∨x 3 ∨x 5 , x 4 ∨x 5 ∨x 6 , }121