Search

In a (parameterized) graph edge modification problem, we are given a graph G, an integer k and a (usually well-structured) class G of graphs, and asked whether it is possible to transform G into a graph G ′ ∈ 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 a 2k-vertex kernel exists for Cluster Editing, this kernel does not reduce the size of the instance in most cases. Therefore, we explore the question of whether linear kernels are a theoretical limit in edge modification problems, in particular when the target graph class is 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 first show that Cluster Deletion admits a 2k-vertex kernel as Cluster Editing, improving the previous 4k-vertex kernel. We prove that (Pseudo-)Split Completion (and the equivalent (Pseudo-)Split Deletion) admits a linear kernel, improving the existing quadratic kernel. We also prove that Trivially Perfect Completion admits a quadratic kernel (improving the cubic kernel), and finally prove that its triangle-free version (Starforest Deletion) admits a linear kernel, which is optimal under the Exponential Time Hypothesis. [ABSTRACT FROM AUTHOR]

In Directed Feedback 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 C -Arc Deletion Set (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 C . In this work, we choose C to be the class of funnels. Funnel-ADS 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-ADS with O (k 6) many vertices and O (k 7) many arcs, computable in O (n m) time, where n is the number of vertices and m the number of arcs in the input digraph. [ABSTRACT FROM AUTHOR]

Clustering genes in similarity graphs is a popular approach for orthology prediction. Most algorithms group genes without considering their species, which results in clusters that contain several paralogous genes. Moreover, clustering is known to be problematic when in-paralogs arise from ancient duplications. Recently, we proposed a two-step process that avoids these problems. First, we infer clusters of only orthologs (i.e. with only genes from distinct species), and second, we infer the missing inter-cluster orthologs. In this paper, we focus on the first step, which leads to a problem we call Colorful Clustering. In general, this is as hard as classical clustering. However, in similarity graphs, the number of species is usually small, as well as the neighborhood size of genes in other species. We therefore study the problem of clustering in which the number of colors is bounded by k , and each gene has at most d neighbors in another species. We show that the well-known cluster editing formulation remains NP-hard even when d = 1 and k ∈ O (1). We then propose a fixed-parameter algorithm in k + d to find the single best cluster in the graph. We implemented this algorithm and included it in the aforementioned two-step approach. Experiments on simulated data show that this approach performs favorably to applying only an unconstrained clustering step. [ABSTRACT FROM AUTHOR]

Matrix visualizations are a useful tool to provide a general overview of a graph's structure. For multivariate graphs, a remaining challenge is to cope with the attributes that are associated with nodes and edges. Addressing this challenge, we propose responsive matrix cells as a focus+context approach for embedding additional interactive views into a matrix. Responsive matrix cells are local zoomable regions of interest that provide auxiliary data exploration and editing facilities for multivariate graphs. They behave responsively by adapting their visual contents to the cell location, the available display space, and the user task. Responsive matrix cells enable users to reveal details about the graph, compare node and edge attributes, and edit data values directly in a matrix without resorting to external views or tools. We report the general design considerations for responsive matrix cells covering the visual and interactive means necessary to support a seamless data exploration and editing. Responsive matrix cells have been implemented in a web-based prototype based on which we demonstrate the utility of our approach. We describe a walk-through for the use case of analyzing a graph of soccer players and report on insights from a preliminary user feedback session. [ABSTRACT FROM AUTHOR]

A subgraph complement of the graph G is a graph obtained from G by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class G , is there a subgraph complement of G which is in G ? We show that this problem can be solved in polynomial time for various choices of the graphs class G , such as bipartite, d-degenerate, or cographs. We complement these results by proving that the problem is NP -complete when G is the class of regular graphs. [ABSTRACT FROM AUTHOR]

We consider the Edge Editing to a Connected Graph of Given Degrees problem that asks, given a graph G , non-negative integers d , k and a function δ : V ( G ) → { 1 , … , d } , whether it is possible to obtain a connected graph G ′ from G such that the degree of v is δ ( v ) for every vertex v by at most k edge editing operations. As the problem is NP-complete even if δ ( v ) = 2 , we are interested in the parameterized complexity and show that Edge Editing to a Connected Graph of Given Degrees admits a polynomial kernel when parameterized by d + k . For the special case δ ( v ) = d , i.e., when the aim is to obtain a connected d -regular graph, the problem is shown to be fixed parameter tractable when parameterized by k only. [ABSTRACT FROM AUTHOR]

Graph editing problems offer an interesting perspective on sub- and supergraph identification problems for a large variety of target properties. They have also attracted significant attention in recent years, particularly in the area of parameterized complexity as the problems have rich parameter ecologies. In this paper we examine generalisations of the notion of editing a graph to obtain a regular subgraph. In particular we extend the notion of regularity to include two variants of edge-regularity along with the unifying constraint of strong regularity. We present a number of results, with the central observation that these problems retain the general complexity profile of their regularity-based inspiration: when the number of edits k and the maximum degree r are taken together as a combined parameter, the problems are tractable (i.e. in FPT ), but are otherwise intractable. We also examine variants of the basic editing to obtain a regular subgraph problem from the perspective of parameterizing by the treewidth of the input graph. In this case the treewidth of the input graph essentially becomes a limiting parameter on the natural k + r parameterization. [ABSTRACT FROM AUTHOR]

We consider the following graph modification problem. Let the input consist of a graph G = ( V , E ) , a weight function w : V ∪ E → N , a cost function c : V ∪ E → N 0 and a degree function δ : V → N 0 , together with three integers k v , k e and C . The question is whether we can delete a set of vertices of total weight at most k v and a set of edges of total weight at most k e so that the total cost of the deleted elements is at most C and every non-deleted vertex v has degree δ ( v ) in the resulting graph G ′ . We also consider the variant in which G ′ must be connected. Both problems are known to be NP -complete and W [ 1 ] -hard when parameterized by k v + k e . We prove that, when restricted to planar graphs, they stay NP -complete but have polynomial kernels when parameterized by k v + k e . [ABSTRACT FROM AUTHOR]

We investigate the parameterized complexity of the graph editing problem called Editing to a Graph with a Given Degree Sequence where the aim is to obtain a graph with a given degree sequence σ by at most k vertex deletions, edge deletions and edge additions. We show that the problem is W [ 1 ] -hard when parameterized by k for any combination of the allowed editing operations. From the positive side, we show that the problem can be solved in time 2 O ( k ( Δ ⁎ + k ) 2 ) n 2 log ⁡ n for n -vertex graphs, where Δ ⁎ = max ⁡ σ , i.e., the problem is FPT when parameterized by k + Δ ⁎ . We also show that Editing to a Graph with a Given Degree Sequence has a polynomial kernel when parameterized by k + Δ ⁎ if only edge additions are allowed, and there is no polynomial kernel unless NP ⊆ co - NP / poly for all other combinations of the allowed editing operations. [ABSTRACT FROM AUTHOR]

We relate the graph editing distance to a generalized weighted version of the most common subgraph distance . To do so, we introduce the new concepts of isotonic shifts and vector weighted graphs . As a consequence we can give a weak but sufficient condition on cost models to result in an edit metric , ensuring the richness of the class of these functions. Moreover, for arbitrary instances we are able to determine a within cubic time computable upper bound on the edit distance, which equals the minimized distance for infinitely many instances. [ABSTRACT FROM AUTHOR]

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 . [ABSTRACT FROM AUTHOR]

The Eulerian Editing problem asks, given a graph G and an integer k , whether G can be modified into an Eulerian graph using at most k edge additions and edge deletions. We show that this problem is polynomial-time solvable for both undirected and directed graphs. We generalize these results for problems with degree parity constraints and degree balance constraints, respectively. We also consider the variants where vertex deletions are permitted. Combined with known results, this leads to full complexity classifications for both undirected and directed graphs and for every subset of the three graph operations. [ABSTRACT FROM AUTHOR]

We consider the Editing to a Graph of Given Degrees problem that asks for a graph G , non-negative integers d , k and a function δ : V ( G ) → { 1 , … , d } , whether it is possible to obtain a graph G ′ from G such that the degree of v is δ ( v ) for any vertex v by at most k vertex or edge deletions or edge additions. We construct an FPT-algorithm for Editing to a Graph of Given Degrees parameterized by d + k . We complement this result by showing that the problem has no polynomial kernel unless NP ⊆ coNP / poly . [ABSTRACT FROM AUTHOR]

In Stata, graphs are usually generated by one call to the graph command. Sometimes, however, it would be convenient to be able to add objects to a graph after the graph has been created. In this article, I provide a command called addplot that offers such functionality for twoway graphs, capitalizing on an undocumented feature of Stata's graphics system. [ABSTRACT FROM AUTHOR]

Abstract: We study a novel generalization of the Vertex Cover problem which is motivated by, e.g., error correction (data cleaning) prior to inference of chemical mixtures by their observable reaction products. We focus on the important case of deciding on one of two candidate substances. This problem has nice graph-theoretic formulations situated between Vertex Cover and 3-Hitting Set. In order to characterize its parameterized complexity we devise parameter-preserving reductions, and we show that some minimum solution can be computed faster than by solving 3-Hitting Set in general. More explicitly, we introduce the Union Editing problem: In a hypergraph with red and blue vertices, edit the colors so that the red set becomes exactly the union of some hyperedges. The case of degree 2 is equivalent to Star Editing: in a graph with red and blue edges, edit the colors so that the red set becomes exactly the union of some stars, i.e., vertices with all their incident edges. Our time bound is where denotes the total number of recolored edges. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: We examine the parameterized complexity of the problem of editing a graph to obtain an -degenerate graph. We show that for the editing operations vertex deletion and edge deletion, both separately and combined, the problem is -complete, and remains -complete even if the input graph is already -degenerate, or has maximum degree for all . We also demonstrate fixed-parameter tractability for several Clique based problems when the input graph has bounded degeneracy. [Copyright &y& Elsevier]

Let A = {A1, …,Ar} be a partition of a set {1, …,m} × {1, …, n} into r nonempty subsets, and let A = (aij) be an m × n matrix. We say that A has a pattern A provided that aij = ai'j' if and only if (i, j), (i', j') ε At for some t ε {1, …, r}. In this note we study the following function f defined on the set of all m × n matrices M with s distinct entries: f(M;A) is the smallest number of positions where the entries of M need to be changed such that the resulting matrix does not have any submatrix with pattern A. We give an asymptotically tight value for f(m, n; s,A) = max{f(M;A) : M is an m × n matrix with at most s distinct entries}. [ABSTRACT FROM AUTHOR]