Incompleteness management has become a popular research topic and been viewed in many applications in the area of data quality and data management. Traditional methods for handling incompleteness assume data is totall...
详细信息
Incompleteness management has become a popular research topic and been viewed in many applications in the area of data quality and data management. Traditional methods for handling incompleteness assume data is totally complete or incomplete. However, in practical applications, data is often partial complete, which means that data is not totally complete but some special parts of the data satisfying given semantic specifications are complete. Intuitively, partial complete data can still give complete answers for queries consistent with the semantic specifications. Therefore, it is highly needed to study the fundamental problems for managing partial complete data. However, as far as known by us, there are only few works focusing on this area. The most important and fundamental problem, completeness reasoning, is studied from the aspect of parameterized complexity by this paper. The completeness reasoning problem, TC-QC (Table Completeness to Query Completeness), is first formally defined and studied by Razniewski et al. [1]. Given completeness statements of data, the goal of the TC-QC problem is to determine whether the result of a special query Q is complete, that is to reason query completeness based on given data completeness. Razniewski et al. have shown that the TC-QC problem is NP-hard even for conjunctive queries, and a natural and interesting question is whether or not TC-QC can be solved efficiently by parameterized algorithms. To answer that, the parameterized complexities of completeness reasoning for conjunctive queries are studied by the paper. First, it is shown that, considering the parameterizations defined by the size of query completeness or table completeness, the parameterized TC-QC problem for conjunctive queries is para-NP-complete, which strongly indicate that the TC-QC problems parameterized by the above two parameters do not admit fixed-parameter tractable algorithms. Then, for more special cases parameterized by different constraints on quer
First, we close the multi-parameter analysis of a canonical problem concerning short reset words (SYN) initiated by Fernau et al. (2013). Namely, we prove that the problem, parameterized by the number of states, does ...
详细信息
First, we close the multi-parameter analysis of a canonical problem concerning short reset words (SYN) initiated by Fernau et al. (2013). Namely, we prove that the problem, parameterized by the number of states, does not admit a polynomial kernel unless the polynomial hierarchy collapses. Second, we consider a related canonical problem concerning synchronizing road colorings (SRCP). Here we give a similar complete multi-parameter analysis. Namely, we show that the problem, parameterized by the number of states, admits a polynomial kernel and we close the previous research of restrictions to particular values of both the alphabet size and the maximum length of a reset word.
We introduce the LONGEST COMPATIBLE SEQUENCE (SLCS) problem. This problem deals with p-sequences, which are strings on a given alphabet where each letter occurs at most once. The SLCS problem takes as input a collecti...
详细信息
We introduce the LONGEST COMPATIBLE SEQUENCE (SLCS) problem. This problem deals with p-sequences, which are strings on a given alphabet where each letter occurs at most once. The SLCS problem takes as input a collection of k p-sequences on a common alphabet L of size n, and seeks a p-sequence on L which respects the precedence constraints induced by each input sequence, and is of maximal length with this property. We investigate the parameterized complexity and the approximability of the problem. As a by-product of our hardness results for the SLCS problem, we derive new hardness results for the LONGEST COMMON SUBSEQUENCE problem and other problems that are hard for the W-hierarchy. (C) 2011 Published by Elsevier B.V.
The problem MaxLin2 can be stated as follows. We are given a system S of m equations in variables x (1),aEuro broken vertical bar,x (n) , where each equation is assigned a positive integral weight w (j) and , I (j) aS...
详细信息
The problem MaxLin2 can be stated as follows. We are given a system S of m equations in variables x (1),aEuro broken vertical bar,x (n) , where each equation is assigned a positive integral weight w (j) and , I (j) aS dagger{1,2,aEuro broken vertical bar,n} for j=1,aEuro broken vertical bar,m. We are required to find an assignment of values in to the variables in order to maximize the total weight of the satisfied equations. Let W be the total weight of all equations in S. We consider the following parameterized version of MaxLin2: decide whether there is an assignment satisfying equations of total weight at least W-k, where k is a nonnegative parameter. We prove that this parameterized problem is W[1]-hard even if each equation of S has exactly three variables and every variable appears in exactly three equations and, moreover, each weight w (j) equals 1 and no two equations have the same left-hand side. We show the tightness of this result by proving that if each equation has at most two variables then the parameterized problem is fixed-parameter tractable. We also prove that if no variable appears in more than two equations then we can maximize the total weight of satisfied equations in polynomial time.
In this article, we study the complexity of weighted team definability for logics with team semantics. This problem is a natural analog of one of the most studied problems in parameterized complexity, the notion of we...
详细信息
In this article, we study the complexity of weighted team definability for logics with team semantics. This problem is a natural analog of one of the most studied problems in parameterized complexity, the notion of weighted Fagin-definability, which is formulated in terms of satisfaction of first-order formulas with free relation variables. We focus on the parameterized complexity of weighted team definability for a fixed formula $\varphi$ of central team-based logics. Given a first-order structure $\mathcal{A}$ and the parameter value $k\in \mathbb N$ as input, the question is to determine whether $\mathcal{A},T\models \varphi$ for some team T of size k. We show several results on the complexity of this problem for dependence, independence, and inclusion logic formulas. Moreover, we also relate the complexity of weighted team definability to the complexity classes in the well-known W-hierarchy as well as paraNP.
We study the parameterized complexity of voter control problems in -peaked elections, where is a positive integer. In particular, we focus on the constructive/destructive control by adding/deleting votes for Condorcet...
详细信息
We study the parameterized complexity of voter control problems in -peaked elections, where is a positive integer. In particular, we focus on the constructive/destructive control by adding/deleting votes for Condorcet, Maximin and Copeland. It is known that in general elections all these problems are NP-hard, except for the destructive control by adding/deleting votes for Condorcet which is polynomial-time solvable. We strengthen these results by showing that, when restricted to -peaked elections where =3,4, the above NP-hard problems not only remain NP-hard but also are W[1]-hard with respect to the number of added/deleted votes.
In a vertex-colored graph, an edge is happy if its endpoints have the same color. Similarly, a vertex is happy if all its incident edges are happy. Motivated by the computation of homophily in social networks, we cons...
详细信息
In a vertex-colored graph, an edge is happy if its endpoints have the same color. Similarly, a vertex is happy if all its incident edges are happy. Motivated by the computation of homophily in social networks, we consider the algorithmic aspects of the following MAXIMUM HAPPY EDGES (k-MHE) problem: given a partially k-colored graph G and an integer l, find an extended full k-coloring of G making at least l edges happy. When we want to make l vertices happy on the same input, the problem is known as MAXIMUM HAPPY VERTICES (k-MHV). We perform an extensive study into the complexity of the problems, particularly from a parameterized viewpoint. For every k >= 3, we prove both problems can be solved in time 2(n) n(O(1)). Moreover, by combining this result with a linear vertex kernel of size (k + l) for k-MHE, we show that the edge-variant can be solved in time 2(l)n(O(1)). In contrast, we prove that the vertex-variant remains W[1]-hard for the natural parameter l. However, the problem does admit a kernel with O (k(2)l(2)) vertices for the combined parameter k + l. From a structural perspective, we show both problems are fixed-parameter tractable for treewidth and neighborhood diversity, which can both be seen as sparsity and density measures of a graph. Finally, we extend the known NP-completeness results of the problems by showing they remain hard on bipartite graphs and split graphs. On the positive side, we show the vertex-variant can be solved optimally in polynomial-time for cographs. (C) 2020 Elsevier B.V. All rights reserved.
The Closest String problem asks to find a string s which is not too far from each string in a set of m input strings, where the distance is taken as the Hamming distance. This well-studied problem has various applicat...
详细信息
The Closest String problem asks to find a string s which is not too far from each string in a set of m input strings, where the distance is taken as the Hamming distance. This well-studied problem has various applications in computational biology and drug design. In this paper, we introduce a new variant of Closest String where the input strings can contain wildcards that can match any letter in the alphabet, and the goal is to find a solution string without wildcards. We call this problem the Closest String with Wildcards problem, and we analyze it in the framework of parameterized complexity. Our study determines for each natural parameterization whether this parameterization yields a fixed-parameter algorithm, or whether such an algorithm is highly unlikely to exist. (C) 2015 Elsevier B.V. All rights reserved.
We consider the weighted satisfiability problem for Boolean circuits and propositional formule, where the weight of an assignment is the number of variables set to true. We study the parameterized complexity of these ...
详细信息
We consider the weighted satisfiability problem for Boolean circuits and propositional formule, where the weight of an assignment is the number of variables set to true. We study the parameterized complexity of these problems and initiate a systematic study of the complexity of its fragments. Only the monotone fragment has been considered so far and proven to be of same complexity as the unrestricted problems. Here, we consider all fragments obtained by semantically restricting circuits or formule to contain only gates (connectives) from a fixed set B of Boolean functions. We obtain a dichotomy result by showing that for each such B, the weighted satisfiability problems are either W [P] -complete (for circuits) or W [SAT] -complete (for formule) or efficiently solvable. We also consider the related enumeration and counting problems.
In this Letter, we consider the parameterized complexity of the following problem: Given a hereditary property P on digraphs, an input digraph D and a positive integer k, does D have an induced subdigraph on k vertice...
详细信息
In this Letter, we consider the parameterized complexity of the following problem: Given a hereditary property P on digraphs, an input digraph D and a positive integer k, does D have an induced subdigraph on k vertices with property P? We completely characterize hereditary properties for which this induced subgraph problem is W[1]-complete for two classes of directed graphs: general directed graphs and oriented graphs. We also characterize those properties for which the induced subgraph problem is,W[l]-complete for general directed graphs but fixed parameter tractable for oriented graphs. These results are among the very few parameterized complexity results on directed graphs. (c) 2007 Elsevier B.V. All rights reserved.
暂无评论