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

A parameterized view on the complexity of dependence and independence logic

JOURNAL OF LOGIC AND COMPUTATION 2022年第8期32卷 1624-1644页

作者： Kontinen, Juha Meier, Arne Mahmood, Yasir Univ Helsinki Dept Math & Stat PL 68 Helsinki 00014 Finland Leibniz Univ Hannover Inst Theoret Informat D-30167 Hannover Germany

In this paper, we investigate the parameterized complexity of model checking for Dependence and Independence logic, which are well studied logics in the area of Team Semantics. We start with a list of nine immediate parameterizations for this problem, namely the number of disjunctions (i.e. splits)/(free) variables/universal quantifiers, formula-size, the tree-width of the Gaifman graph of the input structure, the size of the universe/team and the arity of dependence atoms. We present a comprehensive picture of the parameterized complexity of model checking and obtain a division of the problem into tractable and various intractable degrees. Furthermore, we also consider the complexity of the most important variants (data and expression complexity) of the model checking problem by fixing parts of the input.

关键词： Team semantics dependence logic independence logic parameterized complexity model checking

来源：评论

学校读者我要写书评

暂无评论

Graph Modification for Edge-Coloured and Signed Graph Homomorphism Problems: parameterized and Classical complexity

引用

ALGORITHMICA 2022年第5期84卷 1183-1212页

作者： Foucaud, Florent Hocquard, Herve Lajou, Dimitri Mitsou, Valia Pierron, Theo Univ Clermont Auvergne CNRS Mines St Etienne Clermont Auvergne INP F-63000 Clermont Ferrand France Univ Bordeaux CNRS Bordeaux INP LaBRIUMR5800 F-33400 Bordeaux France Univ Orleans INSA Ctr Val Loire LIFO EA 4022 F-45067 Orleans 2 France Univ Paris CNRS IRIF F-75205 Paris France Univ Lyon Univ Claude Bernard CNRS LIRISUMR 5205 F-69621 Lyon France Masaryk Univ Fac Informat Bot 68A Brno 60200 Czech Republic

We study the complexity of graph modification problems with respect to homomorphism-based colouring properties of edge-coloured graphs. A homomorphism from an edge-coloured graph G to an edge-coloured graph H is a vertex-mapping from G to H that preserves adjacencies and edge-colours. We consider the property of having a homomorphism to a fixed edge-coloured graph H, which generalises the classic vertex-colourability property. The question we are interested in is the following: given an edge-coloured graph G, can we perform k graph operations so that the resulting graph admits a homomorphism to H? The operations we consider are vertex-deletion, edge-deletion and switching (an operation that permutes the colours of the edges incident to a given vertex). Switching plays an important role in the theory of signed graphs, that are 2-edge-coloured graphs whose colours are the signs + and -. We denote the corresponding problems (parameterized by k) by VD-H- COLOURING, ED-H-COLOURING and SW-H-COLOURING. These problems generalise the extensively studied H-COLOURING problem (where one has to decide if an input graph admits a homomorphism to a fixed target H). For 2-edge-coloured H, it is known that H-COLOURING already captures the complexity of all fixed-target Constraint Satisfaction Problems. Our main focus is on the case where H is an edge-coloured graph with at most two vertices, a case that is already interesting since it includes standard problems such as VERTEX COVER, ODD CYCLE TRANSVERSAL and EDGE BIPARTIZATION. For such a graph H, we give a P/NP-complete complexity dichotomy for all three VD-H-COLOURING, ED-H-COLOURING and SW-H-COLOURING problems. Then, we address their parameterized complexity. We show that all VD-H-COLOURING and ED-H-COLOURING problems for such H are FPT. This is in contrast with the fact that already for some H of order 3, unless P = NP, none of the three considered problems is in XP, since 3- COLOURING is NP-complete. We show that the situation i

关键词： parameterized complexity Graph homomorphism Graph modification Edge-coloured graph Signed graph

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithms and complexity for the traveling purchaser problem and its variants

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第4期44卷 2269-2285页

作者： Xiao, Mingyu Zhang, Jianan Lin, Weibo Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China Huawei Technol Co Ltd Hangzhou Zhejiang Peoples R China

The traveling purchaser problem (TPP), a generalization of the traveling salesman problem, is to determine a tour of suppliers and purchase needed products from suppliers while minimizing the traveling and purchasing cost. This problem finds applications in the routing and scheduling contexts and its variants with different constraints have been widely studied. Motivated by the phenomenon that most real-world instances of TPP have a small parameter (such as the number of suppliers, the number of products to purchase, and others), we study TPP and its variants from the view of parameterized complexity. We show that TPP and some variants are fixed-parameter tractable by taking the numberkof products or the numbermof suppliers as the parameter, and W[2]-hard by taking the numberqof visited suppliers as the parameter. Furthermore, we implement some of our fixed-parameter tractable algorithms to show that they are practically effective when the parameters are not very large.

关键词： Traveling purchaser problem Fixed-parameter tractable Dynamic programming parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of d-Restricted Boolean Net Synthesis 16th

On the Parameterized Complexity of d-Restricted Boolean Net ...

引用

16th International Conference on Theory and Applications of Models of Computation (TAMC)

作者： Tredup, Ronny Erofeev, Evgeny Univ Rostock Inst Informat Theoret Informat Albert Einstein Str 22 D-18059 Rostock Germany Carl von Ossietzky Univ Oldenburg Dept Comp Sci D-26111 Oldenburg Germany

In this paper, we investigate the parameterized complexity of d-restricted tau-synthesis (dR tau S) parameterized by d for a range of Boolean types of nets tau. We show that dR tau S is W[1]-hard for 64 of 128 possibl... 详细信息

ISBN: (纸本)9783030592660;9783030592677

关键词： Synthesis parameterized complexity Boolean Petri net

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Committee Elections with Dichotomous and Trichotomous Votes 18

Parameterized Complexity of Committee Elections with Dichoto...

引用

18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS)

作者： Zhou, Aizhong Yang, Yongjie Guo, Jiong Shandong Univ Sch Comp Sci & Technol Jinan Shandong Peoples R China Cent South Univ Changsha Hunan Peoples R China

ISBN: (纸本)9781450363099

We study the winner determination problem for three prevalent committee election rules: Chamberlin-Courant Approval Voting (CCA), Proportional Approval Voting (PAV), and Satisfaction Approval Voting (SAV). Axiomatic and algorithmic studies of elections under these rules have been conducted recently. It is known that the winner determination problem is NP-hard for CCA and PAV and polynomial-time solvable for SAV, if the input votes are dichotomous. Moreover, parameterized complexity of the two NP-hard cases has been examined with respect to some natural parameters such as the number of candidates or the number of votes. In this paper, we extend the above studies to committee elections with trichotomous votes and identify cases, where trichotomous votes lead to an increase of parameterized complexity. We also consider the maximin (or egalitarian) variations of the rules, where the minimum satisfaction of the voters is maximized.

关键词： Committee elections parameterized complexity maximin

来源：评论

学校读者我要写书评

暂无评论

On parameterized complexity of the Word Search Problem in the Baumslag-Gersten Group 20

On Parameterized Complexity of the Word Search Problem in th...

引用

45th International Symposium on Symbolic and Algebraic Computation

作者： Miasnikov, Alexei Nikolaev, Andrey Stevens Inst Technol Hoboken NJ 07030 USA

ISBN: (纸本)9781450371001

We consider the word search problem in the BaumslagsGersten group GB. We show that the parameterized complexity of this problem, where the area of van Kampen diagram serves as a parameter, is polynomial in the length of the input and the parameter. This contrasts the well-known result that the Dehn function and the time complexity of the word search problem in GB are non-elementary.

关键词： parameterized complexity fixed parameter tractability word problem word search problem Baumslag-Solitar group Baumslags Gersten group Dehn function

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Shift Bribery in Iterative Elections 20

Parameterized Complexity of Shift Bribery in Iterative Elect...

引用

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

作者： Aizhong Zhou Jiong Guo Shandong University Qingdao China

ISBN: (纸本)9781450375184

In an iterative voting system, candidates are eliminated in consecutive rounds until either the set of remaining candidates does not change or a fixed number of rounds is reached. In this paper, we consider four prominent iterative voting systems, which are all based on positional scoring rules. The Hare and Coombs systems are based on the plurality and veto rules, respectively, while the Baldwin and Nanson systems are based on the Borda rule. We study the resistance of these four systems against shift bribery. Hereby, we consider both constructive and destructive settings. It is known that all four iterative voting systems are resistant to shift bribery, that is, both constructive and destructive shift bribery problems are NP-hard for these voting systems. We complement these NP-hardness results by examining parameterized complexity of the shift bribery problems with respect to some natural parameters. Our results provide further evidence for the observation that shift bribery problems for iterative voting systems are computationally harder than for the corresponding non-iterative cases. In addition, our reductions apply several techniques which might be useful for proving hardness results for other iterative voting systems.

关键词： iterative elections shift bribery parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity landscape of finding 2-partitions of digraphs

引用

THEORETICAL COMPUTER SCIENCE 2019年 795卷 108-114页

作者： Bang-Jensen, J. Knudsen, Kristine V. K. Saurabh, Saket Zehavi, Meirav Univ Southern Denmark Dept Math & Comp Sci Odense Denmark Univ Bergen Dept Informat Bergen Norway HBNI Inst Math Sci Chennai Tamil Nadu India UMI ReLax Bangalore Karnataka India Ben Gurion Univ Negev Beer Sheva Israel

Given a network modeled by a directed graph D = (V, A), it is natural to ask whether we can partition the vertex set of D into two disjoint subsets V-1, V-2 (called a 2-partition), such that the digraphs D[V-1], D[V-2] induced by each of these has one of the two properties of interest. This question gives rise to a rich realm of combinatorial problems. The complexity of many such problems was determined in [2,3]. We analyze a subset of those problems from the viewpoint of parameterized complexity, and present a complete dichotomy of basic, natural properties. More precisely, given a directed graph D = (V, A) and two non-negative integers k(1) and k(2), we seek a 2-partition (V-1, V-2) of the vertex set V such that vertical bar V-1 vertical bar >= k(1), vertical bar V-2 vertical bar >= k(2), and each of the subdigraphs induced by V-1 and V-2 has a structural property as defined by the problem at hand-for example, D[V-1] is acyclic and D[V-2] is strongly connected. Specifically, we consider the following eight structural properties: being strongly connected;being connected;having an out-branching;having an in-branching;having minimum degree at least one;having minimum semi-degree at least one;being acyclic;and being complete. (C) 2019 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Directed graphs Digraph partitioning 2-Partition

来源：评论

学校读者我要写书评

暂无评论

THE parameterized complexity OF FINDING A 2-SPHERE IN A SIMPLICIAL COMPLEX

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2019年第4期33卷 2092-2110页

作者： Burton, Benjamin Cabello, Sergio Kratsch, Stefan Pettersson, William Univ Queensland Sch Math & Phys Brisbane Qld Australia Univ Ljubljana Fac Math & Phys Ljubljana Slovenia Inst Math Phys & Mech Ljubljana Slovenia Univ Bonn Dept Comp Sci Bonn Germany Humboldt Univ Dept Comp Sci Berlin Germany RMIT Univ Sch Sci Melbourne Vic Australia Univ Glasgow Sch Comp Sci Glasgow Lanark Scotland

We consider the problem of finding a subcomplex K' of a simplicial complex K such that K' is homeomorphic to the 2-dimensional sphere, S-2. We study two variants of this problem. The first asks if there exists such a K' with at most K triangles, and we show that this variant is W [1]-hard and, assuming the exponential time hypothesis, admits no n(o(root k))-time algorithm. We also give an algorithm that is tight with regard to this lower bound. The second problem is the dual of the first and asks if K' can be found by removing at most k triangles from K. This variant has an immediate O (3(k)poly(vertical bar K vertical bar))-time algorithm, and we show that it admits a polynomial kernelization to O (k(2)) triangles, as well as a polynomial compression to a weighted version with bit-size O (k log k).

关键词： computational topology parameterized complexity simplicial complex

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of the geodesic hull number

引用

THEORETICAL COMPUTER SCIENCE 2019年 791卷 10-27页

作者： Kante, Mamadou Moustapha Marcilon, Thiago Sampaio, Rudini Univ Clermont Auvergne CNRS LIMOS Clermont Ferrand France Univ Fed Cariri Ctr Ciencias & Tecnol Juazeiro Do Norte Brazil Univ Fed Ceara Dept Comp Fortaleza Ceara Brazil

Several recent papers obtained complexity results regarding the geodesic hull number hn(gd)(G) of a graph G. In this paper, we prove that determining whether hngd(G) <= k is W[2]-hard parameterized by k in diameter-two graphs and is W[1] -hard parameterized by tw +4, where tw is the treewidth of G. Despite this, for graphs with bounded treewidth tw, we prove that hngd(G) is computable in polynomial time O ((tw+2)(tw+5)n(2tw+5)). (C) 2019 Elsevier B.V. All rights reserved.

关键词： Geodesic convexity Hull number parameterized complexity Treewidth

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：