AS BIN PACKING is NP-hard already for k = 2 bins. it is unlikely to be solvable in polynomial time even if the number of bins is a fixed constant. However, if the sizes of the items are polynomially bounded integers, ...
详细信息
AS BIN PACKING is NP-hard already for k = 2 bins. it is unlikely to be solvable in polynomial time even if the number of bins is a fixed constant. However, if the sizes of the items are polynomially bounded integers, then the problem can be solved in time n(O(k)) for an input of length n by dynamic programming. We show, by proving the W[1]-hardness of UNARY BIN PACKING (where the sizes are given in unary encoding), that this running time cannot be improved to f (k) . n(O(1)) for any function f (k) (under standard complexity assumptions). On the other hand, we provide an algorithm for BIN PACKING that obtains in time 2(O(k log2 k)) + O (n) a solution with additive error at most 1. i.e., either finds a packing into k + 1 bins or decides that k bins do not suffice. (c) 2012 Elsevier Inc. All rights reserved.
It is known that the problem of deleting at most k vertices to obtain a proper interval graph (Proper Interval Vertex Deletion) is fixed parameter tractable. However, whether the problem admits a polynomial kernel or ...
详细信息
It is known that the problem of deleting at most k vertices to obtain a proper interval graph (Proper Interval Vertex Deletion) is fixed parameter tractable. However, whether the problem admits a polynomial kernel or not was open. Here, we answer this question in the affirmative by obtaining a polynomial kernel for Proper Interval Vertex Deletion. This resolves an open question of van Bevern et al. [Graph-Theoretic Concepts in Computer Science (WG 2010), Lecture Notes in Comput. Sci. 6410, Springer, Berlin, 2010, pp. 232-243].
Given a graph G and an integer k, the Pi Edge Completion/Editing/Deletion problem asks whether it is possible to add, edit, or delete at most k edges in G such that one obtains a graph that fulfills the property Pi. E...
详细信息
Given a graph G and an integer k, the Pi Edge Completion/Editing/Deletion problem asks whether it is possible to add, edit, or delete at most k edges in G such that one obtains a graph that fulfills the property Pi. Edge modification problems have received considerable interest from a parameterized point of view. When parameterized by k, many of these problems turned out to be fixed-parameter tractable and some are known to admit polynomial kernelizations, i.e., efficient preprocessing with a size guarantee that is polynomial in k. This paper answers an open problem posed by Cai (IWPEC 2006) [11], namely, whether the Pi Edge Deletion problem, parameterized by the number of deletions, admits a polynomial kernelization when Pi can be characterized by a finite set of forbidden induced subgraphs. We answer this question negatively based on the framework for kernelization lower bounds of Bodlaender et al. (ICALP 2008, JCSS 2009)[15] and Fortnow and Santhanam (STOC 2008, JCSS 2011)[16]. We present a graph H on seven vertices such that H-free Edge Deletion and H-free Edge Editing do not admit polynomial kernelizations, unless NP subset of coNP/poly. The application of the framework is not immediate and requires a lower bound for a Not-1-in-3 SAT problem that may be of independent interest. (C) 2013 Elsevier B.V. All rights reserved.
Publishing personal data without giving up privacy is becoming an increasingly important problem in different fields. In the last years, different interesting approaches have been proposed, i.e. k-Anonymity and l-Dive...
详细信息
Publishing personal data without giving up privacy is becoming an increasingly important problem in different fields. In the last years, different interesting approaches have been proposed, i.e. k-Anonymity and l-Diversity. Given an input table, these approaches partition its rows so that the computed partition satisfies some constraint, in order to prevent the inference of the individuals the data belong to. Then, the rows in a same set of the partition are related to the same rows by suppressing some of their entries. Here we focus on the I-Diversity problem, where the attributes of the input table are distinguished in sensitive attributes and quasi-identifier attributes. The goal is to partition the rows of the input table, so that each set C of the partition contains at most 1/l vertical bar C vertical bar rows having a specific value in the sensitive attribute, and the number of suppressions is minimized. In this paper we investigate the approximation and parameterized complexity of I-Diversity. First, we prove that the problem is not approximable within factor c in!, for some constant c > 0, even if the input table consists of only two columns, and that the problem is APX-hard, even if I = 4 and the input table contains exactly three columns. Then we give an approximation algorithm of factor m (where m + 1 is the number of columns in the input table), when the sensitive attribute ranges over an alphabet of constant size. Concerning the parameterized complexity, we prove that the problem is W[1]-hard when parameterized by the cost-bound, by l, and by the size of the alphabet. Then we prove that the problem admits a fixed-parameter algorithm when both the maximum number of different values in a column and the number of columns are parameters. (C) 2012 Elsevier B.V. All rights reserved.
The notion of treewidth plays an important role in theoretical and practical studies of graph problems. It has been recognized that, especially in practical environments, when computing the treewidth of a graph it is ...
详细信息
The notion of treewidth plays an important role in theoretical and practical studies of graph problems. It has been recognized that, especially in practical environments, when computing the treewidth of a graph it is invaluable to first apply an array of preprocessing rules that simplify and shrink it. This work seeks to prove rigorous performance guarantees for such preprocessing rules-known rules as well as more recent ones-by studying them in the framework of kernelization from parameterized complexity. It is known that the NP-complete problem of determining whether a given graph G has treewidth at most k admits no polynomial-time preprocessing algorithm that reduces any input instance to size polynomial in k, unless NP subset of coNP/poly and the polynomial hierarchy collapses to its third level. In this paper we therefore consider structural graph measures larger than treewidth, and determine whether efficient preprocessing can shrink the instance size to a polynomial in such a parameter value. We prove that, given an instance (G, k) of treewidth, we can efficiently reduce its size to O(FVS(G)(4)) vertices, where FVS(G) is the size of a minimum feedback vertex set in G. We can also prove a size reduction to O(VC(G)(3)) vertices, where VC(G) is the size of a minimum vertex cover. Phrased in the language of parameterized complexity, we show that Treewidth has a polynomial kernel when parameterized by the size of a given feedback vertex set, and also by the size of a vertex cover. In contrast we show that TREEWIDTH parameterized by the vertex-deletion distance to a single clique and WEIGHTED TREEWIDTH parameterized by the size of a vertex cover do not admit polynomial kernelizations unless NP subset of coNP/poly.
Connectivity problems like k-PATH and k-DISJOINT PATHS relate to many important milestones in parameterized complexity, namely the Graph Minors Project, color coding, and the recent development of techniques for obtai...
详细信息
Connectivity problems like k-PATH and k-DISJOINT PATHS relate to many important milestones in parameterized complexity, namely the Graph Minors Project, color coding, and the recent development of techniques for obtaining kernelization lower bounds. This work explores the existence of polynomial kernels for various path and cycle problems, by considering nonstandard parameterizations. We show polynomial kernels when the parameters are a given vertex cover, a modulator to a cluster graph, or a (promised) max leaf number. We obtain lower bounds via cross-composition, e.g., for HAMILTONIAN CYCLE and related problems when parameterized by a modulator to an outerplanar graph. (C) 2012 Elsevier B.V. All rights reserved.
Approximation algorithms and parameterized complexity are usually considered to be two separate ways of dealing with hard algorithmic problems. In this paper, our aim is to investigate how these two fields can be comb...
详细信息
Approximation algorithms and parameterized complexity are usually considered to be two separate ways of dealing with hard algorithmic problems. In this paper, our aim is to investigate how these two fields can be combined to achieve better algorithms than what any of the two theories could offer. We discuss the different ways parameterized complexity can be extended to approximation algorithms, survey results of this type and propose directions for future research.
The paper surveys parameterized algorithms and complexities for computational tasks on biopolymer sequences, including the problems of longest common subsequence, shortest common supersequence, pairwise sequence align...
详细信息
The paper surveys parameterized algorithms and complexities for computational tasks on biopolymer sequences, including the problems of longest common subsequence, shortest common supersequence, pairwise sequence alignment, multiple sequencing alignment, structure-sequence alignment and structure-structure alignment. Algorithm techniques, built on the structural-unit level as well as on the residue level, are discussed.
We investigate a special case of the Induced Subgraph Isomorphism problem, where both input graphs are interval graphs. We show the NP-hardness of this problem, and we prove fixed-parameter tractability of the problem...
详细信息
We investigate a special case of the Induced Subgraph Isomorphism problem, where both input graphs are interval graphs. We show the NP-hardness of this problem, and we prove fixed-parameter tractability of the problem with non-standard parameterization, where the parameter is the difference |V(G)|-|V(H)|, with G and H being the larger and the smaller input graph, respectively. Intuitively, we can interpret this problem as "cleaning" the graph G, regarded as a pattern containing extra vertices indicating errors, in order to obtain the graph H representing the original pattern. We also prove W[1]-hardness for the standard parameterization where the parameter is |V(H)|.
The MINIMUM FILL-IN problem is used to decide if a graph can be triangulated by adding at most k edges. In 1994, Kaplan, Shamir, and Tarjan showed that the problem is solvable in time O(2(O(k)) + k(2)nm) on graphs wit...
详细信息
The MINIMUM FILL-IN problem is used to decide if a graph can be triangulated by adding at most k edges. In 1994, Kaplan, Shamir, and Tarjan showed that the problem is solvable in time O(2(O(k)) + k(2)nm) on graphs with n vertices and m edges and thus is fixed parameter tractable. Here, we give the first subexponential parameterized algorithm solving MINIMUM FILL-IN in time O(2(O(root k log k)) + k(2)nm). This substantially lowers the complexity of the problem. Techniques developed for MINIMUM FILL-IN can be used to obtain subexponential parameterized algorithms for several related problems, including MINIMUM CHAIN COMPLETION, CHORDAL GRAPH SANDWICH, and TRIANGULATING COLORED GRAPH.
暂无评论