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

parameterized and approximation complexity of PARTIAL VC DIMENSION

THEORETICAL COMPUTER SCIENCE 2019年 766卷 1-15页

作者： Bazgan, Cristina Foucaud, Florent Sikora, Florian Univ Paris 09 PSL Univ CNRS LAMSADE F-75016 Paris France Univ Clermont Auvergne CNRS LIMOS Aubiere France Inst Univ France Tremblay En France France

We introduce the problem PARTIAL VC DIMENSION that asks, given a hypergraph H = (X, E) and integers k and l. whether one can select a set C subset of X of k vertices of H such that the set {e boolean AND C, e is an element of E) of distinct hyperedge-intersections with C has size at least l. The sets e boolean AND C define equivalence classes over E. PARTIAL VC DIMENSION is a generalization of VC DIMENSION, which corresponds to the case l = 2(k), and Of DISTINGUISHING TRANSVERSAL, which corresponds to the case l = vertical bar E vertical bar (the latter is also known as TEST COVER in the dual hypergraph). We also introduce the associated fixed-cardinality maximization problem MAX PARTIAL VC DIMENSION that aims at maximizing the number of equivalence classes induced by a solution set of k vertices. We study the algorithmic complexity of PARTIAL VC DIMENSION and MAX PARTIAL VC DIMENSION both on general hypergraphs and on more restricted instances, in particular, neighborhood hypergraphs of graphs. (C) 2018 Elsevier B.V. All rights reserved.

关键词： VC dimension Distinguishing Transversal Partial problems Hypergraphs parameterized complexity Approximation complexity

来源：评论

学校读者我要写书评

暂无评论

Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and parameterized complexity 27

Degree-Constrained Orientation of Maximum Satisfaction: Grap...

引用

27th Annual International Symposium on Algorithms and Computation (ISAAC)

作者： Bodlaender, Hans L. Ono, Hirotaka Otachi, Yota Univ Utrecht Dept Informat & Comp Sci POB 80-089 NL-3508 TB Utrecht Netherlands Univ Technol Eindhoven Dept Math & Comp Sci POB 513 NL-5600 MB Eindhoven Netherlands Nagoya Univ Grad Sch Informat Chikusa Ku Furo Cho Nagoya Aichi 4648601 Japan Kumamoto Univ Fac Adv Sci & Technol Chuo Ku 2-39-1 Kurokami Kumamoto 8608555 Japan

ISBN: (纸本)9783959770262

The problem MAX W-LIGHT (MAX W-HEAVY) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at most W (resp. at least W) is maximized. It is known that these problems are NP-hard even for fixed W. For example, MAX 0- LIGHT is equivalent to the problem of finding a maximum independent set. In this paper, we show that for any fixed constant W, MAX W-HEAVY can be solved in linear time for hereditary graph classes for which treewidth is bounded by a function of degeneracy. We show that such graph classes include chordal graphs, circular-arc graphs, d-trapezoid graphs, chordal bipartite graphs, and graphs of bounded clique-width. To have a polynomial-time algorithm for MAX W-LIGHT, we need an additional condition of a polynomial upper bound on the number of potential maximal cliques to apply the metatheorem by Fomin et al. (SIAM J Comput 44:54-87, 2015). The aforementioned graph classes, except bounded clique-width graphs, satisfy such a condition. For graphs of bounded clique-width, we present a dynamic programming approach not using the metatheorem to show that it is actually polynomial-time solvable for this graph class too. We also study the parameterized complexity of the problems and show some tractability and intractability results.

关键词： Orientation Graph class Width parameter parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2018年第7期29卷 1215-1230页

作者： Roayaei, Mehdy Razzazi, MohammadReza Tarbiat Modares Univ Dept Elect & Comp Engn Tehran Iran Amirkabir Univ Technol Dept Comp Engn & Informat Technol Tehran Iran

We consider the directed Steiner network problem, where given a weighted directed graph G and p pairs of vertices P = {(s(1), t(1)), . . . ,(s(p), t(p))}, one has to find the minimum weight subgraph H of G that contains path from s(i) to t(i) for all i. We search for the main cause of the complexity of the problem and introduce the notions of junction vertex and shared segment in an optimal solution. We study the parameterized complexity of the problem with respect to these parameters and achieve several parameterized hardness results. Also, we present two output-sensitive algorithms for the problem, which are much simpler and easier to implement than the previously best known one;and in addition, when the paths corresponding to the input pairs have few shared vertices or arcs in the optimal solution, these algorithms outperform the previous one.

关键词： Directed Steiner network output-sensitive algorithm junction vertex shared segment parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Multi-winner Determination: More Effort Towards Fixed-Parameter Tractability 18

Parameterized Complexity of Multi-winner Determination: More...

引用

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

作者： Yongjie Yang Jianxin Wang Saarland University & Central South University Saarbrücken Germany Central South University Changsha China

We study the k -committee selection rules minimax approval, proportional approval, and Chamberlin-Courant's approval. It is known that WINNER DETERMINATION for these rules is NP-hard. Moreover, the parameterized complexity of the problem has also been studied with respect to some natural parameters. However, there are still numerous parameterizations that have not been considered. We revisit the parameterized complexity of WINNER DETERMINATION for these rules by considering several important single parameters, combined parameters, and structural parameters, aiming at detecting as many fixed-parameter tractability results as possible.

关键词： parameterized complexity tree-width approval voting maximum matching multi-winner voting

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Group Activity Selection 16

Parameterized Complexity of Group Activity Selection

引用

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

作者： Lee, Hooyeon Williams, Virginia Vassilevska Moloco Inc Palo Alto CA 94301 USA MIT Cambridge MA 02139 USA

ISBN: (纸本)9781510855076

We consider the Group Activity Selection Problem (GASP) in which a group of agents need to be assigned to activities, subject to agent preferences and stability conditions. In GASP, the agents announce dichotomic preferences on which (activity, number-of-participant) pairs are acceptable to them. We consider five solution concepts of assignments: (1) individual rationality (everyone who is assigned to an activity is willing to participate), (2) (Nash) stability (no agent wants to deviate from the assignment), (3) envy-freeness (no agent is envious of someone else's assignment), (4) stability and envy-freeness, and (5) perfection (everyone is assigned and willing to participate). It is known that finding an assignment of a given size with any of these properties is NP-complete. We study the complexity of GASP on a finer scale, through the lens of parameterized complexity. We show that the solution concepts above differ substantially, when parameterized by the size of the solution (the number of assigned agents or the number of used activities). In particular, finding an individually rational assignment is fixed parameter tractable, yet other solutions concepts are less tractable (W[1]- and W[2]-hard) even under very natural restrictions on inputs.

关键词： parameterized complexity Fixed parameter tractability W-hierarchy Individual rationality Stability Envy-free

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity and Approximability of Coverability Problems in Weighted Petri Nets 38th

Parameterized Complexity and Approximability of Coverability...

引用

38th International Conference on Application and Theory of Petri Nets and Concurrency (Petri Nets)

作者： Watel, Dimitri Weisser, Marc-Antoine Barth, Dominique ENSIIE Evry France SAMOVAR Evry France Univ Paris Saclay CentraleSupelec LRI Orsay France Univ Versailles St Quentin En Yvelines DAVID Versailles France

ISBN: (纸本)9783319578613;9783319578606

Many databases have been filled with the chemical reactions found in scientific publications and the associated information (efficiency, chemical products involved...). They can be used to define functions representing costs such as the ecoligical impact of the reactions. A major challenge is to use computer driven optimization in order to improve synthesis process and to provide algorithms to help determining a minimum cost pathway (series of reactions) for the synthesis of a molecule. As, the classical Petri nets do not allows us to consider the optimization component, a weighted model has to be defined and the complexity of the associated problems studied. In this paper we introduce the weighted Petri nets in which each transition is associated with a weight. We define the Minimum Weight Synthesis Problem: find a minimum weight series of transitions to fire to produce a given target component. It mainly differ from classical coverability as it is an optimization problem. We prove that this problem is EXPSPACE-Complete and that there is no polynomial approximation even when both in and outdegree are fixed to two and the target state is a single component. We also consider a more constraint version of the problem limiting the number of fired transitions. We prove this problem falls into PSPACE and the parametrized versions into XP but it remains not approximable.

关键词： Petri net coverability problem Minimum weight synthesis problem parameterized complexity Approximability

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Decision Problems in Non-Classical Logics

Parameterized Complexity of Decision Problems in Non-Classic...

引用

作者： Irena Schindler Gottfried Wilhelm Leibniz Universitat Hannover

学位级别：博士

parameterized complexity is a branch of a computational complexity. The pioneers of this new and promising research field are Downey and Fellows [ DF99 ]. They suggest to examine the structural properties of a given problem and restrict the instance by a parameter. In this thesis we investigate the parameterized complexity of various problems in default logic and in temporal logics. In the first section of Chapter 3 we introduce a dynamic programming algorithm which decides whether a given default theory has a consistent stable extension in fpt-time and enumerates all generating defaults that lead to a stable extension with a pre-computation step that is linear in the input theory and triple exponential in the tree-width followed by a linear delay to output solutions. In the second part of this chapter we lift the notion of backdoors to the field of default logics. We consider two problems, first we are interested to detect a backdoor and then to evaluate it for the target formulae classes HORN, KROM, POSITIVE-UNIT and MONOTONE. In Chapter 4, we investigate the parameterized complexity of problems in various tem- poral logics. In the first section we introduce several graph-like structures for formula representation and the corresponding notion of tree-width and path-width. To obtain the fixed parameter tractability of different fragments, we generalize the prominent Courcelle's Theorem to work for infinite signatures. In this section, we also consider Boolean operator fragments in the sense of Post's lattice. In the second part of Chapter 4 we introduce the notion of backdoors for the glob- ally fragment of linear temporal logic. Again, our problems of interest are to detect a backdoor and to evaluate it, this time, for the target formulae classes HORN and KROM.

关键词： parameterized complexity default logic temporal logic backdoor Post's Lattice tree-and pathwidth temporal depth

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Resilience Decision for Database Debugging 19th

Parameterized Complexity of Resilience Decision for Database...

引用

19th International Conference on Formal Engineering Methods (ICFEM)

作者： Miao, Dongjing Cai, Zhipeng Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA Harbin Engn Univ Coll Comp Sci & Technol Harbin 150001 Heilongjiang Peoples R China

ISBN: (纸本)9783319686905;9783319686899

Resilience decision problem plays a fundamental and important role in database debugging, query explanation and error tracing. Resilience decision problem is defined on a database d, given a boolean query q which is true initially, and a constant k > 0, it is to decide if there is a fact set res of size no more than k such that query q becomes false after deleting all facts in res. Previous results showed it is NP-hard in many cases. However, we revisit this decision problem, in the light of the recent parametric refinement of complexity theory, provide some new results including negative and positive ones. We show that, there are still some cases intractable if only consider the query size or variable numbers as the parameter.

关键词： Resilience Database parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Incremental Problems in the parameterized complexity Setting

引用

THEORY OF COMPUTING SYSTEMS 2017年第1期60卷 3-19页

作者： Mans, Bernard Mathieson, Luke Macquarie Univ Dept Comp Sydney NSW 2109 Australia

Dynamic systems are becoming steadily more important with the profusion of mobile and distributed computing devices. Coincidentally incremental computation is a natural approach to deal with ongoing changes. We explore incremental computation in the parameterized complexity setting and show that incrementalization leads to non-trivial complexity classifications. Interestingly, some incremental versions of hard problems become tractable, while others remain hard. Moreover tractability or intractability is not a simple function of the problem's static complexity, every level of the W-hierarchy exhibits complete problems with both tractable and intractable incrementalizations. For problems that are already tractable in their static form, we also show that incrementalization can lead to interesting algorithms, improving upon the trivial approach of using the static algorithm at each step.

关键词： Algorithm complexity Incremental computation Kernelization parameterized complexity Tractability

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of Reconfiguration Problems

引用

ALGORITHMICA 2017年第1期78卷 274-297页

作者： Mouawad, Amer E. Nishimura, Naomi Raman, Venkatesh Simjour, Narges Suzuki, Akira Univ Bergen Dept Informat Bergen Norway Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON Canada Inst Math Sci Madras Tamil Nadu India Google Waterloo 151 Charles St WestSuite 200 Kitchener ON N2G 1H6 Canada Tohoku Univ Grad Sch Informat Sci Sendai Miyagi Japan CREST JST Saitama Japan

We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration variant of an optimization problem Q takes as input two feasible solutions S and T and determines if there is a sequence of reconfiguration steps, i.e. a reconfiguration sequence, that can be applied to transform S into T such that each step results in a feasible solution to Q. For most of the results in this paper, S and T are sets of vertices of a given graph and a reconfiguration step adds or removes a vertex. Our study is motivated by results establishing that for many NP-hard problems, the classical complexity of reconfiguration is PSPACE-complete. We address the question for several important graph properties under two natural parameterizations: k, a bound on the size of solutions, and l, a bound on the length of reconfiguration sequences. Our first general result is an algorithmic paradigm, the reconfiguration kernel, used to obtain fixed-parameter tractable algorithms for reconfiguration variants of Vertex Cover and, more generally, Bounded Hitting Set and Feedback Vertex Set, all parameterized by k. In contrast, we show that reconfiguring Unbounded Hitting Set is W[2]-hard when parameterized by k + l. We also demonstrate the W[1]-hardness of reconfiguration variants of a large class of maximization problems parameterized by k + l, and of their corresponding deletion problems parameterized by l;in doing so, we show that there exist problems in FPT when parameterized by k, but whose reconfiguration variants are W[1]-hard when parameterized by k + l.

关键词： Reconfiguration parameterized complexity Solution space Vertex cover Hitting set

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：