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

Modifying a Graph Using Vertex Elimination

ALGORITHMICA 2015年第1期72卷 99-125页

作者： Golovach, Petr A. Heggernes, Pinar van 't Hof, Pim Manne, Fredrik Paulusma, Daniel Pilipczuk, Michal Univ Bergen Dept Informat N-5008 Bergen Norway Univ Durham Sch Engn & Comp Sci Durham England

Vertex elimination is a graph operation that turns the neighborhood of a vertex into a clique and removes the vertex itself. It has widely known applications within sparse matrix computations. We define the Elimination problem as follows: given two graphs G and H, decide whether H can be obtained from G by |V(G)|-|V(H)| vertex eliminations. We show that Elimination is -hard when parameterized by |V(H)|, even if both input graphs are split graphs, and -hard when parameterized by |V(G)|-|V(H)|, even if H is a complete graph. On the positive side, we show that Elimination admits a kernel with at most 5|V(H)| vertices in the case when G is connected and H is a complete graph, which is in sharp contrast to the -hardness of the related Clique problem. We also study the case when either G or H is tree. The computational complexity of the problem depends on which graph is assumed to be a tree: we show that Elimination can be solved in polynomial time when H is a tree, whereas it remains NP-complete when G is a tree.

关键词： Graph modification problems Vertex elimination parameterized complexity Linear kernel

来源：评论

学校读者我要写书评

暂无评论

INDUCED DISJOINT PATHS IN CLAW-FREE GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2015年第1期29卷 348-375页

作者： Golovach, Petr A. Paulusma, Daniel Van Leeuwen, Erik Jan Univ Bergen Dept Informat N-5008 Bergen Norway Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England Max Planck Inst Informat D-66123 Saarbrucken Germany

Paths P-1,..., P-k in a graph G = (V, E) are said to be mutually induced if for any 1 <= i < j <= k, P-i and P-j have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The INDUCED DISJOINT PATHS problem is to test whether a graph G with k pairs of specified vertices (s(i), t(i)) contains k mutually induced paths P-i such that P-i connects s(i) and t(i) for i = 1,..., k. We show that this problem is fixed-parameter tractable for claw-free graphs when parameterized by k. Several related problems, such as the k-IN-A-PATH problem, are proved to be fixed-parameter tractable for claw-free graphs as well. We show that an improvement of these results in certain directions is unlikely, for example, by noting that the INDUCED DISJOINT PATHS problem cannot have a polynomial kernel for line graphs (a type of claw-free graphs), unless NP subset of coNP/poly. Moreover, the problem becomes NP-complete, even when k = 2, for the more general class of K-1,K-4-free graphs. Finally, we show that the n(O(k))-time algorithm of Fiala et al. for testing whether a claw-free graph contains some k-vertex graph H as a topological induced minor is essentially optimal by proving that this problem is W[1]-hard even if G and H are line graphs.

关键词： induced disjoint paths claw-free graphs parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On explaining integer vectors by few homogeneous segments

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2015年第4期81卷 766-782页

作者： Bredereck, Robert Chen, Jiehua Hartung, Sepp Komusiewicz, Christian Niedermeier, Rolf Suchy, Ondrej TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Czech Tech Univ Fac Informat Technol Prague Czech Republic

We extend previous studies on "explaining" a nonnegative integer vector by sums of few homogeneous segments, that is, vectors where all nonzero entries are equal and consecutive. We study two NP-complete variants which are motivated by radiation therapy and database applications. In VECTOR POSITIVE EXPLANATION, the segments may have only positive integer entries;in VECTOR EXPLANATION, the segments may have arbitrary integer entries. Considering several natural parameterizations such as the maximum vector entry y and the maximum difference 8 between consecutive vector entries, we obtain a refined picture of the computational (in-)tractability of these problems. For example, we show that VEcrox EXPLANATION is fixed-parameter tractable with respect to delta, and that, unless NP subset of coNP/poly, there is no polynomial kernelization for VECTOR POSITIVE EXPLANATION with respect to the parameter gamma. We also identify relevant special cases where VECTOR POSITIVE EXPLANATION is algorithmically harder than VECTOR EXPLANATION. (C) 2015 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Matrix and vector decomposition Multivariate algorithmics NP-hardness Exact algorithms

来源：评论

学校读者我要写书评

暂无评论

If the Current Clique Algorithms are Optimal, so is Valiant's Parser 56

If the Current Clique Algorithms are Optimal, so is Valiant'...

引用

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 94304 USA MIT EECS Cambridge MA 02139 USA

ISBN: (纸本)9781467381918

The CFG recognition problem is: given a context-free grammar G and a string w of length n, decide if w can be obtained from G. This is the most basic parsing question and is a core computer science problem. Valiant's parser from 1975 solves the problem in O(n(omega)) time, where omega < 2.373 is the matrix multiplication exponent. Dozens of parsing algorithms have been proposed over the years, yet Valiant's upper bound remains unbeaten. The best combinatorial algorithms have mildly subcubic O(n(3)/log(3) n) complexity. Lee (JACM'01) provided evidence that fast matrix multiplication is needed for CFG parsing, and that very efficient and practical algorithms might be hard or even impossible to obtain. Lee showed that any algorithm for a more general parsing problem with running time O(vertical bar G vertical bar center dot n(3-epsilon)) can be converted into a surprising subcubic algorithm for Boolean Matrix Multiplication. Unfortunately, Lee's hardness result required that the grammar size be vertical bar G vertical bar = Omega(n(6)). Nothing was known for the more relevant case of constant size grammars. In this work, we prove that any improvement on Valiant's algorithm, even for constant size grammars, either in terms of runtime or by avoiding the inefficiencies of fast matrix multiplication, would imply a breakthrough algorithm for the k-Clique problem: given a graph on n nodes, decide if there are k that form a clique. Besides classifying the complexity of a fundamental problem, our reduction has led us to similar lower bounds for more modern and well-studied cubic time problems for which faster algorithms are highly desirable in practice: RNA Folding, a central problem in computational biology, and Dyck Language Edit Distance, answering an open question of Saha (FOCS' 14).

关键词： context free grammars parsing CFG recognition clique conditional lower bounds RNA folding Dyck Edit Distance hardness in P tight hardness combinatorial algorithms Valiant's algorithm natural language processing parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Manipulation with Bounded Single-Peaked Width: A parameterized Study 15

Manipulation with Bounded Single-Peaked Width: A Parameteriz...

引用

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

作者： Yang, Yongjie Univ Saarland Campus E 1-7 MMCI D-66123 Saarbrucken Germany

ISBN: (纸本)9781450334136

We study the manipulation problem in elections with bounded single-peaked width from the parameterized complexity point of view. In particular, we focus on the Borda, Copeland(alpha) and Maximin voting correspondences. For Borda, we prove that the unweighted manipulation problem with two manipulators is fixed-parameter tractable with respect to single-peaked width. For Maximin and Copeland(alpha) for every 0 <= alpha <= 1, we prove that the unweighted manipulation problem is fixed-parameter tractable with respect to the combined parameter (k, t), where k denotes the single-peaked width and t denotes the number of manipulators. In addition, we study the weighted manipulation problem for Maximin and Copeland(alpha) for every 0 <= alpha <= 1 in single-peaked elections and achieve several polynomial-time solvability results.

关键词： single-peaked width fixed-parameter tractable parameterized complexity Borda Maximin Copeland weighted election

来源：评论

学校读者我要写书评

暂无评论

How Hard is Control in Multi-Peaked Elections: A parameterized Study 14

How Hard is Control in Multi-Peaked Elections: A Parameteriz...

引用

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

作者： Yang, Yongjie Guo, Jiong Univ Saarland Campus E 1-7 MMCI D-66123 Saarbrucken Germany Shandong Univ Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China

ISBN: (纸本)9781450334136

We study the complexity of voting control problems in multi-peaked elections. In particular, we focus on the constructive/destructive control by adding/deleting votes under Condorcet, Maximin and Copeland(alpha) voting systems. We show that the NP-hardness of these problems (except for the destructive control by adding/deleting votes under Condorcet, which is polynomial-time solvable in the general case) hold even in kappa-peaked elections with kappa being a very small constant. Furthermore, from the parameterized complexity point of view, our reductions actually show that these problems are W[1]-hard in kappa-peaked elections with kappa = 3;4, with respect to the number of added/deleted votes.

关键词： single-peaked generalization multi-peaked parameterized complexity election control Condorcet Maximin Copeland

来源：评论

学校读者我要写书评

暂无评论

Control complexity in Bucklin and fallback voting: A theoretical analysis

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2015年第4期81卷 632-660页

作者： Erdelyi, Gabor Fellows, Michael R. Rothe, Joerg Schend, Lena Univ Siegen Sch Econ Disciplines D-57076 Siegen Germany Charles Darwin Univ Parameterized Complex Res Unit Darwin NT 0909 Australia Univ Dusseldorf Inst Informat D-40225 Dusseldorf Germany

Electoral control models ways of changing the outcome of an election via such actions as adding, deleting, or partitioning either candidates or voters. To protect elections from such control attempts, computational complexity has been used to establish so-called resistance results. We show that fallback voting, an election system proposed by Brams and Sanver [12] to combine Bucklin with approval voting, displays the broadest control resistance currently known to hold among natural election systems with a polynomial-time winner problem. We also study the control complexity of Bucklin voting and show that it performs almost as well as fallback voting in terms of control resistance. Furthermore, we investigate the parameterized control complexity of Bucklin and fallback voting, according to several parameters that are often likely to be small for typical instances. In a companion paper [28], we challenge our worst-case complexity results from an experimental point of view. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Computational social choice Control complexity Bucklin voting Fallback voting parameterized complexity Election systems

来源：评论

学校读者我要写书评

暂无评论

Social Models and Algorithms for Optimization of Contact Immunity of Oral Polio Vaccine 9th

Social Models and Algorithms for Optimization of Contact Imm...

引用

9th International Frontiers of Algorithmics Workshop (FAW)

作者： Guo, Chengwei Ma, Chenglong Zhang, Shengyu Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China

ISBN: (纸本)9783319196473;9783319196466

Oral polio vaccine (OPV) can produce contact immunity and help protect more individuals than the vaccinated from polio. To better capture the utilization of OPV's contact immunity, we model the community as a social network, and formulate the task of maximizing the contact immunity effect as an optimization problem on graphs, which is to find a sequence of vertices to be "vaccinated" to maximize the total number of "infected" vertices. Furthermore, we consider the restriction imported by immune deficient individuals, and study related problems. We present polynomial-time algorithms for these problems on trees, and show the intractability of problems on general graphs.

关键词： Epidemic model Social network Graph theory parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

A refined complexity analysis of degree anonymization in graphs

A refined complexity analysis of degree anonymization in gra...

引用

40th International Colloquium on Automata, Languages and Programming (ICALP)

作者： Hartung, Sepp Nichterlein, Andre Niedermeier, Rolf Suchy, Ondrej TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Czech Tech Univ Fac Informat Technol Prague Czech Republic

ISBN: (纸本)9783642392115

Motivated by a strongly growing interest in graph anonymization, we study the NP-hard DEGREE ANONYMITY problem asking whether a graph can be made k-anonymous by adding at most a given number of edges. Herein, a graph is k-anonymous if for every vertex in the graph there are at least k - 1 other vertices of the same degree. Our algorithmic results shed light on the performance quality of a popular heuristic due to Liu and Terzi [ACM SIGMOD 2008];in particular, we show that the heuristic provides optimal solutions if "many" edges need to be added. Based on this, we develop a polynomial-time data reduction yielding a polynomial-size problem kernel for DEGREE ANONYMITY parameterized by the maximum vertex degree. In terms of parameterized complexity analysis, this result is in a sense tight since we also show that the problem is already NP-hard for H-index three, implying NP-hardness for smaller parameters such as average degree and degeneracy. (C) 2014 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Kernelization Heuristics f-Factors Data privacy

来源：评论

学校读者我要写书评

暂无评论

FO Model Checking on Posets of Bounded Width 56

FO Model Checking on Posets of Bounded Width

引用

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

作者： Gajarsky, Jakub Hlineny, Petr Lokshtanov, Daniel Obdrzalek, Jan Ordyniak, Sebastian Ramanujan, M. S. Saurabh, Saket Masaryk Univ Fac Informat Brno Czech Republic Univ Bergen Bergen Norway Inst Math Sci Chennai Tamil Nadu India TU Wien Vienna Austria

ISBN: (纸本)9781467381918

Over the past two decades the main focus of research into first-order (FO) model checking algorithms have been sparse relational structures-culminating in the FPT-algorithm by Grohe, Kreutzer and Siebertz for FO model checking of nowhere dense classes of graphs [STOC' 14], with dense structures starting to attract attention only recently. Bova, Ganian and Szeider [CSL-LICS' 14] initiated the study of the complexity of FO model checking on partially ordered sets (posets). Bova, Ganian and Szeider showed that model checking existential FO logic is fixed-parameter tractable (FPT) on posets of bounded width, where the width of a poset is the size of the largest antichain in the poset. The existence of an FPT algorithm for general FO model checking on posets of bounded width, however, remained open. We resolve this question in the positive by giving an algorithm that takes as its input an n-element poset P of width w and an FO logic formula phi, and determines whether phi holds on P in time f(phi, w) . n(2).

关键词： first-order logic partially ordered sets parameterized complexity algorithmic meta-theorems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：