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

27th Annual ACM-SIAM Symposium on Discrete Algorithms

作者： Jeong, Jisu Kim, Eun Jung Oum, Sang-il Korea Adv Inst Sci & Technol Dept Math Sci Daejeon 34141 South Korea PSL Res Univ Univ Paris Dauphine CNRS LAMSADE F-75775 Paris France

Given n subspaces of a finite-dimensional vector space over a fixed finite field F, we wish to find a linear layout V-1, V-2, ... , V-n of the subspaces such that dim((V-1 + V-2 + ... + V-i) boolean AND (Vi+1 + ... + V-n)) <= k for all i;such a linear layout is said to have width at most k. When restricted to 1-dimensional subspaces, this problem is equivalent to computing the trellis-width (or minimum trellis state-complexity) of a linear code in coding theory and computing the path-width of an F-represented matroid in matroid theory. We present a fixed parameter tractable algorithm to construct a linear layout of width at most k, if it exists, for input subspaces of a finite dimensional vector space over F. As corollaries, we obtain a fixed parameter tractable algorithm to produce a path-decomposition of width at most k for an input. F-represented matroid of path-width at most k, and a fixed-parameter tractable algorithm to find a linear rank-decomposition of width at most k for an input graph of linear rank-width at most k. In both corollaries, no such algorithms were known previously. Our approach is based on dynamic programming combined with the idea developed by Bodlaender and Kloks (1996) for their work on path-width and tree-width of graphs. It was previously known that a fixed-parameter tractable algorithm exists for the decision version of the problem for matroid path-width;a theorem by Geelen, Gerards, and Whittle (2002) implies that for each fixed finite field F, there are finitely many forbidden F-representable minors for the class of matroids of path-width at most k. An algorithm by Hlineny (2006) can detect a minor in an input F-represented matroid of bounded branch-width. However, this indirect approach would not produce an actual path-decomposition. Our algorithm is the first one to construct such a path-decomposition and does not depend on the finiteness of forbidden minors.

关键词： parameterized complexity branch-width path-width matroid trellis-width trellis state-complexity linear code linear rank-width linear clique-width

来源：评论

学校读者我要写书评

暂无评论

Perfect domination and small cycles

引用

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS 2017年第3期9卷

作者： Jiang, Minghui Zhang, Yong Utah State Univ Dept Comp Sci Logan UT 84322 USA Kutztown Univ PA Dept Comp Sci Kutztown PA 19530 USA

We study the parameterized complexity of several problems related to perfect domination in graphs with or without small cycles. When parameterized by the solution size, these problems areW-hard in graphs with girth at... 详细信息

关键词： Graph domination perfect code parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Ruling out FPT algorithms for Weighted Coloring on forests

引用

Electronic Notes in Discrete Mathematics 2017年 62卷 195-200页

作者： Araújo, Júlio Baste, Julien Sau, Ignasi Departamento de Matemática Universidade Federal do Ceará Fortaleza Brazil CNRS LIRMM Université de Montpellier Montpellier France

A proper k-coloring of a graph G is a partition c=(Si)i∈[1,k] of V(G) into k stable sets S1,…,Sk. Given a weight function w:V(G)→R+, the weight of a color Si is defined as w(i)=maxv∈S⁡w(v) and the weight of a colo... 详细信息

A proper k-coloring of a graph G is a partition c=(S_i)_i∈[1,k] of V(G) into k stable sets S₁,…,S_k. Given a weight function w:V(G)→R⁺, the weight of a color S_i is defined as w(i)=max_v∈S⁡w(v) and the weight of a coloring c as w(c)=∑_i=1^kw(i). Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair (G, w), denoted by σ(G,w), as the minimum weight of a proper coloring of G. For a positive integer r, they also defined σ(G,w;r) as the minimum of w(c) among all proper r-colorings c of G. The complexity of determining σ(G,w) when G is a tree was open for almost 20 years, until Araújo et al. [SIAM J. Discrete Math., 2014] recently proved that the problem cannot be solved in time n^o(log⁡n) on n-vertex trees unless the Exponential Time Hypothesis (ETH) fails. The objective of this article is to provide hardness results for computing σ(G,w) and σ(G,w;r) when G is a tree or a forest, relying on complexity assumptions weaker than the ETH. Namely, we study the problem from the viewpoint of parameterized complexity, and we assume the weaker hypothesis FPT≠W[1]. Building on the techniques of Araújo et al., we prove that when G is a forest, computing σ(G,w) is W[1]-hard parameterized by the size of a largest connected component of G, and that computing σ(G,w;r) is W[2]-hard parameterized by r. Our results rule out the existence of FPT algorithms for computing these invariants on trees or forests for many natural choices of the parameter. © 2017 Elsevier B.V.

关键词： forests max-coloring parameterized complexity weighted coloring W[1]-hard

来源：评论

学校读者我要写书评

暂无评论

Split Contraction: The Untold Story 34

Split Contraction: The Untold Story

引用

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

作者： Agrawal, Akanksha Lokshtanov, Daniel Saurabh, Saket Zehavi, Meirav Univ Bergen Dept Informat Bergen Norway Inst Math Sci Chennai Tamil Nadu India

ISBN: (纸本)9783959770286

The edit operation that contracts edges. which is a fundamental operation in the theory of graph minors, has recently gained substantial scientific attention from the viewpoint of parameterized complexity. In this paper, we examine an important family of graphs, namely the family of split graphs, which in the context of edge contractions, is proven to be significantly less obedient than one might expect. Formally, given a graph G and an integer k, SPLIT CONTRACTION asks whether there exists X subset of E(G) such that G/X is a split graph and vertical bar X vertical bar <= k. Here, GIX is the graph obtained from G by contracting edges in X. It was previously claimed that SPLIT CONTRACTION is fixed-parameter tractable. However, we show that SPLIT CONTRACTION, despite its deceptive simplicity, is W[l]-hard. Our main result establishes the following conditional lower bound: under the Exponential Time Hypothesis, SPLIT CONTRACTION cannot be solved in time 2(o(l)(2)). n(o(1)) where l is the vertex cover number of the input graph. We also verify that this lower bound is essentially tight. To the best of our knowledge, this is the first tight lower bound of the form 2(o(l)(2)). n(o(1)) for problems parameterized by the vertex cover number of the input graph. In particular, our approach to obtain this lower bound borrows the notion of harmonious coloring from Graph Theory, and might be of independent interest.

关键词： Split Graph parameterized complexity Edge Contraction

来源：评论

学校读者我要写书评

暂无评论

A New Parallel Algorithm for Monotone Circuit Value Problem with Bounded Genus 7

A New Parallel Algorithm for Monotone Circuit Value Problem ...

引用

7th International Conference on Information Science and Technology (ICIST)

作者： Lai, Xiaochen Shi, Wenzhe Liu, Xin Fu, Manqing Li, Shouwei Dalian Univ Technol Sch Software Key Lab Ubiquitous Network & Serv Software Dalian 116024 Peoples R China Dalian Univ Technol Sch Software Dalian 116024 Peoples R China Paderborn Univ Heinz Nixdorf Inst D-33102 Paderborn Germany Paderborn Univ Dept Comp Sci D-33102 Paderborn Germany

ISBN: (纸本)9781509054015

We propose a new complexity class to characterize the efficiently parallelizable parameterized problems called fixed-parameter parallel-tractable (FPPT). Although FPPT = FPP and they can be transformed one another, FPPT is much simpler and reasonable than FPP. The viewpoint of FPPT allows us to concentrate on important intrinsic issues, such as to understand the contribution of each parameter to transfer a problem from NC to P-complete. We also develop a new parallel algorithm for the monotone circuit value problem parameterized by the genus of the underlying graphs, which only based on depth-first search and the PC-tree data structure. Our algorithm implies this problem is in FPPT.

关键词： parameterized complexity monotone circuit value problem parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

On the average-case complexity of parameterized clique

引用

THEORETICAL COMPUTER SCIENCE 2015年第1期576卷 18-29页

作者： Fountoulakis, Nikolaos Friedrich, Tobias Hermelin, Danny Univ Birmingham Edgbaston England Hasso Plattner Inst Potsdam Germany Ben Gurion Univ Negev IL-84105 Beer Sheva Israel

The k-CLIQUE problem is a fundamental combinatorial problem that plays a prominent role in classical as well as in parameterized complexity theory. It is among the most well-known NP-complete and W[1]-complete problems. Moreover, its average-case complexity analysis has created a long thread of research already since the 1970s. Here, we continue this line of research by studying the dependence of the average-case complexity of the k-CLIQUE problem on the parameter k. To this end, we define two natural parameterized analogs of efficient average-case algorithms. We then show that k-CLIQUE admits both analogues for Erclos-Renyi random graphs of arbitrary density. We also show that k-CLIQUE is unlikely to admit either of these analogs for some specific computable input distribution. (C) 2015 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Computational complexity Average-case Clique

来源：评论

学校读者我要写书评

暂无评论

parameterized Dichotomy of Choosing Committees Based on Approval Votes in the Presence of Outliers 16

Parameterized Dichotomy of Choosing Committees Based on Appr...

引用

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

作者： Dey, Palash Misra, Neeldhara Narahari, Y. Tata Inst Fundamental Res Mumbai Maharashtra India Indian Inst Technol Gandhinagar India Indian Inst Sci Bangalore Karnataka India

ISBN: (纸本)9781510855076

Approval ballots provide an opportunity for agents to make a comment about every candidate, without incurring the overhead of determining a full ranking on the set of candidates;they are very natural for many practical settings. We study the computational complexity of the committee selection problem for several approval-based voting rules in the presence of outliers. Our first result shows that outliers render the committee selection problem intractable for approval, net approval, and minisum approval voting rules. We next study the parameterized complexity of this problem with five natural parameters, namely the target score, the size of the committee (and its dual parameter namely the number of candidates outside the committee);and the number of outliers (and its dual parameter namely the number of non-outliers). For approval, net approval, and minisum approval voting rules, we provide a dichotomous result, which resolves the parameterized complexity of this problem for all subsets of the above five natural parameters considered (by showing either FPT or W[1]-hardness for all subsets of parameters).

关键词： voting committee selection outliers social choice parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Structural properties of graphs and eficient algorithms: Problems Between Parameters

Structural properties of graphs and eficient algorithms: Pro...

引用

作者： Knop, Dušan Charles University of Prague

Structural Properties of Graphs and Eficient Algorithms: Problems Between Parameters Dušan Knop parameterized complexity became over last two decades one of the most impor- tant subfield of computational complexity. Structural graph parameters (widths) play important role both in graph theory and (parameterized) algoritmh design. By studying some concrete problems we exhibit the connection between struc- tural graph parameters and parameterized tractability. We do this by examining tractability and hardness results for the Target Set Selection, Minimum Length Bounded Cut, and other problems. In the Minimum Length Bounded Cut problem we are given a graph, source, sink, and a positive integer L and the task is to remove edges from the graph such that the distance between the source and the sink exceeds L in the resulting graph. We show that an optimal solution to the Minimum Length Bounded Cut problem can be computed in time f(k)n, where f is a computable function and k denotes the tree-depth of the input graph. On the other hand we prove that (under assumption that FPT ̸= W[1]) no such algorithm can exist if the parameter k is the tree-width of the input graph. Currently only few such problems are known. The Target Set Selection problem exibits the same phenomenon for the vertex cover number and...

关键词： Graph decompositions computational complexity parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Improved Kernels for Signed Max Cut parameterized Above Lower Bound on (r, l)-graphs

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2017年第1期19卷

作者： Faria, Luerbio Klein, Sulamita Sau, Ignasi Sucupira, Rubens Univ Estado Rio De Janeiro Inst Matemat & Estat Rio De Janeiro Brazil Univ Fed Rio de Janeiro COPPE Sistemas Rio de Janeiro Brazil Univ Fed Rio de Janeiro Inst Matemat Rio de Janeiro Brazil Univ Montpellier CNRS LIRMM Montpellier France Univ Fed Ceara Dept Matemat Fortaleza Ceara Brazil

A graph G is signed if each edge is assigned "+" or "-". A signed graph is balanced if there is a bipartition of its vertex set such that an edge has sign "-" if and only if its endpoints... 详细信息

A graph G is signed if each edge is assigned "+" or "-". A signed graph is balanced if there is a bipartition of its vertex set such that an edge has sign "-" if and only if its endpoints are in different parts. The Edwards-Erdos bound states that every signed graph with n vertices and m edges has a balanced subgraph with at least m/2 + n-1/4 edges. In the SIGNED MAX CUT ABOVE TIGHT LOWER BOUND (SIGNED MAX CUT ATLB) problem, given a signed graph G and a parameter k, the question is whether G has a balanced subgraph with at least m/2 + n-1/4 + k/4 edges. This problem generalizes MAX CUT ABOVE TIGHT LOWER BOUND, for which a kernel with O(k(5)) vertices was given by Crowston et al. [ICALP 2012, Algorithmica 2015]. Crowston et al. [TCS 2013] improved this result by providing a kernel with O(k(3)) vertices for the more general SIGNED MAX CUT ATLB problem. In this article we are interested in improving the size of the kernels for SIGNED MAX CUT ATLB on restricted graph classes for which the problem remains hard. For two integers r, l >= 0, a graph G is an (r, l)-graph if V(G) can be partitioned into r independent sets and l cliques. Building on the techniques of Crowston et al. [TCS 2013], for any r, l >= 0 we provide a kernel with O((r + l)k(2)) vertices on (r, l)-graphs, and a simple linear kernel on subclasses of split graphs for which we prove that the problem is still NP-hard.

关键词： max cut (r, l)-graphs split graphs parameterized complexity parameterization above lower bound polynomial kernels

来源：评论

学校读者我要写书评

暂无评论

Multidimensional Binary Vector Assignment problem: standard, structural and above guarantee parameterizations

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2017年第4期19卷

作者： Bougeret, Marin Duvillie, Guillerme Giroudeau, Rodolphe Watrigant, Remi Univ Montpellier 2 LIRMM Montpellier France Hong Kong Polytech Univ Comp Dept Hong Kong Hong Kong Peoples R China

In this article we focus on the parameterized complexity of the Multidimensional Binary Vector Assignment problem (called BMVA). An input of this problem is defined by m disjoint sets V-1, V-2, ... , V-m, each composed of n binary vectors of size p. An output is a set of n disjoint m-tuples of vectors, where each m-tuple is obtained by picking one vector from each set V-i. To each m-tuple we associate a p dimensional vector by applying the bit-wise AND operation on the m vectors of the tuple. The objective is to minimize the total number of zeros in these n vectors. BMVA can be seen as a variant of multidimensional matching where hyperedges are implicitly locally encoded via labels attached to vertices, but was originally introduced in the context of integrated circuit manufacturing. We provide for this problem FPT algorithms and negative results (ETH-based results, W2-hardness and a kernel lower bound) according to several parameters: the standard parameter k (i.e. the total number of zeros), as well as two parameters above some guaranteed values.

关键词： parameterized complexity kernel above guarantee parameterization AND-cross composition multidimensional binary vector assignment wafer-to-wafer integration locally encoded multidimensional matching

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：