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

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

ALGORITHMICA 2018年第7期80卷 2160-2180页

作者： 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

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

来源：评论

学校读者我要写书评

暂无评论

Approximate inference in Bayesian networks: parameterized complexity results

引用

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING 2018年 93卷 119-131页

作者： Kwisthout, Johan Radboud Univ Nijmegen Donders Inst Brain Cognit & Behav Montessorilaan 3 NL-6525 HR Nijmegen Netherlands

Computing posterior and marginal probabilities constitutes the backbone of almost all inferences in Bayesian networks. These computations are known to be intractable in general, both to compute exactly and to approximate (e.g., by sampling algorithms). While it is well known under what constraints exact computation can be rendered tractable (viz., bounding tree-width of the moralized network and bounding the cardinality of the variables) it is less known under what constraints approximate Bayesian inference can be tractable. Here, we extend the existing formal framework of fixed-error randomized tractability (a randomized analogue of fixed-parameter tractability), and use it to address this problem, both by re-interpreting known results from the literature and by providing some additional new results, including results on fixed parameter tractable de-randomization of approximate inference. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Approximate inference Sampling Bayesian networks parameterized complexity Stochastic algorithms De-randomization

来源：评论

学校读者我要写书评

暂无评论

MATRIX RIGIDITY FROM THE VIEWPOINT OF parameterized complexity

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2018年第2期32卷 966-985页

作者： Fomin, Fedor, V Lokshtanov, Daniel Meesum, S. M. Saurabh, Saket Zehavi, Meirav Univ Bergen Dept Informat Bergen Norway HBNI Inst Math Sci Theoret Comp Sci Madras 600113 Tamil Nadu India

For a target rank r, the rigidity of a matrix A over a field F is the minimum Hamming distance between A and a matrix of rank at most r. Rigidity is a classical concept in computational complexity theory: constructions of rigid matrices are known to imply lower bounds of significant importance relating to arithmetic circuits. Yet, from the viewpoint of parameterized complexity, the study of central properties of matrices in general, and of the rigidity of a matrix in particular, has been neglected. In this paper, we conduct a comprehensive study of different aspects of the computation of the rigidity of general matrices in the framework of parameterized complexity. Naturally, given parameters r and k, the Matrix Rigidity problem asks whether the rigidity of A for the target rank r is at most k. We show that in the case F = R or F is any finite field, this problem is fixed-parameter tractable with respect to k+ r. To this end, we present a dimension reduction procedure, which may be a valuable primitive in future studies of problems of this nature. We also employ central tools in real algebraic geometry, which are not well known in parameterized complexity, as a black box. In particular, we view the output of our dimension reduction procedure as an algebraic variety. Our main results are complemented by a W[1]-hardness result and a subexponential-time parameterized algorithm for a special case of Matrix Rigidity, highlighting the different flavors of this problem.

关键词： matrix rigidity parameterized complexity linear algebra

来源：评论

学校读者我要写书评

暂无评论

Taxi-sharing: parameterized complexity and approximability of the dial-a-ride problem with money as an incentive

引用

THEORETICAL COMPUTER SCIENCE 2018年 745卷 202-223页

作者： Watel, Dimitri Faye, Alain ENSIIE 1 Sq Resistance F-91025 Evry France Telecom SudParis SAMOVAR 9 Rue Charles Fourier F-91000 Evry France CNAM CEDRIC 2 Rue Conte F-75003 Paris France

We study, in this paper, a taxi-sharing problem, called Dial-a-Ride problem with money as an incentive (DARP-M). This problem consists in defining a set of taxis that will be shared by different clients in order to reduce their bill by a given factor alpha < 1. To achieve this, each client shares the cost of the ride with other passengers. More precisely, the fragments of the ride in which the client is alone is fully paid by this client and, for each fragment in which the client shares the taxi with other passengers, the cost is equally divided between the passengers. In addition to this cost constraint, the taxi must satisfy a time window constraint for each passenger and a capacity constraint. We define three versions of the problem: max-DARP-M where the objective is to drive the maximum number of clients with an arbitrarily large number of taxis;max-1-DARP-M in which we want to drive the maximum number of clients with one taxi;and 1-DARPM which consists in deciding whether it is possible to drive at least one client while satisfying the constraints. We study the parameterized complexity and approximability of those problems with respect to four parameters: the factor alpha, the capacity capa of the taxis, the maximum size TW of the time windows of the clients, and the value S of an optimal solution. Among other results, we prove that 1-DARP-M is NP-Complete and max-DARP-M and max-l-DARP-M cannot be approximated in polynomial time to within any variable ratio even if alpha, capa and T W are fixed and if the road network is a planar graph. We also give a polynomial algorithm for max-1-DARP-M for the case where capa and TW are fixed and where the network does not contain a circuit. This algorithm implies a 1/root n-polynomial approximation for max-DARP-M. (C) 2018 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Approximability Dial-a-ride problem Taxi-sharing

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity Dichotomy for (r, a)-Vertex Deletion

引用

THEORY OF COMPUTING SYSTEMS 2017年第3期61卷 777-794页

作者： Baste, Julien Faria, Luerbio Klein, Sulamita Sau, Ignasi LIRMM CNRS AlGCo Project Team Montpellier France Univ Estado Rio de Janeiro FFP Rio De Janeiro Brazil Univ Fed Rio de Janeiro Rio De Janeiro Brazil

For two integers r, a"" 0, a graph G = (V, E) is an (r, a"")-graph if V can be partitioned into r independent sets and a"" cliques. In the parameterized (r, a"")-Vertex Deletion... 详细信息

For two integers r, a"" 0, a graph G = (V, E) is an (r, a"")-graph if V can be partitioned into r independent sets and a"" cliques. In the parameterized (r, a"")-Vertex Deletion problem, given a graph G and an integer k, one has to decide whether at most k vertices can be removed from G to obtain an (r, a"")-graph. This problem is NP-hard if r + a"" 1 and encompasses several relevant problems such as Vertex Cover and Odd Cycle Transversal. The parameterized complexity of (r, a"")-Vertex Deletion was known for all values of (r, a"") except for (2,1), (1,2), and (2,2). We prove that each of these three cases is FPT and, furthermore, solvable in single-exponential time, which is asymptotically optimal in terms of k. We consider as well the version of (r, a"")-Vertex Deletion where the set of vertices to be removed has to induce an independent set, and provide also a parameterized complexity dichotomy for this problem.

关键词： Graph modification problem parameterized complexity Iterative compression FPT-algorithm Single-exponential algorithm

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Superstring Problems

引用

ALGORITHMICA 2017年第3期79卷 798-813页

作者： Bliznets, Ivan Fomin, Fedor V. Golovach, Petr A. Karpov, Nikolay Kulikov, Alexander S. Saurabh, Saket Russian Acad Sci St Petersburg Dept Steklov Inst Math St Petersburg Russia Univ Bergen Dept Informat Bergen Norway Inst Math Sci Madras Tamil Nadu India

In the Shortest Superstring problem we are given a set of strings and S = {s(1),..., s(n}) integer l and the question is to decide whether there is a superstring s of length at most l containing all strings of S as substrings. We obtain several parameterized algorithms and complexity results for this problem. In particular, we give an algorithm which in time 2(O(k)) poly(n) finds a superstring of length at most l containing at least k strings of S. We complement this by a lower bound showing that such a parameterization does not admit a polynomial kernel up to some complexity assumption. We also obtain several results about "below guaranteed values" parameterization of the problem. We show that parameterization by compression admits a polynomial kernel while parameterization "below matching" is hard.

关键词： Shortest superstring parameterized complexity Kernelization

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity classes beyond para-NP

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2017年 87卷 16-57页

作者： de Haan, Ronald Szeider, Stefan TU Wien Algorithms & Complex Grp Vienna Austria

Today's propositional satisfiability (SAT) solvers are extremely powerful and can be used as an efficient back-end for solving NP-complete problems. However, many fundamental problems in logic, in knowledge representation and reasoning, and in artificial intelligence are located at the second level of the Polynomial Hierarchy or even higher, and hence for these problems polynomial-time transformations to SAT are not possible, unless the hierarchy collapses. Recent research shows that in certain cases one can break through these complexity barriers by fixed-parameter tractable (fpt) reductions to SAT which exploit structural aspects of problem instances in terms of problem parameters. These reductions are more powerful because their running times can grow superpolynomially in the problem parameters. In this paper we develop a general theoretical framework that supports the classification of parameterized problems on whether they admit such an fpt-reduction to SAT or not. (C) 2017 The Author(s). Published by Elsevier Inc.

关键词： parameterized complexity Fpt-reductions Polynomial hierarchy Weft-hierarchy

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Secluded Connectivity Problems

引用

THEORY OF COMPUTING SYSTEMS 2017年第3期61卷 795-819页

作者： Fomin, Fedor V. Golovach, Petr A. Karpov, Nikolay Kulikov, Alexander S. Univ Bergen Dept Informat Bergen Norway Russian Acad Sci Steklov Inst Math St Petersburg St Petersburg Russia

The Secluded Path problem models a situation where sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of a selected path is its exposure cost, which is the total cost of vertices in its closed neighborhood. The task is to select a secluded path, i.e., a path with a small exposure cost. Similarly, the Secluded Steiner Tree problem is to find a tree in a graph connecting a given set of terminals such that the exposure cost of the tree is minimized. In this paper we present a systematic study of the parameterized complexity of Secluded Steiner Tree. In particular, we establish the tractability of Secluded Path being parameterized by "above guarantee" value, which in this case is the length of a shortest path between vertices. We also show how to extend this result for Secluded Steiner Tree, in this case we parameterize above the size of an optimal Steiner tree and the number of terminals. We also consider various parameterization of the problems such as by the treewidth, the size of a vertex cover, feedback vertex set, or the maximum vertex degree and establish kernelization complexity of the problem subject to different choices of parameters.

关键词： Secluded path Secluded Steiner tree parameterized complexity Kernelization

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of the MINCCA problem on graphs of bounded decomposability

引用

THEORETICAL COMPUTER SCIENCE 2017年 690卷 91-103页

作者： Gozupek, Didem Ozkan, Sibel Paul, Christophe Sau, Ignasi Shalom, Mordechai Gebze Tech Univ Dept Comp Engn Kocaeli Turkey Gebze Tech Univ Dept Math Kocaeli Turkey Univ Montpellier LIRMM CNRS Montpellier France TelHai Coll IL-12210 Upper Galilee Israel Bogazici Univ Dept Ind Engn Istanbul Turkey

In an edge-colored graph, the cost incurred at a vertex on a path when two incident edges with different colors are traversed is called reload or changeover cost. The Minimum Changeover Cost Arborescence (MINCCA) problem consists in finding an arborescence with a given root vertex such that the total changeover cost of the internal vertices is minimized. It has been recently proved by Gozupek et al. (2016) that the MINCCA problem when parameterized by the treewidth and the maximum degree of the input graph is in FPT. In this article we present the following hardness results for MINCCA: the problem is W[1]-hard when parameterized by the vertex cover number of the input graph, even on graphs of degeneracy at most 3. In particular, it is W[1]-hard parameterized by the treewidth of the input graph, which answers the main open problem in the work of Gozupek et al. (2016);it is W[1]-hard on multigraphs parameterized by the tree-cutwidth of the input multigraph;and it remains NP-hard on planar graphs even when restricted to instances with at most 6 colors and 0/1 symmetric costs, or when restricted to instances with at most 8 colors, maximum degree bounded by 4, and 0/1 symmetric costs. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Minimum changeover cost arborescence parameterized complexity FPT algorithm Treewidth Tree-cutwidth Planar graph

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Sparse Linear Complementarity Problems

引用

ALGORITHMICA 2017年第1期79卷 42-65页

作者： Sumita, Hanna Kakimura, Naonori Makino, Kazuhisa Natl Inst Informat JST Kawarabayashi Large Graph Project ERATO Tokyo 1018430 Japan Univ Tokyo Grad Sch Arts & Sci Tokyo 1538902 Japan Kyoto Univ Math Sci Res Inst Kyoto 6068502 Japan

In this paper, we study the parameterized complexity of the linear complementarity problem (LCP), which is one of the most fundamental mathematical optimization problems. The parameters we focus on are the sparsities of the input and the output of the LCP: the maximum numbers of nonzero entries per row/column in the coefficient matrix and the number of nonzero entries in a solution. Our main result is to present a fixed-parameter algorithm for the LCP with the combined parameter. We also show that if we drop any of the three parameters, then the LCP is NP-hard or W[1]-hard. In addition, we show the nonexistence of a polynomial kernel for the LCP unless coNP NP/poly.

关键词： Linear complementarity problem Sparsity parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：