Search

A matrix M is said to be k-anonymous if for each row r in M there are at least k − 1 other rows in M which are identical to r. The NP-hard k- Anonymity problem asks, given an n × m-matrix M over a fixed alphabet and an integer s > 0, whether M can be made k-anonymous by suppressing (blanking out) at most s entries. Complementing previous work, we introduce two new 'data-driven' parameterizations for k- Anonymity-the number t of different input rows and the number t of different output rows-both modeling aspects of data homogeneity. We show that k- Anonymity is fixed-parameter tractable for the parameter t, and that it is NP-hard even for t = 2 and alphabet size four. Notably, our fixed-parameter tractability result implies that k- Anonymity can be solved in linear time when t is a constant. Our computational hardness results also extend to the related privacy problems p- Sensitivity and ℓ- Diversity, while our fixed-parameter tractability results extend to p- Sensitivity and the usage of domain generalization hierarchies, where the entries are replaced by more general data instead of being completely suppressed. [ABSTRACT FROM AUTHOR]

Abstract: The min-edge clique partition problem asks to find a partition of the vertices of a graph into a set of cliques with the fewest edges between cliques. This is a known NP-complete problem and has been studied extensively in the scope of fixed-parameter tractability (FPT) where it is commonly known as the Cluster Deletion problem. Many of the recently-developed FPT algorithms rely on being able to solve Cluster Deletion in polynomial time on restricted graph structures. We prove new structural properties of cographs which characterize how a largest clique interacts with the rest of the graph. These results imply a remarkably simple polynomial time algorithm for Cluster Deletion on cographs. In contrast, we observe that Cluster Deletion remains NP-hard on a hereditary graph class which is slightly larger than cographs. [Copyright &y& Elsevier]

Abstract: We consider the following problem called the k-Chinese Postman Problem (k-CPP): given a connected edge-weighted graph G and integers p and k, decide whether there are at least k closed walks such that every edge of G is contained in at least one of them and the total weight of the edges in the walks is at most p? The problem k-CPP is NP-complete, and van Bevern et al. [4] and Sorge [14] asked whether the k-CPP is fixed-parameter tractable when parameterized by k. We prove that the k-CPP is indeed fixed-parameter tractable. In fact, we prove a stronger result: the problem admits a kernel with vertices. We prove that the directed version of k-CPP is NP-complete and ask whether the directed version is fixed-parameter tractable when parameterized by k. [Copyright &y& Elsevier]

Abstract: Power assignment in wireless ad hoc networks can be seen as a family of problems in which the task is to find in a given power requirement network a minimum power communication subnetwork that satisfies a given connectivity constraint. These problems have been extensively studied from the viewpoint of approximation, heuristic, linear programming, etc. In this paper, we add a new facet by initiating a systematic parameterized complexity study of three types of power assignment problems related to multicast: Min-power Single-source -Multicast, Min-power Strongly Connected -Multicast and Min-power Multi-source -Multicast. We investigate their parameterized complexities with respect to the number of terminals and the number of senders. We show that a Min-power Single-source -Multicast is fixed-parameter tractable with respect to the number of terminals and achieve several parameterized hardness results. [Copyright &y& Elsevier]

The BIPARTITE CONTRACTION problem takes as input an n-vertex graph G and an integer κ, and the task is to determine whether we can obtain a bipartite graph from G by a sequence of at most κ edge contractions. We show that BIPARTITE CONTRACTION is fixed-parameter tractable when parameterized by κ. Despite a strong resemblance between Bipartite Contraction and the classical ODD CYCLE TRANSVERSAL (OCT) problem, the methods developed to tackle OCT do not seem to be directly applicable to BIPARTITE CONTRACTION. To obtain our result, we combine several techniques and concepts that are central in parameterized complexity: iterative compression, irrelevant vertices, and important separators. To the best of our knowledge, this is the first time the irrelevant vertex technique and the concept of important separators are applied in unison. Furthermore, our algorithm may serve as a comprehensible example of the usage of the irrelevant vertex technique. [ABSTRACT FROM AUTHOR]

Recently, we have shown that calculating the minimum-temporal-hybridization number for a set ${\mathcal{P}}$ of rooted binary phylogenetic trees is NP-hard and have characterized this minimum number when ${\mathcal{P}}$ consists of exactly two trees. In this paper, we give the first characterization of the problem for ${\mathcal{P}}$ being arbitrarily large. The characterization is in terms of cherries and the existence of a particular type of sequence. Furthermore, in an online appendix to the paper, we show that this new characterization can be used to show that computing the minimum-temporal hybridization number for two trees is fixed-parameter tractable. [ABSTRACT FROM AUTHOR]

Abstract: We study the following general stabbing problem from a parameterized complexity point of view: Given a set of n translates of an object in , find a set of k lines with the property that every object in is “stabbed” (intersected) by at least one line. We show that when S consists of axis-parallel unit squares in the (decision) problem of stabbing S with axis-parallel lines is W[1]-hard with respect to k (and thus, not fixed-parameter tractable unless FPT=W[1]) while it becomes fixed-parameter tractable when the squares are disjoint. We also show that the problem of stabbing a set of disjoint unit squares in with lines of arbitrary directions is W[1]-hard with respect to k. Several generalizations to other types of objects and lines with arbitrary directions are also presented. Finally, we show that deciding whether a set of unit balls in can be stabbed by one line is W[1]-hard with respect to the dimension d. [Copyright &y& Elsevier]

We extend previous work on the parameterized complexity of local search for the Traveling Salesperson Problem (TSP). So far, its parameterized complexity has been investigated with respect to the distance measures (defining the local search area) 'Edge Exchange' and 'Max-Shift'. We perform studies with respect to the distance measures 'Swap' and ' r-Swap', 'Reversal' and ' r-Reversal', and 'Edit', achieving both fixed-parameter tractability and W[1]-hardness results. In particular, from the parameterized reduction showing W[1]-hardness we infer running time lower bounds (based on the exponential time hypothesis) for all corresponding distance measures. Moreover, we provide non-existence results for polynomial-size problem kernels and we show that some in general W[1]-hard problems turn fixed-parameter tractable when restricted to planar graphs. [ABSTRACT FROM AUTHOR]

We present a method for reducing the treewidth of a graph while preserving all of itsminimal s-t separators up to a certain fixed size k. This technique allows us to solve s - t CUT and MULTICUT problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set or induce a connected graph) in linear time for every fixed number k of removed vertices. Our results have applications for problems that are not directly defined by separators, but the known solution methods depend on some variant of separation. For example, we can solve similarly restricted generalizations of BIPARTIZATION (delete at most k vertices from G to make it bipartite) in almost linear time for every fixed number k of removed vertices. These results answer a number of open questions in the area of parameterized complexity. Furthermore, our technique turns out to be relevant for (H,C, K)- and (H,C,≤K)- coloring problems as well, which are cardinality constrained variants of the classical H-coloring problem. We make progress in the classification of the parameterized complexity of these problems by identifying new cases that can be solved in almost linear time for every fixed cardinality bound. [ABSTRACT FROM AUTHOR]

Given a directed graph G, a set of k terminals, and an integer p, the Directed Vertex Multiway Cut problem asks whether there is a set S of at most p (nonterminal) vertices whose removal disconnects each terminal from all other terminals. Directed Edge Multiway Cut is the analogous problem where S is a set of at most p edges. These two problems are indeed known to be equivalent. A natural generalization of the multiway cut is the Multicut problem, in which we want to disconnect only a set of k given pairs instead of all pairs. Marx [Theoret. Comput. Sci., 351 (2006), pp. 394--406] showed that in undirected graphs Vertex/Edge Multiway cut is fixed-parameter tractable (FPT) parameterized by p. Marx and Razgon [Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011, pp. 469--478] showed that undirected Multicut is FPT and Directed Multicut is W[1]-hard parameterized by p. We complete the picture here by our main result, which is that both Directed Vertex Multiway Cut and Directed Edge Multiway Cut can be solved in time 2²O(p) nO(1), i.e., FPT parameterized by size p of the cutset of the solution. This answers an open question raised by the aforementioned papers. It follows from our result that Directed Edge/Vertex Multicut is FPT for the case of k = 2 terminal pairs, which answers another open problem raised by Marx and Razgon. [ABSTRACT FROM AUTHOR]

We present new and improved fixed-parameter algorithms for computing maximum agreement forests of pairs of rooted binary phylogenetic trees. The size of such a forest for two trees corresponds to their subtree prune-and-regraft distance and, if the agreement forest is acyclic, to their hybridization number. These distance measures are essential tools for understanding reticulate evolution. Our algorithm for computing maximum acyclic agreement forests is the first depth-bounded search algorithm for this problem. Our algorithms substantially outperform the best previous algorithms for these problems. [ABSTRACT FROM AUTHOR]

Comparing and ranking information is an important topic in social and information sciences, and in particular on the web. Its objective is to measure the difference of the preferences of voters on a set of candidates and to compute a consensus ranking. Commonly, each voter provides a total order of all candidates. Recently, this approach was generalized to bucket orders, which allow ties. In this work we further generalize and consider total, bucket, interval and partial orders. The disagreement between two orders is measured by the nearest neighbor Spearman footrule distance, which has not been studied so far. For two bucket orders and for a total and an interval order the nearest neighbor Spearman footrule distance is shown to be computable in linear time, whereas for a total and a partial order the computation is NP-hard, 4-approximable and fixed-parameter tractable. Moreover, in contrast to the well-known efficient solution of the rank aggregation problem for total orders, we prove the NP-completeness for bucket orders and establish a 4-approximation. [ABSTRACT FROM AUTHOR]

Abstract: The diameter of a graph is the maximum distance between any pair of vertices in the graph. The Diameter- Augmentation problem takes as input a graph and a positive integer and asks whether there exists a set of at most new edges so that the graph has diameter . This problem is NP-hard (Schoone et al. 1987) [10], even in the case (Li et al. 1992) [7]. We give a parameterized reduction from Dominating Set to Diameter- Augmentation to prove that Diameter- Augmentation is -hard for every . [Copyright &y& Elsevier]

We study the NP-hard Target Set Selection (TSS) problem occurring in social network analysis. Roughly speaking, given a graph where each vertex is associated with a threshold, in TSS the task is to select a minimum-size 'target set' such that all vertices of the graph get activated. Activation is a dynamic process. First, only the vertices in the target set are active. Then, a vertex becomes active if the number of its active neighbors exceeds its threshold, and so on. TSS models the spread of information, infections, and influence in networks. Complementing results on its polynomial-time approximability and extending results for its restriction to trees and bounded treewidth graphs, we classify the influence of the parameters 'diameter', 'cluster editing number', 'vertex cover number', and 'feedback edge set number' of the underlying graph on the problem's computational complexity, revealing both tractable and intractable cases. For instance, even for diameter-two split graphs TSS remains W[2]-hard with respect to the parameter 'size of the target set'. TSS can be efficiently solved on graphs with small feedback edge set number and also turns out to be fixed-parameter tractable when parameterized by the vertex cover number. Both results contrast known parameterized intractability results for the parameter 'treewidth'. While these tractability results are relevant for sparse networks, we also show efficient fixed-parameter algorithms for the parameter 'cluster editing number', yielding tractability for certain dense networks. [ABSTRACT FROM AUTHOR]

In this paper, we consider multi-objective evolutionary algorithms for the Vertex Cover problem in the context of parameterized complexity. We consider two different measures for the problem. The first measure is a very natural multi-objective one for the use of evolutionary algorithms and takes into account the number of chosen vertices and the number of edges that remain uncovered. The second fitness function is based on a linear programming formulation and proves to give better results. We point out that both approaches lead to a kernelization for the Vertex Cover problem. Based on this, we show that evolutionary algorithms solve the vertex cover problem efficiently if the size of a minimum vertex cover is not too large, i.e., the expected runtime is bounded by O( f(OPT)⋅ n), where c is a constant and f a function that only depends on OPT. This shows that evolutionary algorithms are randomized fixed-parameter tractable algorithms for the vertex cover problem. [ABSTRACT FROM AUTHOR]

Abstract: The maximum induced matching problem is known to be APX-hard in the class of bipartite graphs. Moreover, the problem is also intractable in this class from a parameterized point of view, i.e. it is W[1]-hard. In this paper, we reveal several classes of bipartite (and more general) graphs for which the problem admits fixed-parameter tractable algorithms. We also study the computational complexity of the problem for regular bipartite graphs and prove that the problem remains APX-hard even under this restriction. On the other hand, we show that for hypercubes (a proper subclass of regular bipartite graphs) the problem admits a simple solution. [Copyright &y& Elsevier]

Abstract: We prove that weighted circuit satisfiability for monotone or antimonotone circuits has no fixed-parameter tractable approximation algorithm with any approximation ratio function ρ, unless . In particular, not having such an fpt-approximation algorithm implies that these problems have no polynomial-time approximation algorithms with ratio for any nontrivial function ρ. [Copyright &y& Elsevier]

The classical Feedback Vertex Set problem asks, for a given undirected graph G and an integer k, to find a set of at most k vertices that hits all the cycles in the graph G. Feedback Vertex SET has attracted a large amount of research in the parameterized setting, and subsequent fixed-parameter and kernelization algorithms have been a rich source of ideas in the field. In this paper we consider a more general and difficult version of the problem, named Subset Feedback Vertex SET (Subset-FVS), where an instance comes additionally with a set S ⊆ V of vertices, and we ask for a set of at most k vertices that hits all simple cycles passing through S. Because of its applications in circuit testing and genetic linkage analysis, Subset-FVS was studied from the approximation algorithm perspective by Even et al. [SIAM J. Discrete Math., 13 (2000), pp. 225-267; SIAM J. Comput., 30 (2000), pp. 1231-1252]. The question of whether the Subset-FVS problem is fixed-parameter tractable was posed independently by Kawarabayashi and Saurabh in 2009. We answer this question affirmatively. We begin by showing that this problem is fixed-parameter tractable when parameterized by |S|. Next we present an algorithm which reduces the given instance to 2knO(1) instances with the size of S bounded by O(k³), using kernelization techniques such as the 2-expansion lemma, Menger's theorem, and Gallai's theorem. These two facts allow us to give a 2O(k log k)nO(1) time algorithm solving the Subset-FVS problem, proving that it is indeed fixed-parameter tractable. [ABSTRACT FROM AUTHOR]

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]

Abstract: The model-checking problem for monadic second-order logic on graphs is fixed-parameter tractable with respect to tree-width and clique-width. The proof constructs finite automata from monadic second-order sentences. These automata recognize the terms over fixed finite signatures that define graphs satisfying the given sentences. However, this construction produces automata of hyper-exponential sizes, and is thus impossible to use in practice in many cases. To overcome this difficulty, we propose to specify the transitions of automata by programs instead of tables. Such automata are called fly-automata. By using them, we can check certain monadic second-order graph properties with limited quantifier alternation depth, that are nevertheless interesting for Graph Theory. We give explicit constructions of automata relative to graphs of bounded clique-width, and we report on experiments. [Copyright &y& Elsevier]