Search

Labelings that are used in graph decompositions are called Rosa-type labelings. The gamma-labeling of an almost-bipartite graph is a natural generalization of an alpha-labeling of a bipartite graph. It is known that if a bipartite graph G with m edges possesses an alpha-labeling or an almost-bipartite graph G with m edges possesses a gamma-labeling, then the complete graph K_{2mx+1} admits a cyclic G-decomposition. A variation of an alpha-labeling is introduced in this paper by allowing additional vertex labels and some conditions on edge labels and show that whenever a bipartite graph G admits such a labeling, then there exists a supergraph H of G such that H is almost-bipartite and H has a gamma-labeling.

An alliance in a graph is a set of vertices that is either safe under attacks from the neighborhood (defensive), capable of attacking its neighbors (offensive), or simultaneously defensive and offensive (powerful). An alliance is global if all nonmembers are adjacent to some members of the alliance. The concept of alliances was introduced by Kristiansen et al. (2004). After that many results concerning the complexity for finding a minimum alliance were shown. It was shown that the problem of finding a minimum alliance of any variant is NP-hard in general. For some variants, it was shown that the problem becomes polynomial-time solvable when restricted to trees or series–parallel graphs. In this paper, we show that the problems for all variants are efficiently solvable for much larger graph classes. We present a polynomial-time algorithm for graphs of bounded clique-width. We also show that the problem is fixed-parameter tractable when parameterized by the vertex cover number.

Many real world operational research problems, such as frequency assignment and exam timetabling, can be reformulated as graph colouring problems (GCPs). Most algorithms for the GCP operate under the assumption that its constraints are fixed, allowing us to model the problem using a static graph. However, in many real-world cases this does not hold and it is more appropriate to model problems with constraints that change over time using an edge dynamic graph. Although exploring methods for colouring dynamic graphs has been identified as an area of interest with many real-world applications, to date, very little literature exists regarding such methods. In this paper we present several heuristic methods for modifying a feasible colouring at time-step t into an initial, but not necessarily feasible, colouring for a “similar” graph at time-step t+1t+1 . We will discuss two cases; (1) where changes occur at random, and (2) where probabilistic information about future changes is provided. Experimental results are also presented and the benefits of applying these particular modification methods are investigated.

We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of $n$ vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex $u$ to vertex $v$ is a path from $u$ to $v$ where successive path edges have strictly increasing labels. A graph is temporally connected iff there is a $(u,v)$-journey for any pair of vertices $u,v,~u\not= v$. We first give a simple polynomial-time algorithm to check whether a given temporal graph is temporally connected. We then consider the case in which a designer of temporal graphs can \emph{freely choose} availability instances for all edges and aims for temporal connectivity with very small \emph{cost}; the cost is the total number of availability instances used. We achieve this via a simple polynomial-time procedure which derives designs of cost linear in $n$. We also show that the above procedure is (almost) optimal when the underlying graph is a tree, by proving a lower bound on the cost for any tree. However, there are pragmatic cases where one is not free to design a temporally connected graph anew, but is instead \emph{given} a temporal graph design with the claim that it is temporally connected, and wishes to make it more cost-efficient by removing labels without destroying temporal connectivity (redundant labels). Our main technical result is that computing the maximum number of redundant labels is APX-hard, i.e., there is no PTAS unless $P=NP$. On the positive side, we show that in dense graphs with random edge availabilities, there is asymptotically almost surely a very large number of redundant labels. A temporal design may, however, be \emph{minimal}, i.e., no redundant labels exist. We show the existence of minimal temporal designs with at least $n \log{n}$ labels.

Constructing a graph to represent the structure among data objects plays a fundamental role in various data mining tasks with graph-based learning. Since traditional pairwise distance-based graph construction is sensitive to noise and outliers, sparse representation based graphs (e.g., ź1-graphs) have been proposed in the literature. Although ź1-graphs prove powerful and robust for many graph-based learning tasks, it suffers from weak locality and high computation costs. In this paper, we propose a locality weighted sparse representation (LWSR), which aims for good preservation of the locality structure among data objects and a significant reduction of the computation time. LWSR approximates each object as a sparse linear combination of its nearest neighbors, and weights their corresponding coefficients by their distances to the target object. Experimental results show that LWSR-graph based learning methods outperform state-of-the-art methods in both effectiveness and efficiency for graph-based learning.

Graph is widely used to model data in various applications. With the rapid growth of many emerging applications such as Internet of Things, it is urgent to require the processing capability on large scale graphs with billions of vertices. Web graph is a typical case of graph data that is widely used for analyzing the structure, behavior and evolution of the World Wide Web. In this paper, we focus on optimal representation of large-scale Web graphs. Our work is motivated by the need of fit large-scale graphs into the main memory and carry out analyze on them. By analyzing the adjacency matrix of Web graphs, we find two characteristics on the distribution of 1s in the matrix. Firstly, only a very small proportion of elements in the matrix are 1s. Secondly, majority of 1s gather around the principal diagonal and form a few number of clusters in the matrix. Based on these characteristics, we first develop a clustering mechanism to locate the clusters of 1s in the adjacency matrix. Then, we combine this clustering mechanism with a structure named K2-tree and propose an approach for representing large-scale Web graphs compactly. Basic idea of the approach is trying to compress a large number of zeros as a single zero. Experimental results show that, our approach not only reduces the space for representing a Web graph, but also reduces the time consumption for operations such as retrieving neighbors of any nodes on the graph; compared with existing approaches, our approach achieves the best space/time tradeoff.

Discriminative systems that can deal with graphs in input are known, however, generative or constructive approaches that can sample graphs from empirical distributions are less developed. Here we propose a Metropolis–Hastings approach that uses a novel type of graph grammar to efficiently learn proposal distributions in a data driven fashion. We report experimental results in a de-novo molecular synthesis problem where we show that the distribution of the molecules generated by the sampling procedure is accurate enough to improve a predictor's performance in a classification task.

Design patterns are strategies for solving commonly occurring problems within a given context in software design. In the process of re-engineering, detection of design pattern instances from source codes can play a major role in understanding large and complex software systems. However, detecting design pattern instances is not always a straightforward task. In this paper, based on the graph theory, a new design pattern detection method is presented. The proposed detection process is subdivided into two sequential phases. In the first phase, we concern both the semantics and the syntax of the structural signature of patterns. To do so, the system under study and the patterns asked to be detected, are transformed into semantic graphs. Now, the initial problem is converted into the problem of finding matches in the system graph for the pattern graph. To reduce the exploration space, based on a predetermined set of criteria, the system graph is broken into the possible subsystem graphs. After applying a semantic matching algorithm and obtaining the candidate instances, by analyzing the behavioral signature of the patterns, in the second phase, final matches will be obtained. The performance of the suggested technique is evaluated on three open source systems regarding precision and recall metrics. The results demonstrate the high efficiency and accuracy of the proposed method.

A modulator of a graph G to a specified graph class H is a set of vertices whose deletion puts G into H. The cardinality of a modulator to various tractable graph classes has long been used as a structural parameter which can be exploited to obtain FPT algorithms for a range of hard problems. Here we investigate what happens when a graph contains a modulator which is large but "well-structured" (in the sense of having bounded rank-width). Can such modulators still be exploited to obtain efficient algorithms? And is it even possible to find such modulators efficiently? We first show that the parameters derived from such well-structured modulators are strictly more general than the cardinality of modulators and rank-width itself. Then, we develop an FPT algorithm for finding such well-structured modulators to any graph class which can be characterized by a finite set of forbidden induced subgraphs. We proceed by showing how well-structured modulators can be used to obtain efficient parameterized algorithms for Minimum Vertex Cover and Maximum Clique. Finally, we use well-structured modulators to develop an algorithmic meta-theorem for deciding problems expressible in Monadic Second Order (MSO) logic, and prove that this result is tight in the sense that it cannot be generalized to LinEMSO problems., Comment: Accepted at WADS 2015

Locally-biased graph algorithms are algorithms that attempt to find local or small-scale structure in a large data graph. In some cases, this can be accomplished by adding some sort of locality constraint and calling a traditional graph algorithm; but more interesting are locally-biased graph algorithms that compute answers by running a procedure that does not even look at most of the input graph. This corresponds more closely to what practitioners from various data science domains do, but it does not correspond well with the way that algorithmic and statistical theory is typically formulated. Recent work from several research communities has focused on developing locally-biased graph algorithms that come with strong complementary algorithmic and statistical theory and that are useful in practice in downstream data science applications. We provide a review and overview of this work, highlighting commonalities between seemingly-different approaches, and highlighting promising directions for future work., Comment: 19 pages, 13 figures

Graph-based representations are experiencing a growing usage in visual recognition and retrieval due to their representational power in front of classical appearance-based representations. However, retrieving a query graph from a large dataset of graphs implies a high computational complexity. The most important property for a large-scale retrieval is the search time complexity to be sub-linear in the number of database examples. With this aim, in this paper we propose a graph indexation formalism applied to visual retrieval. A binary embedding is defined as hashing keys for graph nodes. Given a database of labeled graphs, graph nodes are complemented with vectors of attributes representing their local context. Then, each attribute vector is converted to a binary code applying a binary-valued hash function. Therefore, graph retrieval is formulated in terms of finding target graphs in the database whose nodes have a small Hamming distance from the query nodes, easily computed with bitwise logical operators. As an application example, we validate the performance of the proposed methods in different real scenarios such as handwritten word spotting in images of historical documents or symbol spotting in architectural floor plans.

Scalable algorithm based on bipartite graphs to perform transduction learning.Label propagation procedure that uses class information associated with vertices and edges.Better performance than state-of-the-art algorithms based on vector space or graphs.Comprehensive evaluation showing the proposal performance with few labeled instances.Optimization process using KL-Divergence. Transductive classification is an useful way to classify a collection of unlabeled textual documents when only a small fraction of this collection can be manually labeled. Graph-based algorithms have aroused considerable interests in recent years to perform transductive classification since the graph-based representation facilitates label propagation through the graph edges. In a bipartite graph representation, nodes represent objects of two types, here documents and terms, and the edges between documents and terms represent the occurrences of the terms in the documents. In this context, the label propagation is performed from documents to terms and then from terms to documents iteratively. In this paper we propose a new graph-based transductive algorithm that use the bipartite graph structure to associate the available class information of labeled documents and then propagate these class information to assign labels for unlabeled documents. By associating the class information to edges linking documents to terms we guarantee that a single term can propagate different class information to its distinct neighbors. We also demonstrated that the proposed method surpasses the algorithms for transductive classification based on vector space model or graphs when only a small number of labeled documents is available.

Graph processing is becoming a crucial component for analyzing big data arising in many application domains such as social and biological networks, fraud detection, and sentiment analysis. As a result, a number of computational models for graph analytics have been proposed in the literature to help users write efficient large scale graph algorithms. In this paper we present an alternative model for implementing graph algorithms using a linear algebra based specification. We first specify a set of linear algebra primitives that allows users to express graph algorithms by composition of linear algebra operations. We then describe a high performance implementation of these primitives using C $$++$$ and subsequently its integration with the Spark framework to achieve the scalability we need for large systems. We provide an overview of our implementation and also compare and contrast the expressiveness and performance of various algorithms implemented with our approach with that of the current Spark GraphX implementation of those algorithms.

We study the problem of discrepancy maximization on graphs: given a set of nodes $Q$ of an underlying graph $G$ , we aim to identify a connected subgraph of $G$ that contains many more nodes from $Q$ than other nodes. This variant of the discrepancy-maximization problem extends the well-known notion of “bump hunting” in the Euclidean space [1] . We consider the problem under two access models. In the unrestricted-access model, the whole graph $G$ is given as input, while in the local-access model we can only retrieve the neighbors of a given node in $G$ using a possibly slow and costly interface. We prove that the basic problem of discrepancy maximization on graphs is $\mathbf {NP}$ -hard, and empirically evaluate the performance of four heuristics for solving it. For the local-access model, we consider three different algorithms that aim to recover a part of $G$ large enough to contain an optimal solution, while using only a small number of calls to the neighbor-function interface. We perform a thorough experimental evaluation in order to understand the trade offs between the proposed methods and their dependencies on characteristics of the input graph.

We present a parallelizable direct method for computing the solution to graph Laplacian-based linear systems derived from graphs that can be hierarchically bipartitioned with small edge cuts. For a graph of size $n$ that can be recursively partitioned into equal-sized sets with constant-size edge cuts, our method decomposes a graph Laplacian in time $O(n \log n)$ and then uses that decomposition to perform a linear solve in time $O(n \log n)$. Many real-world graphs, however, do not possess this property. So, we use this technique to design a preconditioner for graph Laplacians that do not have this property. Finally, we augment this preconditioner with a two-grid method that accounts for much of the preconditioner's weaknesses. We present an analysis of this method, as well as a general theorem for the condition number of a general class of two-grid support graph-based preconditioners. Numerical experiments illustrate the performance of the studied methods.

Knowledge extraction is very much possible from the community graph using graph mining techniques. The authors have studied the related definitions of graph partition in terms of both mathematical as well as computational aspects. To derive knowledge from a particular sub-community graph of a large community graph, the authors start partitioning the large community graph into smaller sub-community graphs. Thus, the knowledge extraction from the sub-community graph becomes easier and faster. The proposed approach of partition is done by detection of edges among the community members of dissimilar community. By studying existing techniques followed by different researchers, the authors propose a new and simple algorithm for partitioning the community graph into sub-community graphs using graph mining techniques. Finally, the authors have considered a benchmark dataset as example which verifies the strength and easiness of the proposed algorithm.

We give a fixed-parameter tractable algorithm that, given a parameter $k$ and two graphs $G_1,G_2$, either concludes that one of these graphs has treewidth at least $k$, or determines whether $G_1$ and $G_2$ are isomorphic. The running time of the algorithm on an $n$-vertex graph is $2^{O(k^5\log k)}\cdot n^5$, and this is the first fixed-parameter algorithm for Graph Isomorphism parameterized by treewidth. Our algorithm in fact solves the more general canonization problem. We namely design a procedure working in $2^{O(k^5\log k)}\cdot n^5$ time that, for a given graph $G$ on $n$ vertices, either concludes that the treewidth of $G$ is at least $k$, or: * finds in an isomorphic-invariant way a graph $\mathfrak{c}(G)$ that is isomorphic to $G$; * finds an isomorphism-invariant construction term --- an algebraic expression that encodes $G$ together with a tree decomposition of $G$ of width $O(k^4)$. Hence, the isomorphism test reduces to verifying whether the computed isomorphic copies or the construction terms for $G_1$ and $G_2$ are equal., Full version of a paper presented at FOCS 2014

The cut-rank of a set $X$ of vertices in a graph $G$ is defined as the rank of the $ X \times (V(G)\setminus X)$ matrix over the binary field whose $(i,j)$-entry is $1$ if the vertex $i$ in $X$ is adjacent to the vertex $j$ in $V(G)\setminus X$ and $0$ otherwise. We introduce the graph parameter called the average cut-rank of a graph, defined as the expected value of the cut-rank of a random set of vertices. We show that this parameter does not increase when taking vertex-minors of graphs and a class of graphs has bounded average cut-rank if and only if it has bounded neighborhood diversity. This allows us to deduce that for each real $\alpha$, the list of induced-subgraph-minimal graphs having average cut-rank larger than (or at least) $\alpha$ is finite. We further refine this by providing an upper bound on the size of obstruction and a lower bound on the number of obstructions for average cut-rank at most (or smaller than) $\alpha$ for each real $\alpha\ge0$. Finally, we describe explicitly all graphs of average cut-rank at most $3/2$ and determine up to $3/2$ all possible values that can be realized as the average cut-rank of some graph., Comment: 22 pages, 1 figure. The bound $x_n$ is corrected. Accepted to European J. Combinatorics

We prove that the combinatorial Weisfeiler-Leman algorithm of dimension $(3k+4)$ is a complete isomorphism test for the class of all graphs of rank width at most $k$. Rank width is a graph invariant that, similarly to tree width, measures the width of a certain style of hierarchical decomposition of graphs; it is equivalent to clique width. It was known that isomorphism of graphs of rank width $k$ is decidable in polynomial time (Grohe and Schweitzer, FOCS 2015), but the best previously known algorithm has a running time $n^{f(k)}$ for a non-elementary function $f$. Our result yields an isomorphism test for graphs of rank width $k$ running in time $n^{O(k)}$. Another consequence of our result is the first polynomial time canonisation algorithm for graphs of bounded rank width. Our second main result is that fixed-point logic with counting captures polynomial time on all graph classes of bounded rank width., Comment: 32 pages, 2 figures; second version corrects a small error in the proof of Theorem 1.1 and improves the presentation

In this paper we study the problem of finding a small safe set S in a graph G, i.e. a non-empty set of vertices such that no connected component of G[S] is adjacent to a larger component in \(G - S\). We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[2]-hard when parameterized by the pathwidth \(\mathsf {pw}\) and cannot be solved in time \(n^{o(\mathsf {pw})}\) unless the ETH is false, (2) it admits no polynomial kernel parameterized by the vertex cover number \(\mathsf {vc}\) unless \(\mathrm {PH} = \varSigma ^{\mathrm {p}}_{3}\), but (3) it is fixed-parameter tractable (FPT) when parameterized by the neighborhood diversity \(\mathsf {nd}\), and (4) it can be solved in time \(n^{f(\mathsf {cw})}\) for some double exponential function f where \(\mathsf {cw}\) is the clique-width. We also present (5) a faster FPT algorithm when parameterized by solution size.

Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic tractability: if the clique-width of a graph class ${\cal G}$ is bounded by a constant, a wide range of problems that are NP-complete in general can be shown to be polynomial-time solvable on ${\cal G}$. For this reason, the boundedness or unboundedness of clique-width has been investigated and determined for many graph classes. We survey these results for hereditary graph classes, which are the graph classes closed under taking induced subgraphs. We then discuss the algorithmic consequences of these results, in particular for the Colouring and Graph Isomorphism problems. We also explain a possible strong connection between results on boundedness of clique-width and on well-quasi-orderability by the induced subgraph relation for hereditary graph classes.

We almost completely resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs \(H_1\) and \(H_2\). Schweitzer settled the complexity of this problem restricted to \((H_1,H_2)\)-free graphs for all but a finite number of pairs \((H_1,H_2)\), but without explicitly giving the number of open cases. Grohe and Schweitzer proved that Graph Isomorphism is polynomial-time solvable on graph classes of bounded clique-width. By combining known results with a number of new results, we reduce the number of open cases to seven. By exploiting the strong relationship between Graph Isomorphism and clique-width, we simultaneously reduce the number of open cases for boundedness of clique-width for \((H_1,H_2)\)-free graphs to five.

The 0-1-knapsack problem is a well-known NP-hard problem in combinatorial optimization. We consider the extensions to the knapsack problem with conflict graph (KCG) and the knapsack problem with forcing graph (KFG). Within this paper we provide pseudo-polynomial solutions for KCG and KFG with co-graphs as conflict and forcing graphs and extend these solutions to conflict and forcing graphs of bounded clique-width. Our solutions are based on dynamic programming using the tree-structure representing the conflict graph and the forcing graph. Further we conclude fully polynomial time approximation schemes (FPTAS) for KCG on conflict graphs of bounded clique-width and KFG on forcing graphs of bounded clique-width. This generalizes the known results for conflict and forcing graphs of bounded tree-width of Pferschy and Schauer.

Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, their proper subclass, where each interval has a unit length, has also been extensively studied. We study mixed unit interval graphs-a generalization of unit interval graphs where each interval has still a unit length, but intervals of more than one type (open, closed, semi-closed) are allowed. This small modification captures a much richer class of graphs. In particular, mixed unit interval graphs are not claw-free, compared to unit interval graphs. Heggernes, Meister, and Papadopoulos defined a representation of unit interval graphs called the bubble model which turned out to be useful in algorithm design. We extend this model to the class of mixed unit interval graphs. The original bubble model was used by Boyaci, Ekim, and Shalom for proving the polynomiality of the MaxCut problem on unit interval graphs. However, we found a significant mistake in the proof which seems to be hardly repairable. Moreover, we demonstrate advantages of such model by providing a subexponential-time algorithm solving the MaxCut problem on mixed unit interval graphs using our extended version of the bubble model. In addition, it gives us a polynomial-time...

In the last decades, considerable efforts have been spent to characterize what makes NP-hard problems tractable. A successful approach in this line of research is the theory of parameterized complexity introduced by Downey and Fellows in the nineties.In this framework, the complexity of a problem is not measured only in terms of the input size, but also in terms of a parameter on the input. One of the most well-studied parameters is tree-width, a graph parameter which measures how close a graph is to the topological structure of a tree.It appears that tree-width has numerous structural properties and algorithmic applications.However, only sparse graph classes can have bounded tree-width. But, many NP-hard problems are tractable on dense graph classes. Most of the time, this tractability can be explained by the ability of these graphs to be recursively decomposable along vertex bipartitions (A,B) where the adjacency between A and B is simple to describe. A lot of graph parameters -- called width measures -- have been defined to characterize this ability, the most remarkable ones are certainly clique-width, rank-width, and mim-width. In this thesis, we study the algorithmic properties of these width measures. We provide a framework that generalizes and simplifies the tools developed for tree-width and for problems with a constraint of acyclicity or connectivity such as Connected Vertex Cover, Connected Dominating Set, Feedback Vertex Set, etc. For all these problems, we obtain 2^{O(k)}⋅n^{O(1)}, 2^{O(k log(k))}⋅n^{O(1)}, 2^{O(k²)}⋅n^{O(1)} and n^{O(k)} time algorithms parameterized respectively by clique-width, Q-rank-width, rank-width and mim-width. We also prove that there exists an algorithm solving Hamiltonian Cycle in time n^{O(k)}, when a clique-width decomposition of width k is given. Finally, we prove that we can count in polynomial time the minimal transversals of β-acyclic hypergraphs and the minimal dominating sets of strongly chordal graphs. All these results offer promising perspectives towards a generalization of width measures and their algorithmic applications., Durant ces dernières décennies, d'importants efforts et beaucoup de café ont été dépensés en vue de caractériser les instances faciles des problèmes NP-difficiles. Dans ce domaine de recherche, une approche s'avère être redoutablement efficace : la théorie de la complexité paramétrée introduite par Downey et Fellows dans les années 90.Dans cette théorie, la complexité d'un problème n'est plus mesurée uniquement en fonction de la taille de l'instance, mais aussi en fonction d'un paramètre. Dans cette boite à outils, la largeur arborescente est sans nul doute un des paramètres de graphe les plus étudiés. Ce paramètre mesure à quel point un graphe est proche de la structure topologique d'un arbre.La largeur arborescente a de nombreuses propriétés algorithmiques et structurelles.Néanmoins, malgré l'immense intérêt suscité par la largeur arborescente, seules les classes de graphes peu denses peuvent avoir une largeur arborescente bornée. Mais, de nombreux problèmes NP-difficiles s'avèrent faciles dans des classes de graphes denses. La plupart du temps, cela peut s'expliquer par l'aptitude de ces graphes à se décomposer récursivement en bipartitions de sommets (A,B) où le voisinage entre A et B possède une structure simple. De nombreux paramètres -- appelés largeurs -- ont été introduits pour caractériser cette aptitude, les plus remarquables sont certainement la largeur de clique , la largeur de rang, la largeur booléenne et la largeur de couplage induit. Dans cette thèse, nous étudions les propriétés algorithmiques de ces largeurs. Nous proposons une méthode qui généralise et simplifie les outils développés pour la largeur arborescente et les problèmes admettant une contrainte d'acyclicité ou de connexité tel que Couverture Connexe, Dominant Connexe, Coupe Cycle, etc. Pour tous ces problèmes, nous obtenons des algorithmes s'exécutant en temps 2^{O(k)}⋅n^{O(1)}, 2^{O(k log(k))}⋅n^{O(1)}, 2^{O(k²)}⋅n^{O(1)} et n^{O(k)} avec k étant, respectivement, la largeur de clique, la largeur de Q-rang, la larguer de rang et la largueur de couplage induit. On prouve aussi qu'il existe un algorithme pour Cycle Hamiltonien s'exécutant en temps n^{O(k)} quand une décomposition de largeur de clique k est donné en entrée. Finalement, nous prouvons qu'on peut compter en temps polynomial le nombre de transversaux minimaux d'hypergraphes β-acyclique ainsi que le nombre de dominants minimaux de graphes fortement triangulés. Tous ces résultats offrent des pistes prometteuses en vue d'une généralisation des largeurs et de leurs applications algorithmiques.

We study the Maximum Happy Vertices and Maximum Happy Edges problems. The former problem is a variant of clusterization, where some vertices have already been assigned to clusters. The second problem gives a natural generalization of Multiway Uncut, which is the complement of the classical Multiway Cut problem. Due to their fundamental role in theory and practice, clusterization and cut problems has always attracted a lot of attention. We establish a new connection between these two classes of problems by providing a reduction between Maximum Happy Vertices and Node Multiway Cut. Moreover, we study structural and distance to triviality parameterizations of Maximum Happy Vertices and Maximum Happy Edges. Obtained results in these directions answer questions explicitly asked in four works: Agrawal ’17, Aravind et al. ’16, Choudhari and Reddy ’18, Misra and Reddy ’17.

An intuitionistic fuzzy graph structure (IFGS) is a generalization of an intuitionistic fuzzy graph. The concept of intuitionistic fuzzy graph structure is introduced and investigated in this paper. Some operations including union, join, Cartesian product, cross product, lexicographic product, strong product and composition on intuitionistic fuzzy graph structures are defined and elaborated with a number of examples. Some basic properties of these operations are also presented.

A multi-layer graph consists of multiple layers of weighted graphs, where the multiple layers represent the different aspects of relationships. Considering multiple aspects (i.e., layers) together is essential to achieve a comprehensive and consolidated view. In this article, we propose a novel framework of differential flattening , which facilitates the analysis of multi-layer graphs, and apply this framework to community detection. Differential flattening merges multiple graphs into a single graph such that the graph structure with the maximum clustering coefficient is obtained from the single graph. It has two distinct features compared with existing approaches. First, dealing with multiple layers is done independently of a specific community detection algorithm, whereas previous approaches rely on a specific algorithm. Thus, any algorithm for a single graph becomes applicable to multi-layer graphs. Second, the contribution of each layer to the single graph is determined automatically for the maximum clustering coefficient. Since differential flattening is formulated by an optimization problem, the optimal solution is easily obtained by well-known algorithms such as interior point methods. Extensive experiments were conducted using the Lancichinetti-Fortunato-Radicchi (LFR) benchmark networks as well as the DBLP, 20 Newsgroups, and MIT Reality Mining networks. The results show that our approach of differential flattening leads to discovery of higher-quality communities than baseline approaches and the state-of-the-art algorithms.