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

3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS 2015年第2期7卷

作者： Kanj, Iyad Zhang, Fenghui Depaul Univ Sch Comp 243 S Wabash Ave Chicago IL 60604 USA Google Kirkland Kirkland WA 98033 USA

We study upper and lower bounds on the vertex-kernel size for the 3-hitting set problem on hypergraphs of degree at most 3, denoted 3-3-hs. We first show that, unless P = NP, 3-3-hs on 3-uniform hypergraphs does not have a vertex-kernel of size at most 35k/19 > 1.8421k. We then give a 4k - k(0.2692) vertex-kernel for 3-3-hs that is computable in time O(k(2)). We do not assume that the hypergraph is 3-uniform for the vertex-kernel upper bound results. This result improves the upper bound of 4k on the vertex-kernel size for 3-3-hs, implied by the results of Wahlstrom.

关键词： Hitting set kernel upper bounds lower bounds parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Large-Scale Election Campaigns: Combinatorial Shift Bribery 14

Large-Scale Election Campaigns: Combinatorial Shift Bribery

引用

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

作者： Bredereck, Robert Faliszewski, Piotr Niedermeier, Rolf Talmon, Nimrod TU Berlin Berlin Germany AGH Univ Sci & Technol Krakow Poland

ISBN: (纸本)9781450334136

We study the complexity of a combinatorial variant of the Shift Bribery problem in elections. In the standard Shift Bribery problem, we are given an election where each voter has a preference order over the candidate set and where an outside agent, the briber, can pay each voter to rank the briber's favorite candidate a given number of positions higher. The goal is to ensure the victory of the briber's preferred candidate. The combinatorial variant of the problem, introduced in this paper, models settings where it is possible to affect the position of the preferred candidate in multiple votes, either positively or negatively, with a single bribery action. This variant of the problem is particularly interesting in the context of large-scale campaign management problems (which, from the technical side, are modeled as bribery problems). We show that, in general, the combinatorial variant of the problem is highly intractable (NP-hard, hard in the parameterized sense, and hard to approximate), but we provide some (approximation) algorithms for natural restricted cases.

关键词： campaign management preference aggregation voting computational complexity parameterized complexity fixed-parameter tractability approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Kernelization complexity of Possible Winner and Coalitional Manipulation Problems in Voting 14

Kernelization Complexity of Possible Winner and Coalitional ...

引用

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

作者： Dey, Palash Misra, Neeldhara Narahari, Y. Indian Inst Sci Dept Comp Sci & Automat Bangalore Karnataka India

ISBN: (纸本)9781450334136

In the POSSIBLE WINNERproblem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences to linear preferences. Previous work has provided, for many common voting rules, fixed parameter tractable algorithms for the POSSIBLE WINNERproblem, with number of candidates as the parameter. However, the corresponding kernelization question is still open and in fact, has been mentioned as a key research challenge [ 10]. In this paper, we settle this open question for many common voting rules. We show that the POSSIBLE WINNERproblem for maximin, Copeland, Bucklin, ranked pairs, and a class of scoring rules that include the Borda voting rule do not admit a polynomial kernel with the number of candidates as the parameter. We show however that the Coalitional Manipulation problem which is an important special case of the POSSIBLE WINNERproblem does admit a polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring rules that includes the Borda voting rule, when the number of manipulators is polynomial in the number of candidates. A significant conclusion of our work is that the POSSIBLE WINNERproblem is harder than the Coalitional Manipulation problem since the Coalitional Manipulation problem admits a polynomial kernel whereas the POSSIBLE WINNERproblem does not admit a polynomial kernel.

关键词： Computational social choice possible winner voting kernelization parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the complexity of finding a largest common subtree of bounded degree

On the complexity of finding a largest common subtree of bou...

引用

19th International Symposium on Fundamentals of Computation Theory

作者： Akutsu, Tatsuya Tamura, Takeyuki Melkman, Avraham A. Takasu, Atsuhiro Kyoto Univ Inst Chem Res Bioinformat Ctr Uji Kyoto 6110011 Japan Ben Gurion Univ Negev IL-84105 Beer Sheva Israel Natl Inst Informat Tokyo 1018430 Japan

ISBN: (纸本)9783642401633

The largest common subtree problem is to find a bijective mapping between subsets of nodes of two input rooted trees of maximum cardinality or weight that preserves labels and ancestry relationship. The problem is known to be NP-hard for unordered trees. In this paper, we consider a restricted unordered case in which the maximum outdegree of a common subtree is bounded by a constant D. We present an O(n(D)) time algorithm where n is the maximum size of two input trees, which improves a previous O(n(2D)) time algorithm. We also present an O((H-2 center dot 2(2H-1)center dot D-2H)(D-1) poly(n)) time algorithm, where H is the maximum height of two input trees. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Tree edit distance Unordered trees Dynamic programming parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

A Parametric Polynomial Deterministic Algorithm for #2SAT 14th

A Parametric Polynomial Deterministic Algorithm for #2SAT

引用

14th Mexican International Conference on Artificial Intelligence (MICAI)

作者： Raymundo Marcial-Romero, J. De Ita Luna, Guillermo Antonio Hernandez, J. Maria Valdovinos, Rosa UAEM Fac Ingn Toluca Mexico Benemerita Univ Autonoma Puebla FCC Puebla Mexico

ISBN: (纸本)9783319270609;9783319270593

Counting models for two Conjunctive Normal Form formulae (2-CFs), known as the #2SAT problem, is a classic #P complete problem. It is known that if the constraint graph of a 2-CF F is acyclic or contains loops and parallel edges, #2SAT(F) can be computed efficiently. In this paper we address the cyclic case different from loops and parallel edges. If the constraint graph G of a 2-CF F is cyclic, T a spanning tree plus loops and parallel edges of G and (T) over bar = G \ T, what we called its cotree, we show that by building a set partition boolean OR T-i of (T) over bar, where each T-i of the partition is formed by the frond edges of the cycles that are chained via other intersected cycles, then a parametric polynomial deterministic procedure for computing # 2SAT with time complexity for the worst case of O(2(k) . poly(|E(T)|)) can be obtained, where poly is a polynomial function, and k is the cardinality of the largest set in the partition. This method shows that # 2SAT is in the class of fixed-parameter tratable (FPT) problems, where the fixed-parameter k in our proposal, depends on the number of edges of a subcotree of a decomposition of the constraint graph (tree+ loops+ parallel: cotree) associated to the formula.

关键词： #SAT problem Counting models in 2-CF formulae parameterized complexity FPT complexity class

来源：评论

学校读者我要写书评

暂无评论

parameterized approaches for large-scale optimization problems

Parameterized approaches for large-scale optimization proble...

引用

作者： Buchanan, Austin Loyd Texas A&M University

学位级别：Ph.D.

In this dissertation, we study challenging discrete optimization problems from the perspective of parameterized complexity. The usefulness of this type of analysis is twofold. First, it can lead to efficient algorithms for large-scale problem instances. Second, the analysis can provide a rigorous explanation for why challenging problems might appear relatively easy in practice. We illustrate the approach on several different problems, including: the maximum clique problem in sparse graphs; 0-1 programs with many conflicts; and the node-weighted Steiner tree problem with few terminal nodes. We also study polyhedral counterparts to fixed-parameter tractable algorithms. Specifically, we provide fixed-parameter tractable extended formulations for independent set in tree-like graphs and for cardinality-constrained vertex covers.

关键词： parameterized complexity integer programming extended formulations fixed-parameter tractable combinatorial optimization Steiner tree node-weighted Steiner tree maximum-weight connected subgraph vertex cover independent set maximum clique degene

来源：评论

学校读者我要写书评

暂无评论

Tight Hardness Results for LCS and other Sequence Similarity Measures 56

Tight Hardness Results for LCS and other Sequence Similarity...

引用

56th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Abboud, Amir Backurs, Arturs Williams, Virginia Vassilevska Stanford Univ Dept Comp Sci Palo Alto CA USA MIT EECS Cambridge MA USA

ISBN: (纸本)9781467381918

Two important similarity measures between sequences are the longest common subsequence (LCS) and the dynamic time warping distance (DTWD). The computations of these measures for two given sequences are central tasks in a variety of applications. Simple dynamic programming algorithms solve these tasks in O(n(2)) time, and despite an extensive amount of research, no algorithms with significantly better worst case upper bounds are known. In this paper, we show that for any constant epsilon > 0, an O(n(2-epsilon)) time algorithm for computing the LCS or the DTWD of two sequences of length n over a constant size alphabet, refutes the popular Strong Exponential Time Hypothesis (SETH).

关键词： SETH lower bounds sequence alignments parameterized complexity LCS DTWD

来源：评论

学校读者我要写书评

暂无评论

A Completeness Theory for Polynomial (Turing) Kernelization

A Completeness Theory for Polynomial (Turing) Kernelization

引用

8th International Symposium on parameterized and Exact Computation (IPEC) as part of the annual ALGO Meeting

作者： Hermelin, Danny Kratsch, Stefan Soltys, Karolina Wahlstroem, Magnus Wu, Xi Ben Gurion Univ Negev Beer Sheva Israel Tech Univ Berlin Berlin Germany Max Planck Inst Informat D-66123 Saarbrucken Germany Univ London Egham Surrey England Univ Wisconsin Madison WI USA

ISBN: (纸本)9783319038971

The framework of Bodlaender et al. (J Comput Sys Sci 75(8):423-434, 2009) and Fortnow and Santhanam (J Comput Sys Sci 77(1):91-106, 2011) allows us to exclude the existence of polynomial kernels for a range of problems under reasonable complexity-theoretical assumptions. However, some issues are not addressed by this framework, including the existence of Turing kernels such as the "kernelization" of leaf out-branching that outputs instances each of size poly. Observing that Turing kernels are preserved by polynomial parametric transformations (PPTs), we define two kernelization hardness hierarchies by the PPT-closure of problems that seem fundamentally unlikely to admit efficient Turing kernelizations. This gives rise to the MK- and WK-hierarchies which are akin to the M- and W-hierarchies of parameterized complexity. We find that several previously considered problems are complete for the fundamental hardness class WK[1], including Min Ones -SAT , Binary NDTM Halting , Connected Vertex Cover , and Clique parameterized by . We conjecture that no WK[1]-hard problem admits a polynomial Turing kernel. Our hierarchy subsumes an earlier hierarchy of Harnik and Naor that, from a parameterized perspective, is restricted to classical problems parameterized by witness size. Our results provide the first natural complete problems for, e.g., their class;this had been left open.

关键词： parameterized complexity Kernelization Turing kernelization complexity hierarchies

来源：评论

学校读者我要写书评

暂无评论

Backdoors to Normality for Disjunctive Logic Programs

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2015年第1期17卷 7-7页

作者： Fichte, Johannes K. Szeider, Stefan Vienna Univ Technol A-1040 Vienna Austria Univ Potsdam Inst Comp Sci D-14482 Potsdam Germany Vienna Univ Technol A-1040 Vienna Austria

The main reasoning problems for disjunctive logic programs are complete for the second level of the polynomial hierarchy and hence considered harder than the same problems for normal (i.e., disjunction-free) programs, which are on the first level. We propose a new exact method for solving the disjunctive problems which exploits the small distance of a disjunctive programs from being normal. The distance is measured in terms of the size of a smallest "backdoor to normality," which is the smallest number of atoms whose deletion makes the program normal. Our method consists of three phases. In the first phase, a smallest backdoor is computed. We show that this can be done using an efficient algorithm for computing a smallest vertex cover of a graph. In the second phase, the backdoor is used to transform the logic program into a quantified Boolean formula (QBF) where the number of universally quantified variables equals the size of the backdoor and where the total size of the quantified Boolean formula is quasilinear in the size of the given logic program. The quasilinearity is achieved by means of a characterization of the least model of a Horn program in terms of level numberings. In a third phase, the universal variables are eliminated using universal expansion yielding a propositional formula. The blowup in the last phase is confined to a factor that is exponential in the size of the backdoor but linear in the size of the quantified Boolean formula. By checking the satisfiability of the resulting formula with a SAT solver (or by checking the satisfiability of the quantified Boolean formula by a QBF-SAT solver), we can decide the ASP reasoning problems on the input program. In consequence, we have a transformation from ASP problems to propositional satisfiability where the combinatorial explosion, which is expected when transforming a problem from the second level of the polynomial hierarchy to the first level, is confined to a function of the distance to normality o

关键词： Theory parameterized complexity backdoors answer set programming quantified Boolean formulas propositional satisfiability

来源：评论

学校读者我要写书评

暂无评论

Tight complexity bounds for FPT subgraph problems parameterized by the clique-width

引用

THEORETICAL COMPUTER SCIENCE 2013年 485卷 69-84页

作者： Broersma, Hajo Golovach, Petr A. Patel, Viresh Univ Twente Fac EEMCS NL-7500 AE Enschede Netherlands Univ Bergen Dept Informat N-5020 Bergen Norway Univ Birmingham Sch Math Birmingham B15 2TT W Midlands England

We give tight algorithmic lower and upper bounds for some double-parameterized subgraph problems when the clique-width of the input graph is one of the parameters. Let G be an arbitrary input graph on n vertices with clique-width at most w. We prove the following results. The DENSE (SPARSE) k-SUBGRAPH problem, which asks whether there exists an induced subgraph of G with k vertices and at least q edges (at most q edges, respectively), can be solved in time k(O(w)) . n, but it cannot be solved in time 2(0(w log k)) . n(0(1)) unless the Exponential Time Hypothesis (ETH) fails. The d-REGULAR INDUCED SUBGRAPH problem, which asks whether there exists a d-regular induced subgraph of G, and the MINIMUM SUBGRAPH OF MINIMUM DEGREE AT LEAST d problem, which asks whether there exists a subgraph of G with k vertices and minimum degree at least d, can be solved in time d(0(w)) . n, but they cannot be solved in time 2(0(w log d)) . n(0(1)) unless ETH fails. (C) 2013 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Clique-width Exponential Time Hypothesis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：