检索结果-内蒙古大学图书馆

SIAM JOURNAL ON DISCRETE MATHEMATICS 2017年第2期31卷 687-713页

作者： Bjorklund, Andreas Kamat, Vikram Kowalik, Lukasz Zehavi, Meirav Lund Univ Lund Sweden Virginia Commonwealth Univ Dept Math & Appl Math Med Coll Virginia Campus Richmond VA 23284 USA Warsaw Ctr Math & Comp Sci Warsaw Poland Univ Warsaw Warsaw Poland Technion IIT Haifa Israel

We show two results related to finding trees and paths in graphs. First, we show that in O* (1.657(k)2(l/2)) time one can either find a k-vertex tree with 1 leaves in an n-vertex undirected graph or conclude that such a tree does not exist. Our solution can be applied as a subroutine to solve the k-INTERNAL SPANNING TREE problem in O*(min(3.455(k), 1.946(n))) time using polynomial space, improving upon previous algorithms for this problem. In particular, for the first time we break the natural barrier of O*(2n). Second, we show that the running time can be improved whenever the host graph admits a vertex coloring with few colors;it can be an ordinary proper vertex coloring, a fractional vertex coloring, or a vector coloring. In effect, we show improved bounds for HAMILTONICITY and k-PATH in any graph of maximum degree Delta = 4,..., 12 or with vector chromatic number at most 8. Our results extend the technique by Bjorklund [SIAM J. Comput., 43 (2014), pp. 280-299] and Bjorklund et al. [Narrow Sieves for parameterized Paths and Packings, CoRR, arXiv:1007. 1161, 2010] to finding structures more general than paths as well as refine it to handle special classes of graphs more efficiently.

关键词： parameterized complexity Hamiltonian cycle k-Path k-INTERNAL SPANNING TREE algebraic techniques coloring fractional coloring vector coloring

来源：评论

学校读者我要写书评

暂无评论

An Upper Bound for Resolution Size: Characterization of Tractable SAT Instances 11th

An Upper Bound for Resolution Size: Characterization of Trac...

引用

11th International Conference and Workshops on Algorithms and Computation (WALCOM)

作者： Imanishi, Kensuke Univ Tokyo Dept Comp Sci Bunkyo Ku 7-3-1 Hongo Tokyo 1138656 Japan

ISBN: (纸本)9783319539256;9783319539249

We show the first upper bound for resolution size of a SAT instance by pathwidth of its incidence graph. Namely, we prove that if an incidence graph of an unsatisfiable CNF formula has pathwidth pw, the formula can be refuted by a resolution proof with at most O*(3(pw)) clauses. It is known that modern practical SAT-solvers run efficiently for instances which have small and narrow resolution refutations. Resolution size is one of the parameters which make SAT tractable, whereas it is shown that even linearly approximating the resolution size is NP-hard. In contrast, computing graph based parameters such as treewidth or pathwidth is fixed-parameter tractable, and also efficient FPT algorithms for SAT of bounded such parameters are widely researched. However, few explicit connection between these parameters and resolutions or SATsolvers are known. In this paper, we provide an FPT algorithm for SAT on path decomposition of its incidence graph. The algorithm can construct resolution refutations for unsatisfiable formulas, and analyzing the size of constructed proof gives the new bound.

关键词： Satisfiability parameterized complexity Resolution size Incidence graph Pathwidth

来源：评论

学校读者我要写书评

暂无评论

parameterized and subexponential-time complexity of satisfiability problems and applications

引用

THEORETICAL COMPUTER SCIENCE 2015年第Part3期607卷 282-295页

作者： Kanj, Iyad Szeider, Stefan Depaul Univ Sch Comp Chicago IL 60604 USA Vienna Univ Technol A-1040 Vienna Austria

We study the parameterized and the subexponential-time complexity of the weighted and the unweighted satisfiability problems on bounded-depth normalized Boolean circuits. We establish relations between the subexponential-time complexity of the weighted and the unweighted satisfiability problems, and use them to derive relations among the subexponential-time complexity of several NP-hard problem. We then study the role of certain natural structural parameters of the circuit in characterizing the parameterized and the subexponential-time complexity of the circuit satisfiability problems under consideration. We obtain threshold functions on some circuit structural parameters, including the depth, the number of gates, the fan-in, and the maximum number of (variable) occurrences, that lead to tight characterizations of the parameterized and the subexponential-time complexity of the circuit satisfiability problems under consideration. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Circuit satisfiability parameterized complexity Subexponential-time complexity

来源：评论

学校读者我要写书评

暂无评论

complexity of Controlling Nearly Single-Peaked Elections Revisited 18

Complexity of Controlling Nearly Single-Peaked Elections Rev...

引用

Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems

作者： Yongjie Yang Saarland University and Central South University Saarbrücken Germany

We investigate the complexity of Constructive Control by Adding/Deleting Votes (CCAV/CCDV) for r -approval, Condorcet, Maximin and Copeland α in k -axes and k -candidate partition single-peaked elections. In general, we prove that CCAV and CCDV for most of the voting correspondences mentioned above are NP-hard even when k is a very small constant. Exceptions are CCAV and CCDV for Condorcet and CCAV for r -approval in k -axes single-peaked elections, which we show to be fixed-parameter tractable with respect to k . In addition, we give a polynomial-time algorithm for recognizing 2-axes elections, resolving an open question.

关键词： nearly single-peaked election control parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Lossy Kernelization 2017

Lossy Kernelization

引用

49th Annual ACM-SIGACT Symposium on Theory of Computing (STOC)

作者： Lokshtanov, Daniel Panolan, Fahad Ramanujan, M. S. Saurabh, Saket Univ Bergen Dept Informat Bergen Norway TU Wien Algorithms & Complex Grp Vienna Austria Inst Math Sci Madras Tamil Nadu India

ISBN: (纸本)9781450345286

In this paper we propose a new framework for analyzing the performance of pre-processing algorithms. Our framework builds on the notion of kernelization from parameterized complexity. However, as opposed to the original notion of kernelization, our definitions combine well with approximation algorithms and heuristics. The key new definition is that of a polynomial size alpha-approximate kernel. Loosely speaking, a polynomial size alpha-approximate kernel is a polynomial time pre-processing algorithm that takes as input an instance (I, k) to a parameterized problem, and outputs another instance (I', k') to the same problem, such that vertical bar I'vertical bar + k' <= k(O(1)). Additionally, for every c >= 1, a c-approximate solution s' to the pre-processed instance (I', k') can be turned in polynomial time into a (c . alpha)-approximate solution s to the original instance (I, k). Amongst our main technical contributions are alpha-approximate kernels of polynomial size for three problems, namely CONNECTED. VERTEX COVER, DISJOINT CYCLE PACKING and DISJOINT FACTORS These problems are known not to admit any polynomial size kernels unless NP subset of coNP/Poly Our approximate kernels simultaneously beat both the lower bounds on the (normal) kernel size, and the hardness of approximation lower bounds for all three problems. On the negative side we prove that LONGEST PATH parameterized by the length of the path and SET COVER parameterized by the universe size do not admit even an alpha-approximate kernel of polynomial size, for any alpha >= 1, unless NP subset of coNP/Poly.

关键词： Kernelization parameterized complexity Inapproximability

来源：评论

学校读者我要写书评

暂无评论

Anyone But Them: The complexity Challenge for A Resolute Election Controller 16

Anyone But Them: The Complexity Challenge for A Resolute Ele...

引用

16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)

作者： Yang, Yongjie Wang, Jianxin Cent S Univ Sch Informat Sci & Engn Changsha Hunan Peoples R China Saarland Univ Chair Econ Theory Saarbrucken Germany

ISBN: (纸本)9781510855076

We study the voting problems where given is an election associated with a subset J of candidates, and the question is whether we can modify the election in a way so that none of the candidates in J wins the election. The modification operations include either adding some votes/candidates or deleting some votes/candidates. These problems are natural generalizations of destructive control problems where J is a singleton and capture many practical situations. We achieve a broad range of complexity results for a number of single-winner voting systems involving voting rules which are compositions of commonly used voting correspondences, such as Borda, Maximin and Copeland(alpha), and three tie-breaking schemes, namely the fixed-order, random candidates and random votes. In particular, we achieve polynomial-time solvability results, NP-hardness results, fixed-parameter tractability results as well as XP results. In addition, we study other tie-breaking schemes and show that the complexity of the problems may depend on tie-breaking schemes.

关键词： destructive control voting systems Borda Maximin Copeland parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

complexity of Token Swapping and its Variants 34

Complexity of Token Swapping and its Variants

引用

34th Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Bonnet, Edouard Miltzow, Tillmann Rzazewski, Pawel Hungarian Acad Sci Inst Comp Sci & Control MTA SZTAKI Budapest Hungary Warsaw Univ Technol Fac Math & Informat Sci Warsaw Poland

ISBN: (纸本)9783959770286

In the TOKEN SWAPPING problem we are given a graph with a token placed on each vertex. Each token has exactly one destination vertex, and we try to move all the tokens to their destinations, using the minimum number of swaps, i.e., operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that TOKEN SWAPPING is W[1]-hard parameterized by the length k of a shortest sequence of swaps. In fact, we prove that, for any computable function f, it cannot be solved in time f(k)n degrees((k/log k)) where n is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial n(O(k))-time algorithm. We also consider two generalizations of the TOKEN SWAPPING, namely COLORED TOKEN SWAPPING (where the tokens have colors and tokens of the same color are indistinguishable), and SUBSET TOKEN SWAPPING (where each token has a set of possible destinations). To complement the hardness result, we prove that even the most general variant, SUBSET TOKEN SWAPPING, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NT-hard cases.

关键词： token swapping parameterized complexity NP-hardness W[1]-hardness

来源：评论

学校读者我要写书评

暂无评论

On the complexity of Borda Control in Single-Peaked Elections 17

On the Complexity of Borda Control in Single-Peaked Election...

引用

16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)

作者： Yang, Yongjie Cent S Univ Sch Informat Sci & Engn Changsha Hunan Peoples R China Saarland Univ Chair Econ Saarbrucken Germany

ISBN: (纸本)9781510855076

Recent research reveals that many NP-hard voting problems in general become polynomial-time solvable in single-peaked elections. In contrast to these results, we prove for the first time that constructive control by adding/deleting votes for Borda are NP-hard even in single-peaked elections. On the other side, we prove that constructive control by adding/deleting votes/candidates for Borda are polynomial-time solvable in single-dived elections, which are elections obtained from single-peaked elections by reversing voters' preferences. Finally, we study constructive control by adding/deleting votes/candidates for Borda in single-peaked elections with k-truncated votes, i.e., each voter ranks only her top-k candidates, aiming at investigating how the values of k affect the complexity of these problems. For this purpose, we adopt the voting correspondences Borda(up arrow) , Borda(down arrow) and Borda(av). We obtain many polynomial-time solvable results for k being a constant.

关键词： Borda control single-peaked parameterized complexity social choice

来源：评论

学校读者我要写书评

暂无评论

The complexity of degree anonymization by graph contractions 12

The complexity of degree anonymization by graph contractions

引用

12th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Talmon, Nimrod Hartung, Sepp Tech Univ Berlin Inst Softwaretech & Theoret Informat D-10587 Berlin Germany

ISBN: (纸本)9783319171418

We study the computational complexity of k-anonymizing a given graph by as few graph contractions as possible. A graph is said to be k-anonymous if for every vertex in it, there are at least k - 1 other vertices with exactly the same degree. The general degree anonymization problem is motivated by applications in privacy-preserving data publishing, and was studied to some extent for various graph operations (most notable operations being edge addition, edge deletion, vertex addition, and vertex deletion). We complement this line of research by studying the computational complexity of degree anonymization by graph contractions. We consider several variants of graph contractions, which are operations of interest, for example, in the contexts of social networks and clustering algorithms. We show that the problem of degree anonymization by graph contractions is NP-hard even for some very restricted inputs, and identify some fixed-parameter tractable cases. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Computational complexity parameterized complexity Fixed-parameter tractability Privacy Data publishing Graph modifications Degree-constrained editing

来源：评论

学校读者我要写书评

暂无评论

Reverse Engineering SPJ-Queries from Examples 17

Reverse Engineering SPJ-Queries from Examples

引用

36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Weiss, Yaacov Y. Cohen, Sara Hebrew Univ Jerusalem Rachel & Selim Benin Sch Comp Sci & Engn Jerusalem Israel

ISBN: (纸本)9781450341981

This paper investigates the problem of reverse engineering, i.e., learning, select-project-join (SPJ) queries from a user-provided example set, containing positive and negative tuples. The goal is then to determine whether there exists a query returning all the positive tuples, but none of the negative tuples, and furthermore, to find such a query, if it exists. These are called the satisfiability and learning problems, respectively. The ability to solve these problems is an important step in simplifying the querying process for non-expert users. This paper thoroughly investigates the satisfiability and learning problems in a variety of settings. In particular, we consider several classes of queries, which allow different combinations of the operators select, project and join. In addition, we compare the complexity of satisfiability and learning, when the query is, or is not, of bounded size. We note that bounded-size queries are of particular interest, as they can be used to avoid over-fitting (i.e., tailoring a query precisely to only the seen examples). In order to fully understand the underlying factors which make satisfiability and learning (in)tractable, we consider different components of the problem, namely, the size of a query to be learned, the size of the schema and the number of examples. We study the complexity of our problems, when considering these as part of the input, as constants or as parameters (i.e., as in parameterized complexity analysis). Depending on the setting, the complexity of satisfiability and learning can vary significantly. Among other results, our analysis also provides new problems that are complete for W[3], for which few natural problems are known. Finally, by considering a variety of settings, we derive insight on how the different facets of our problem interplay with the size of the database, thereby providing the theoretical foundations necessary for a future implementation of query learning from examples.

关键词： parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：