Search

Isolation is a concept originally conceived in the context of clique enumeration in static networks, mostly used to model communities that do not have much contact to the outside world. Herein, a clique is considered isolated if it has few edges connecting it to the rest of the graph. Motivated by recent work on enumerating cliques in temporal networks, we transform the isolation concept to the temporal setting. We discover that the addition of the time dimension leads to six distinct natural isolation concepts. Our main contribution is the development of parameterized enumeration algorithms for five of these six isolation types for clique enumeration, employing the parameter "degree of isolation." In a nutshell, this means that the more isolated these cliques are, the faster we can find them. On the empirical side, we implemented and tested these algorithms on (temporal) social network data, obtaining encouraging results. [ABSTRACT FROM AUTHOR]

Dealing with the NP-complete DOMINATING SET problem on graphs, we demonstrate the power of data reduction by preprocessing from a theoretical as well as a practical side. In particular, we prove that DOMINATING SET restricted to planar graphs has a so-called problem kernel of linear size, achieved by two simple and easy-to-implement reduction rules. Moreover, having implemented our reduction rules, first experiments indicate the impressive practical potential of these rules. Thus, this work seems to open up a new and prospective way how to cope with one of the most important problems in graph theory and combinatorial optimization. [ABSTRACT FROM AUTHOR]

Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G , a temporal graph is represented by assigning a set of integer time-labels to every edge e of G , indicating the discrete time steps at which e is active. We introduce and study the complexity of a natural temporal extension of the classical graph problem Maximum Matching , taking into account the dynamic nature of temporal graphs. In our problem, Maximum Temporal Matching , we are looking for the largest possible number of time-labeled edges (simply time-edges) (e , t) such that no vertex is matched more than once within any time window of Δ consecutive time slots, where Δ ∈ N is given. We prove strong computational hardness results for Maximum Temporal Matching , even for elementary cases, as well as fixed-parameter algorithms with respect to natural parameters and polynomial-time approximation algorithms. [ABSTRACT FROM AUTHOR]

We study the problem of non-preemptively scheduling n jobs, each job j with a release time $$t_j$$ , a deadline $$d_j$$ , and a processing time $$p_j$$ , on m parallel identical machines. Cieliebak et al. (2004) considered the two constraints $$|d_j-t_j|\le \lambda {}p_j$$ and $$|d_j-t_j|\le p_j +\sigma $$ and showed the problem to be NP-hard for any $$\lambda >1$$ and for any $$\sigma \ge 2$$ . We complement their results by parameterized complexity studies: we show that, for any $$\lambda >1$$ , the problem remains weakly NP-hard even for $$m=2$$ and strongly W[1]-hard parameterized by m. We present a pseudo-polynomial-time algorithm for constant m and $$\lambda $$ and a fixed-parameter tractability result for the parameter m combined with $$\sigma $$ . [ABSTRACT FROM AUTHOR]

Co-clustering, that is partitioning a numerical matrix into "homogeneous" submatrices, has many applications ranging from bioinformatics to election analysis. Many interesting variants of co-clustering are NP-hard. We focus on the basic variant of co-clustering where the homogeneity of a submatrix is defined in terms of minimizing the maximum distance between two entries. In this context, we spot several NP-hard, as well as a number of relevant polynomial-time solvable special cases, thus charting the border of tractability for this challenging data clustering problem. For instance, we provide polynomial-time solvability when having to partition the rows and columns into two subsets each (meaning that one obtains four submatrices). When partitioning rows and columns into three subsets each, however, we encounter NP-hardness, even for input matrices containing only values from f0, 1, 2g. [ABSTRACT FROM AUTHOR]

We study the NP-hard Temporal (s , z) -Separation problem on temporal graphs, which are graphs with fixed vertex sets but edge sets that change over discrete time steps. We tackle Temporal (s , z) -Separation by restricting the layers (i.e., graphs characterized by edges that are present at a certain point in time) to specific graph classes. We restrict the layers of the temporal graphs to be either all split graphs or all permutation graphs (both being perfect graph classes) and provide both intractability and tractability results. In particular, we show that in general Temporal (s , z) -Separation remains NP-hard both on temporal split and temporal permutation graphs, but we also spot promising islands of fixed-parameter tractability particularly based on parameterizations that measure the amount of "change over time". [ABSTRACT FROM AUTHOR]

The NP-hard RAINBOW SUBGRAPH problem, motivated from bioinformatics, is to find in an edge-colored graph a subgraph that contains each edge color exactly once and has at most k vertices. We examine the parameterized complexity of RAINBOW SUBGRAPH for paths, trees, and general graphs. We show that RAINBOW SUBGRAPH is W[1]-hard with respect to the parameter k and also with respect to the dual parameter ℓ := n - k where n is the number of vertices. Hence, we examine parameter combinations and show, for example, a polynomial-size problem kernel for the combined parameter ℓ and "maximum number of colors incident with any vertex". Additionally, we show APX-hardness even if the input graph is a properly edge-colored path in which every color occurs at most twice. [ABSTRACT FROM AUTHOR]

The NP-hard Subset Interconnection Design problem, also known as Minimum Topic-Connected Overlay, is motivated by numerous applications including the design of scalable overlay networks and vacuum systems. It has as input a finite set V and a collection of subsets V1, V2, . . ., Vm ⊆ V, and asks for a minimum-cardinality edge set E such that for the graph G = (V,E) all induced subgraphs G[V1],G[V2], . . .,G[Vm] are connected. We study Subset Interconnection Design in the context of polynomial-time data reduction rules that preserve the possibility of constructing optimal solutions. Our contribution is threefold: First, we show the incorrectness of earlier polynomial-time data reduction rules. Second, we show linear-time solvability in case of a constant number m of subsets, implying fixed-parameter tractability for the parameter m. Third, we provide a fixed-parameter tractability result for small subset sizes and tree-like output graphs. To achieve our results, we elaborate on polynomial-time data reduction rules which also may be of practical use in solving Subset Interconnection Design. [ABSTRACT FROM AUTHOR]

A popular clustering algorithm for biological networks which was proposed by Hartuv and Shamir refid="ref5"/ identifies nonoverlapping highly connected components. We extend the approach taken by this algorithm by introducing the combinatorial optimization problem Highly Connected Deletion, which asks for removing as few edges as possible from a graph such that the resulting graph consists of highly connected components. We show that Highly Connected Deletion is NP-hard and provide a fixed-parameter algorithm and a kernelization. We propose exact and heuristic solution strategies, based on polynomial-time data reduction rules and integer linear programming with column generation. The data reduction typically identifies 75  percent of the edges that are deleted for an optimal solution; the column generation method can then optimally solve protein interaction networks with up to 6,000 vertices and 13,500 edges within five hours. Additionally, we present a new heuristic that finds more clusters than the method by Hartuv and Shamir. [ABSTRACT FROM PUBLISHER]

The aim of directed Eulerian extension problems is to make a given directed, possibly arc-weighted, (multi-)graph Eulerian by adding a minimum-cost set of arcs. These problems have natural applications in scheduling and arc routing and are closely related to the Chinese Postman and Rural Postman problems. Our main result is to show that the NP-hard Weighted Multigraph Eulerian Extension problem is fixed-parameter tractable with respect to the number k of extension arcs. For a directed n-vertex multigraph, the corresponding running time amounts to O(4k ·n³). This also implies a fixed-parameter tractability result for the "equivalent" Rural Postman problem parameterized above guarantee. In addition, we present several polynomial-time algorithms for natural Eulerian extension problems, including undirected variants which can be defined analogously to the directed ones. [ABSTRACT FROM AUTHOR]

We introduce the NP-hard graph-based data clustering problem s- Plex Cluster Vertex Deletion, where the task is to delete at most k vertices from a graph so that the connected components of the resulting graph are s-plexes. In an s-plex, every vertex has an edge to all but at most s−1 other vertices; cliques are 1-plexes. We propose a new method based on 'approximation and tidying' for kernelizing vertex deletion problems whose goal graphs can be characterized by forbidden induced subgraphs. The method exploits polynomial-time approximation results and thus provides a useful link between approximation and kernelization. Employing 'approximation and tidying', we develop data reduction rules that, in O( ksn) time, transform an s- Plex Cluster Vertex Deletion instance with n vertices into an equivalent instance with O( k s) vertices, yielding a problem kernel. To this end, we also show how to exploit structural properties of the specific problem in order to significantly improve the running time of the proposed kernelization method. [ABSTRACT FROM AUTHOR]

Abstract: We introduce overlap cluster graph modification problems where, other than in most previous works, the clusters of the target graph may overlap. More precisely, the studied graph problems ask for a minimum number of edge modifications such that the resulting graph consists of clusters (that is, maximal cliques) that may overlap up to a certain amount specified by the overlap number . In the case of -vertex-overlap, each vertex may be part of at most  maximal cliques; -edge-overlap is analogously defined in terms of edges. We provide a complexity dichotomy (polynomial-time solvable versus NP-hard) for the underlying edge modification problems, develop forbidden subgraph characterizations of “cluster graphs with overlaps”, and study the parameterized complexity in terms of the number of allowed edge modifications, achieving fixed-parameter tractability (in case of constant -values) and parameterized hardness (in case of unbounded -values). [Copyright &y& Elsevier]

We introduce the S-PLEX CLUSTER EDITING problem as a generalization of the well-studied CLUSTER EDITING problem; both are NP-hard and both are motivated by graph-based data clustering. Instead of transforming a given graph by a minimum number of edge modifications into a disjoint union of cliques (this is CLUSTER EDITING), the task in the case of S-PLEX CLUSTER EDITING is to transform a graph into a cluster graph consisting of a disjoint union of so-called s-plexes. Herein, an s-plex is a vertex set S inducing a subgraph in which every vertex has degree at least |S| -- s. Cliques are 1-plexes. The advantage of s-plexes for s ≥ 2 is that they allow us to model a more relaxed cluster notion (s-plexes instead of cliques), better reflecting inaccuracies of the input data. We develop a provably effective preprocessing based on data reduction (yielding a so-called problem kernel), a forbidden subgraph characterization of s-plex cluster graphs, and a depth-bounded search tree which is used to find optimal edge modification sets. Altogether, this yields efficient algorithms in case of moderate numbers of edge modifications; this is often a reasonable assumption under a maximum parsimony model for data clustering. [ABSTRACT FROM AUTHOR]

Abstract: Complementing recent progress on classical complexity and polynomial-time approximability of feedback set problems in (bipartite) tournaments, we extend and improve fixed-parameter tractability results for these problems. We show that Feedback Vertex Set in tournaments (FVST) is amenable to the novel iterative compression technique, and we provide a depth-bounded search tree for Feedback Arc Set in bipartite tournaments based on a new forbidden subgraph characterization. Moreover, we apply the iterative compression technique to d-Hitting Set, which generalizes Feedback Vertex Set in tournaments, and obtain improved upper bounds for the time needed to solve 4-Hitting Set and 5-Hitting Set. Using our parameterized algorithm for Feedback Vertex Set in tournaments, we also give an exact (not parameterized) algorithm for it running in time, where n is the number of input graph vertices, answering a question of Woeginger [G.J. Woeginger, Open problems around exact algorithms, Discrete Appl. Math. 156 (3) (2008) 397–405]. [Copyright &y& Elsevier]

Abstract: We introduce an NP-complete special case of the Weighted Set Cover problem and show its fixed-parameter tractability with respect to the maximum subset size, a parameter that appears to be small in relevant applications. More precisely, in this practically relevant variant we require that the given collection C of subsets of a base set S should be “tree-like”. That is, the subsets in C can be organized in a tree T such that every subset one-to-one corresponds to a tree node and, for each element s of S, the nodes corresponding to the subsets containing s induce a subtree of T. This is equivalent to the problem of finding a minimum edge cover in an edge-weighted acyclic hypergraph. Our main result is an algorithm running in time where k denotes the maximum subset size, , and . The algorithm also implies a fixed-parameter tractability result for the NP-complete Multicut in Trees problem, complementing previous approximation results. Our results find applications in computational biology in phylogenomics and for saving memory in tree decomposition based graph algorithms. [Copyright &y& Elsevier]

We initiate a systematic study of the ROW DELETION(B) problem on matrices: Given an input matrix A and a fixed "forbidden submatrix" B, the task is to remove a minimum number of rows from A such that no row or column permutation of B occurs as a submatrix in the resulting matrix. An application of this problem can be found, for instance, in the construction of perfect phylogenies. Establishing a strong connection to variants of the NP-complete HITTING SET problem, we describe and analyze structural properties of B that make ROW DELETION(B)NP-complete. On the positive side, the close relation with HITTING SET problems yields constant-factor polynomial-time approximation algorithms and fixed-parameter tractability results. [ABSTRACT FROM AUTHOR]

Given a collection C of subsets of size three of a finite set S and a positive integer k, the 3-Hitting Set problem is to determine a subset S′⊆S with &z.sfnc;S′&z.sfnc;⩽k, so that S′ contains at least one element from each subset in C. The problem is NP-complete, and is motivated, for example, by applications in computational biology. Improving previous work, we give an O(2.270k+n) time algorithm for 3-Hitting Set, which is efficient for small values of k, a typical occurrence in some applications. For d-Hitting Set we present an O(ck+n) time algorithm with c=d−1+O(d−1). [Copyright &y& Elsevier]

The classical, linear-time solvable Feedback Edge Set problem is concerned with finding a minimum number of edges intersecting all cycles in a (static, unweighted) graph. We provide a first study of this problem in the setting of temporal graphs , where edges are present only at certain points in time. We find that there are four natural generalizations of Feedback Edge Set , all of which turn out to be NP-hard. We also study the tractability of these problems with respect to several parameters (solution size, lifetime, and number of graph vertices, among others) and obtain some parameterized hardness but also fixed-parameter tractability results. [ABSTRACT FROM AUTHOR]

We investigate for temporal graphs the computational complexity of separating two distinct vertices s and z by vertex deletion. In a temporal graph, the vertex set is fixed but the edges have (discrete) time labels. Since the corresponding Temporal (s , z) -Separation problem is NP -complete, it is natural to investigate whether relevant special cases exist that are computationally tractable. To this end, we study restrictions of the underlying (static) graph—there we observe polynomial-time solvability in the case of bounded treewidth—as well as restrictions concerning the "temporal evolution" along the time steps. Systematically studying partially novel concepts in this direction, we identify sharp borders between tractable and intractable cases. [ABSTRACT FROM AUTHOR]

We study the NP-complete Minimum Shared Edges (MSE) problem, defined as follows. Given an undirected graph, a source and a sink vertex, and two integers p and k , we ask whether there are p paths in the graph connecting the source with the sink and sharing at most k edges. Herein, an edge is shared if it appears in at least two paths. On the positive side, we show that MSE is fixed-parameter tractable with respect to p. On the negative side, we show that MSE is W [ 1 ] -hard when parameterized by the treewidth of the input graph and the number k of shared edges combined, and that MSE does not admit a polynomial-size kernel with respect to p (unless NP ⊆ coNP / poly). [ABSTRACT FROM AUTHOR]

To cover the edges of a graph with a minimum number of cliques is an NP-hard problem with many applications. For this problem we develop efficient and effective polynomial-time data reduction rules that, combined with a search tree algorithm, allow for exact problem solutions in competitive time. This is confirmed by experiments with real-world and synthetic data. Moreover, we prove the fixed-parameter tractability of covering edges by cliques. [ABSTRACT FROM AUTHOR]

The NP-hard Distinct Vectors problem asks to delete as many columns as possible from a matrix such that all rows in the resulting matrix are still pairwise distinct. Our main result is that, for binary matrices, there is a complexity dichotomy for Distinct Vectors based on the maximum ( H ) and the minimum ( h ) pairwise Hamming distance between matrix rows: Distinct Vectors can be solved in polynomial time if H ≤ 2 ⌈ h / 2 ⌉ + 1 , and is NP-complete otherwise. Moreover, we explore connections of Distinct Vectors to hitting sets, thereby providing several fixed-parameter tractability and intractability results also for general matrices. [ABSTRACT FROM AUTHOR]

Abstract: We present a first thorough theoretical analysis of the Transitivity Editing problem on digraphs. Herein, the task is to make a given digraph transitive by a minimum number of arc insertions or deletions. Transitivity Editing has applications in the detection of hierarchical structure in molecular characteristics of diseases. We demonstrate that if the input digraph does not contain “diamonds”, then there is an optimal solution that performs only arc deletions. This fact helps us construct a first proof of NP-hardness, which also extends to the restricted cases in which the input digraph is acyclic or has maximum degree three. By providing an -vertex problem kernel, we answer an open question from the literature. In case of digraphs with maximum degree d, an -vertex problem kernel can be shown. Moreover, we improve previous fixed-parameter algorithms, now achieving a running time of for an n-vertex digraph if k arc modifications are sufficient to make it transitive. Our hardness as well as algorithmic results transfer to Transitivity Deletion, where only arc deletions are allowed. [Copyright &y& Elsevier]

Abstract: We develop an algorithmically useful refinement of a forbidden submatrix characterization of 0/1-matrices fulfilling the Consecutive Ones Property (C1P). This characterization finds applications in new polynomial-time approximation algorithms and fixed-parameter tractability results for the NP-hard problem to delete a minimum number of rows or columns from a 0/1-matrix such that the remaining submatrix has the C1P. [Copyright &y& Elsevier]

Abstract: We show that the two NP-complete problems of Dodgson Score and Young Score have differing computational complexities when the winner is close to being a Condorcet winner. On the one hand, we present an efficient fixed-parameter algorithm for determining a Condorcet winner in Dodgson elections by a minimum number of switches in the votes. On the other hand, we prove that the corresponding problem for Young elections, where one has to delete votes instead of performing switches, is W[2]-complete. In addition, we study Dodgson elections that allow ties between the candidates and give fixed-parameter tractability as well as W[2]-completeness results depending on the cost model for switching ties. [Copyright &y& Elsevier]

Abstract: Many NP-complete problems on planar graphs are “fixed-parameter tractable:” Recent theoretical work provided tree decomposition-based fixed-parameter algorithms exactly solving various parameterized problems on planar graphs, among others VERTEX COVER, in time . Here, is some constant depending on the graph problem to be solved, is the number of graph vertices, and is the problem parameter (for VERTEX COVER this is the size of the vertex cover). In this paper, we present an experimental study for such tree decomposition-based algorithms focusing on VERTEX COVER. We demonstrate that the tree decomposition-based approach provides a valuable way of exactly solving VERTEX COVER on planar graphs. Doing so, we also demonstrate the impressive power of the so-called Nemhauser/Trotter theorem which provides a VERTEX COVER-specific, extremely useful data reduction through polynomial time preprocessing. Altogether, this underpins the practical importance of the underlying theory. [Copyright &y& Elsevier]

We discuss general techniques, centered around the “Layerwise Separation Property” (LSP) of a planar graph problem, that allow to develop algorithms with running time c√ of k&z.sfnc;G&z.sfnc;, given an instance G of a problem on planar graphs with parameter k. Problems having LSP include planar vertex cover, planar independent set, and planar dominating set. Extensions of our speed-up technique to basically all fixed-parameter tractable planar graph problems are also exhibited. Moreover, we relate, e.g., the domination number or the vertex cover number, with the treewidth of a plane graph. [Copyright &y& Elsevier]

We continue and extend previous work on the parameterized complexity analysis of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby strengthening earlier results both on the side of parameterized hardness as well as on the side of fixed-parameter tractability. Other than for its famous sister problem Stable Marriage which focuses on a bipartite scenario, Stable Roommates with Incomplete Lists allows for arbitrary acceptability graphs whose edges specify the possible matchings of each two agents (agents are represented by graph vertices). Herein, incomplete lists and ties reflect the fact that in realistic application scenarios the agents cannot bring all other agents into a linear order. Among our main contributions is to show that it is W[1]-hard to compute a maximum-cardinality stable matching for acceptability graphs of bounded treedepth, bounded tree-cut width, and bounded disjoint paths modulator number (these are each time the respective parameters). Moreover, we obtain that 'only' asking for perfect stable matchings or the mere existence of a stable matching is fixed-parameter tractable with respect to tree-cut width but not with respect to treedepth. On the positive side, we also provide fixed-parameter tractability results for the parameter feedback edge set number. [ABSTRACT FROM AUTHOR]

Motivated by applications in privacy-preserving data publishing, we study the problem of making an undirected graph k -anonymous by adding few vertices (together with some incident edges). That is, after adding these “dummy vertices”, for every vertex degree d appearing in the resulting graph, there shall be at least k vertices with degree d . We explore three variants of vertex addition (justified by real-world considerations) and study their (parameterized) computational complexity. We derive mostly intractability results, even for very restricted cases (including trees and bounded-degree graphs) but also obtain some encouraging fixed-parameter tractability results. [ABSTRACT FROM AUTHOR]

Abstract: We propose an effective polynomial-time preprocessing strategy for intractable median problems. Developing a new methodological framework, we show that if the input objects of generally intractable problems exhibit a sufficiently high degree of similarity between each other on average, then there are efficient exact solving algorithms. In other words, we show that the median problems Swap Median Permutation, Consensus Clustering, Kemeny Score, and Kemeny Tie Score all are fixed-parameter tractable with respect to the parameter “average distance between input objects”. To this end, we develop the novel concept of “partial kernelization” and, furthermore, identify polynomial-time solvable special cases for the considered problems. [Copyright &y& Elsevier]

Abstract: We do computational studies concerning the enumeration of isolated cliques in graphs. Isolation, as recently introduced, measures the degree of connectedness of the cliques to the rest of the graph. Isolation helps both in getting faster algorithms for the enumeration of maximal general cliques and in filtering out cliques with special semantics. We compare three isolation concepts and their combination with two enumeration modi for maximal cliques (“isolated maximal” vs “maximal isolated”). All studied concepts exhibit the fixed-parameter tractability of the enumeration task with respect to the parameter “degree of isolation”. We provide a first systematic experimental study of the corresponding enumeration algorithms, using synthetic graphs (in the model), financial networks, and a music artist similarity network, proposing the enumeration of isolated cliques as a useful instrument in analyzing financial and social networks. [Copyright &y& Elsevier]