Search

In Directed Feeback Arc Set (DFAS) we search for a set of at most $k$ arcs which intersect every cycle in the input digraph. It is a well-known open problem in parameterized complexity to decide if DFAS admits a kernel of polynomial size. We consider $\mathcal{C}$-Arc Deletion Set ($\mathcal{C}$-ADS), a variant of DFAS where we want to remove at most $k$ arcs from the input digraph in order to turn it into a digraph of a class $\mathcal{C}$. In this work, we choose $\mathcal{C}$ to be the class of funnels. Funnel-Arc Deletion Set is NP-hard even if the input is a DAG, but is fixed-parameter tractable with respect to $k$. So far no polynomial kernels for this problem were known. Our main result is a kernel for Funnel-Arc Deletion Set with $\mathcal{O}(k^6)$ many vertices and $\mathcal{O}(k^7)$ many arcs, computable in $\mathcal{O}(nm)$ time, where $n$ is the number of vertices and $m$ the number of arcs in the input digraph., Accepted at IPEC 2020

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

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.

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