Search

We consider the problem of transforming a given graph into a quasi-threshold graph using a minimum number of edge additions and deletions. Building on the previously proposed heuristic Quasi-Threshold Mover (QTM), we present improvements both in terms of running time and quality. We propose a novel, linear-time algorithm that solves the inclusion-minimal variant of this problem, i.e., a set of edge edits such that no subset of them also transforms the given graph into a quasi-threshold graph. In an extensive experimental evaluation, we apply these algorithms to a large set of graphs from different applications and find that they lead QTM to find solutions with fewer edits. Although the inclusion-minimal algorithm needs significantly more edits on its own, it outperforms the initialization heuristic previously proposed for QTM., Lecture Notes in Computer Science, 13201, ISSN:0302-9743, ISSN:1611-3349, Algorithms for Big Data, ISBN:978-3-031-21533-9, ISBN:978-3-031-21534-6

In a (parameterized) graph edge modification problem, we are given a graph $G$, an integer $k$ and a (usually well-structured) class of graphs $\mathcal{G}$, and ask whether it is possible to transform $G$ into a graph $G' \in \mathcal{G}$ by adding and/or removing at most $k$ edges. Parameterized graph edge modification problems received considerable attention in the last decades. In this paper, we focus on finding small kernels for edge modification problems. One of the most studied problems is the Cluster Editing problem, in which the goal is to partition the vertex set into a disjoint union of cliques. Even if this problem admits a $2k$ kernel [Cao, 2012], this kernel does not reduce the size of most instances. Therefore, we explore the question of whether linear kernels are a theoretical limit in edge modification problems, in particular when the target graphs are very structured (such as a partition into cliques for instance). We prove, as far as we know, the first sublinear kernel for an edge modification problem. Namely, we show that Clique + Independent Set Deletion, which is a restriction of Cluster Deletion, admits a kernel of size $O(k/\log k)$. We also obtain small kernels for several other edge modification problems. We prove that Split Addition (and the equivalent Split Deletion) admits a linear kernel, improving the existing quadratic kernel of Ghosh et al. [Ghosh et al., 2015]. We complement this result by proving that Trivially Perfect Addition admits a quadratic kernel (improving the cubic kernel of Guo [Guo, 2007]), and finally prove that its triangle-free version (Starforest Deletion) admits a linear kernel, which is optimal under ETH., 19 pages, to be published in IPEC'21; Minor modifications following reviews

This document describes our heuristic Cluster Editing solver, ��Solver, which got the third place in the 2021 PACE Challenge. We present the local search and kernelization techniques for Cluster Editing that are implemented in the solver., LIPIcs, Vol. 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), pages 33:1-33:3

For a fixed graph H, the H-Minor Edit problem takes as input a graph G and an integer k and asks whether G can be modified into H by a total of at most k edge contractions, edge deletions and vertex deletions. Replacing edge contractions by vertex dissolutions yields the H-Topological Minor Edit problem. For each problem we show polynomial-time solvable and NP-complete cases depending on the choice of H. Moreover, when G is AT-free, chordal or planar, we show that H-Minor Edit is polynomial-time solvable for all graphs H.

This work deals with the p-Cluster Editing Problem (p-CEP), which consists in performing a minimum number of editions (additions or removals of edges) in a graph G in order to transform it in a disjoint union of p cliques (clusters), where G and p are input data. p-CEP is a NP-Hard problem with applications in areas such as computational biology and machine learning. To solve this problem, we propose two new mathematical formulations and improvements in a formulation from the literature, as well as new valid inequalities. The three formulations were studied both theoretically, by comparing their linear relaxations, and practically, by implementing three exact algorithms: two based on Branch-and-Cut (BC) and one based on Branch-and-Price (BP). The proposed algorithms were tested in instances with up to 211 vertices. The results show the performance of the algorithms according to the graph density and the ratio between p and the number of vertices. Overall, the BC algorithms were superior to the BP algorithm. However, the latter obtained the best dual bounds in some instances. Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES Este trabalho trata do Problema de Edi¸c˜ao de p-Clusters (p-PEC), o qual consiste em realizar um n´umero m´ınimo de edi¸c˜oes (adi¸c˜oes ou remo¸c˜oes de arestas) em um grafo G de modo a transform´a-lo em uma uni˜ao disjunta de p cliques (ou clusters), sendo G e p dados de entrada. O p-PEC ´e um problema NP-Dif´ıcil que possui aplica¸c˜oes em ´areas como biologia computacional e aprendizagem de m´aquina. Para resolvˆe-lo, foram propostas duas novas formula¸c˜oes matem´aticas e melhorias em uma formula¸c˜ao proveniente da literatura, bem como novas desigualdades v´alidas. As trˆes formula¸c˜oes consideradas foram estudadas tanto teoricamente, atrav´es da compara¸c˜ao entre as relaxa¸c˜oes lineares, quanto empiricamente, atrav´es do desenvolvimento de trˆes algoritmos exatos: dois baseados em Branch-and-Cut (BC) e um baseado em Branch-and-Price (BP). Os algoritmos foram testados em instˆancias com at´e 211 v´ertices. Os resultados mostram o impacto da raz˜ao entre p e o n´umero de v´ertices, da densidade do grafo e das desigualdades nos desempenhos dos algoritmos. No geral, os algoritmos BC foram superiores ao algoritmo BP. Por´em, em algumas instˆancias, os melhores limites duais foram obtidos pelo algoritmo BP.

One of the current practical, useful but sensitive topic in social networks is polling problemwhere the privacy of exchanged information and user reputation are very critical. Indeed, userswant to preserve the confidentiality of their votes and to hide, if any, their misbehaviors. Recently,Guerraoui et al. proposed polling protocols based on simple secret sharing scheme and withoutrequiring any central authority or cryptography system. However these protocols can be deployedsafely and efficiently provided that the social graph structure should be transformed into a ringstructure-based overlay and the number of participating users is perfect square. In this thesis,we address the problem of deploying decentralized polling protocols for general social graphsand how to transform these graphs in order to increase the privacy and/or accuracy properties.First, we propose three simple decentralized polling protocols that rely on the current state ofsocial graphs. The two first protocols use synchronous and asynchronous models and verificationprocedures to detect the misbehaving users. The third protocol is an asynchronous one thatdoes not require any verification procedures and contains a method for efficiently broadcastingmessage under a family of social graphs satisfying what we call the m-broadcasting property.Second, we formalize the “adding friends” problem such that we can reuse the social graphs aftersome minimum structural modifications consisting in adding new friendship relations. We alsodevise algorithms for solving this problem in centralized and decentralized networks. We validateour solutions with some performance evaluations which show that our protocols are accurate,and inside the theoretical bounds.; Un des thèmes pratiques, mais hautement sensibles, est le problème de sondage dans les réseauxso ciaux où le caractère secret des informations sélectionnées et la réputation de l’utilisateur sonttrès critiques. En effet, les utilisateurs désirent préserver la confidentialité de leurs votes et dissimuler, le cas échéant, leurs mauvais comp ortements. Récemment, Guerraoui et al. ont proposédes protocoles de sondage basés sur la partage de secret et ne nécessitant aucune infrastructure cryptographique. Néanmoins, ces protocoles ne sont applicables que si le graphe social aune structure d’anneau et le nombre d’utilisateurs est un carré parfait. Dans cette thèse, noustraitons, d’une part, du problème du déploiement décentralisé des protocoles de sondage qui sontbasés sur des graphes sociaux ayant des structures générales, et d’autre part, du problème detransformation des graphes sociaux pour augmenter les propriétés de vie privée et de précision,nécessaires au déroulement sûr et rentable du sondage décentralisé. Premièrement, nous proposons trois protocoles décentralisés qui s’appuient sur l’état originel (sans transformation) desgraphes sociaux. Les deux premiers protocoles utilisent respectivement des modèles de communication synchrone et asynchrone, et manipulent des procédures de vérification pour détecter lesutilisateurs malhonnêtes. Quant au troisième protocole, il est asynchrone et ne nécessite pasde procédures de vérification. Pour que ce protocole permette une diffusion efficace de messages, nous avons défini une propriété sur les graphes sociaux, appelée “ m-broadcasting”. Dansla deuxième partie de la thèse, nous formalisons le problème de “l’ajout des amis” qui consiste àtrouver une transformation optimale des graphes sociaux pour les adapter au partage de secret.Pour résoudre ce problème, nous présentons deux algorithmes selon deux approches différentes:centralisée et décentralisée. Une évaluation expérimentale montre que nos protocoles sont préciset restreints aux bornes théoriques.

One of the current practical, useful but sensitive topic in social networks is polling problemwhere the privacy of exchanged information and user reputation are very critical. Indeed, userswant to preserve the confidentiality of their votes and to hide, if any, their misbehaviors. Recently,Guerraoui et al. proposed polling protocols based on simple secret sharing scheme and withoutrequiring any central authority or cryptography system. However these protocols can be deployedsafely and efficiently provided that the social graph structure should be transformed into a ringstructure-based overlay and the number of participating users is perfect square. In this thesis,we address the problem of deploying decentralized polling protocols for general social graphsand how to transform these graphs in order to increase the privacy and/or accuracy properties.First, we propose three simple decentralized polling protocols that rely on the current state ofsocial graphs. The two first protocols use synchronous and asynchronous models and verificationprocedures to detect the misbehaving users. The third protocol is an asynchronous one thatdoes not require any verification procedures and contains a method for efficiently broadcastingmessage under a family of social graphs satisfying what we call the m-broadcasting property.Second, we formalize the “adding friends” problem such that we can reuse the social graphs aftersome minimum structural modifications consisting in adding new friendship relations. We alsodevise algorithms for solving this problem in centralized and decentralized networks. We validateour solutions with some performance evaluations which show that our protocols are accurate,and inside the theoretical bounds.; Un des thèmes pratiques, mais hautement sensibles, est le problème de sondage dans les réseauxso ciaux où le caractère secret des informations sélectionnées et la réputation de l’utilisateur sonttrès critiques. En effet, les utilisateurs désirent préserver la confidentialité de leurs votes et dissimuler, le cas échéant, leurs mauvais comp ortements. Récemment, Guerraoui et al. ont proposédes protocoles de sondage basés sur la partage de secret et ne nécessitant aucune infrastructure cryptographique. Néanmoins, ces protocoles ne sont applicables que si le graphe social aune structure d’anneau et le nombre d’utilisateurs est un carré parfait. Dans cette thèse, noustraitons, d’une part, du problème du déploiement décentralisé des protocoles de sondage qui sontbasés sur des graphes sociaux ayant des structures générales, et d’autre part, du problème detransformation des graphes sociaux pour augmenter les propriétés de vie privée et de précision,nécessaires au déroulement sûr et rentable du sondage décentralisé. Premièrement, nous proposons trois protocoles décentralisés qui s’appuient sur l’état originel (sans transformation) desgraphes sociaux. Les deux premiers protocoles utilisent respectivement des modèles de communication synchrone et asynchrone, et manipulent des procédures de vérification pour détecter lesutilisateurs malhonnêtes. Quant au troisième protocole, il est asynchrone et ne nécessite pasde procédures de vérification. Pour que ce protocole permette une diffusion efficace de messages, nous avons défini une propriété sur les graphes sociaux, appelée “ m-broadcasting”. Dansla deuxième partie de la thèse, nous formalisons le problème de “l’ajout des amis” qui consiste àtrouver une transformation optimale des graphes sociaux pour les adapter au partage de secret.Pour résoudre ce problème, nous présentons deux algorithmes selon deux approches différentes:centralisée et décentralisée. Une évaluation expérimentale montre que nos protocoles sont préciset restreints aux bornes théoriques.

We study two clustering problems, Starforest Editing, the problem of adding and deleting edges to obtain a disjoint union of stars, and the generalization Bicluster Editing. We show that, in addition to being NP-hard, none of the problems can be solved in subexponential time unless the exponential time hypothesis fails. Misra, Panolan, and Saurabh (MFCS 2013) argue that introducing a bound on the number of connected components in the solution should not make the problem easier: In particular, they argue that the subexponential time algorithm for editing to a fixed number of clusters (p-Cluster Editing) by Fomin et al. (J. Comput. Syst. Sci., 80(7) 2014) is an exception rather than the rule. Here, p is a secondary parameter, bounding the number of components in the solution. However, upon bounding the number of stars or bicliques in the solution, we obtain algorithms which run in time $2^{5 \sqrt{pk}} + O(n+m)$ for p-Starforest Editing and $2^{O(p \sqrt{k} \log(pk))} + O(n+m)$ for p-Bicluster Editing. We obtain a similar result for the more general case of t-Partite p-Cluster Editing. This is subexponential in k for fixed number of clusters, since p is then considered a constant. Our results even out the number of multivariate subexponential time algorithms and give reasons to believe that this area warrants further study., Comment: Accepted for presentation at IPEC 2015

We investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. Let $ea$, $ed$ and $vd$ denote the operations edge addition, edge deletion and vertex deletion respectively. For any $S\subseteq \{ea,ed,vd\}$, we define Connected Degree Parity Editing$(S)$ (CDPE($S$)) to be the problem that takes as input a graph $G$, an integer $k$ and a function $\delta\colon V(G)\rightarrow\{0,1\}$, and asks whether $G$ can be modified into a connected graph $H$ with $d_{H}(v)\equiv\delta(v)~(\bmod~2)$ for each $v\in V(H)$, using at most $k$ operations from $S$. We prove that 1. if $S=\{ea\}$ or $S=\{ea,ed\}$, then CDPE($S$) can be solved in polynomial time; 2. if $\{vd\} \subseteq S\subseteq \{ea,ed,vd\}$, then CDPE($S$) is NP-complete and W[1]-hard when parameterized by $k$, even if $\delta\equiv 0$. Together with known results by Cai and Yang and by Cygan, Marx, Pilipczuk, Pilipczuk and Schlotter, our results completely classify the classical and parameterized complexity of the CDPE($S$) problem for all $S\subseteq \{ea,ed,vd\}$. We obtain the same classification for a natural variant of the CDPE($S$) problem on directed graphs, where the target is a weakly connected digraph in which the difference between the in- and out-degree of every vertex equals a prescribed value. As an important implication of our results, we obtain polynomial-time algorithms for the Eulerian Editing problem and its directed variant., Comment: 33 pages. An extended abstract of this paper will appear in the proceedings of FSTTCS 2014

We study a wide class of graph editing problems that ask whether a given graph can be modified to satisfy certain degree constraints, using a limited number of vertex deletions, edge deletions, or edge additions. The problems generalize several well-studied problems such as the General Factor Problem and the Regular Subgraph Problem. We classify the parameterized complexity of the considered problems taking upper bounds on the number of editing steps and the maximum degree of the resulting graph as parameters. © 2011 Elsevier Inc. All rights reserved.

üOZETË şË ş Ë ü ËCHISIO: BILESIK CIZGE DUZENLEMESI VEşË Ë ËşË ü ËşYERLESTIRMESI ICIN GORSEL BIR CERCEVEşCihan Kücukkeşeciuşü cBilgisayar Mühendisliği, Yüksek Lisansu g uTez Yüneticisi: Doşent Dr. Uğur Doğrusüzo c g goHaziran, 2007Cizgeler, ağ oluşturmaktan, biyolojiye, bilgisayar bilimlerine, birşok alanda sıkşaş g s c ckullanılan veri modelleridir. Gürselleştirme, etkileşimli düzenleme kabiliyetio s s uve şizgelerin yerleştirilmesi, temeldeki ilişkisel bilgilerin şozümlenmesinde kritikc s s cü ukonulardır.Birşok ticari ve ticari olmayan şizge gürselleştirme araşları mevcuttur. Ancakc c o s cbileşik veya sıradüzensel olarak düzenlenmiş şizge güsterimini sağlayan araş sayısıs u u sc o g cşok sınırlı sayıdadır.cBiz adı Chisio olan yeni bir aşık-kaynak düzenleme ve yerleştirme ya-c u span şerşeve tanıtıyoruz. Chisio bedava, kullanımı kolay ve etkili, otomatikccyerleşim algoritmalarını destekleyen bir akademik şizge gürselleştirme aracı olaraks c o sgeliştirildi. Java'da yazıldı ve Eclipse'in Graï¬ksel Düzenleme Cerşevesi'ni (GEF)s u şctemel olarak aldı.Chisio yakınlaştırma, kaydırma, şizge nesneleri ekleme ya da cıkarma, harekets c şettirme, boyutunu değiştirme gibi standart şizge düzenleyici ozellikleri ile tamam-gs c u ülanmış üzelleşmemiş bileşik cizge düzenleyicisi olarak kullanılabilir. Var olan şizgeso s s sş u cnesnelerinin ozelliklerini ve yerleşim seşeneklerini değiştirmek işin nesne ozellikleriü s c gs c üve yerleşim seşenekleri pencereleri sunulmaktadır. Ayrıca, kullanılmakta olans cşizgeyi yazdırma ya da resim olarak ve kalıcı bellekte saklamak da mümkündür.c uuuSaklanan şizgeler ya da diğer araşlar tarafından yaratılmış GraphML bişimindekic g c s cdosyalar Chisio'ya yüklenebilir. Bunlardan başka, vurgulama mekanizması ileu skullanıcıların ilgilendiği altşizgelerin vurgulanması da mümkündür.g c uuuCerşeve, son kullanıcıların üzel ihtiyaşları işin kolayca üzelleştirilebilmeyeşc o c c o solanak sağlayacak bir mimariye de sahiptir. Ayrıca Chisio yay gümmeli'deng osıradüzensel yerleşime, bileşik yay gümmeliye, dairesel yerleşime ceşitli yerleşimu s s o s şs svvistilleri sunmaktadır. Bundan başka, yerleşim algoritması geliştirenler işin Chi-s s s csio'yu ideal bir sınama ortamı yapacak şekilde yeni algoritmalar doğruca ek-s glenebilir.Anahtar süzcükler : bilgi gürselleştirme, cizge yerleşimi, şizge düzenleme, yazılımou o s ş s c usistemi, şizge düzenleyici, bileşik şizgeler.c u sc ABSTRACTCHISIO: A VISUAL FRAMEWORK FORCOMPOUND GRAPH EDITING AND LAYOUTCihan Kücukkeşeciuşü cM.S. in Computer EngineeringSupervisor: Assoc. Prof. Dr. Uğur Doğrusüzg goJune, 2007Graphs are data models, widely used in many areas from networking to biology tocomputer science. Visualization, interactive editing ability and layout of graphsare critical issues when analyzing the underlying relational information.There are many commercial and non-commercial graph visualization tools.However, overall support for compound or hierarchically organized graph repre-sentations is very limited.We introduce a new open-source editing and layout framework named Chisiofor compound graphs. Chisio is developed as a free, easy-to-use and powerful aca-demic graph visualization tool, supporting various automatic layout algorithms.It is written in Java and based on Eclipse?s Graphical Editing Framework (GEF).Chisio can be used as a ï¬nished generic compound graph editor with standardgraph editing facilities such as zoom, scroll, add or remove graph objects, move,and resize. Object property and layout options dialogs are provided to modifyexisting graph object properties and layout options, respectively. In addition,printing or saving the current drawing as a static image and persistent storagefacilities are supported. Saved graphs or GraphML formatted ï¬les created byother tools can be loaded into Chisio. Furthermore, a highlight mechanism isprovided to emphasize subgraphs of users interest.The framework has an architecture suitable for easy customization of the toolfor end-users? speciï¬c needs as well. Also Chisio oï¬ers several layout styles fromthe basic spring embedder to hierarchical layout to compound spring embedder tocircular layout. Furthermore, new algorithms are straightforward to add, makingChisio an ideal test environment for layout algorithm developers.iiiivKeywords: information visualization, graph layout, graph editing, software sys-tem, graph editor, compound graphs. 114

Search and retrieval of three-dimensional media will rapidly become a key issue in the upcoming panorama of multimedia content: 3D models are indeed expected to represent a huge amount of traffic and data stored in the Internet. This article proposes a novel technique to define and construct 3D shape prototypes, that improve the automatic classification of 3D content. The shape-prototype summarizes the most relevant features of the members of a class. The query object is then classified into the class represented by the prototype more similar to the given query. In the proposed methodology, each member of a class is represented by a structural descriptor encoded as an attributed graph. The prototype is obtained by applying graph-transformation techniques among the shape descriptors associated to the members of the class. The effectiveness of the classification process is finally evaluated on an heterogeneous benchmark of 3D objects. © 2007 IEEE.