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

parameterized Hardness of Art Gallery Problems

ACM TRANSACTIONS ON ALGORITHMS 2020年第4期16卷 1–23页

作者： Bonnet, Edouard Miltzow, Tillmann Univ Claude Bernard Lyon 1 Univ Lyon CNRS ENS LyonLab Informat Parallelisme 46 Allee Italie F-69007 Lyon France Univ Utrecht Princetonpl 5 NL-3584 CC Utrecht Netherlands

Given a simple polygon P on n vertices, two points x, y in P are said to be visible to each other if the line segment between x and y is contained in P. The POINT GUARD ART GALLERY problem asks for a minimum set S such that every point in P is visible from a point in S. The VERTEX GUARD ART GALLERY problem asks for such a set S subset of the vertices of P. A point in the set S is referred to as a guard. For both variants, we rule out any f(k)n(o(k/log k)) algorithm, where k := vertical bar S vertical bar is the number of guards, for any computable function f, unless the exponential time hypothesis fails. These lower bounds almost match the n(O(k)) algorithms that exist for both problems.

关键词： Computational geometry art gallery parameterized complexity intractability ETH lower bound

来源：评论

学校读者我要写书评

暂无评论

Color spanning objects: Algorithms and hardness results

引用

DISCRETE APPLIED MATHEMATICS 2020年 280卷 14-22页

作者： Banerjee, Sandip Misra, Neeldhara Nandy, Subhas C. Indian Stat Inst Kolkata India Indian Inst Technol Gandhinagar India

In this paper, we study the SHORTEST COLOR SPANNING t- INTERVALS problem, and related generalizations, namely SMALLEST COLOR SPANNING t- SQUARES and SMALLEST COLOR SPANNING t- CIRCLES. The generic setting is the following: we are given n points in the plane (or on a line), each colored with one of k colors. For each color i we also have a demand s(i). Given a budget t, we are required to find at most t objects (for example, intervals, squares, circles, etc.) that cover at least si points of color i. Typically, the goal is to minimize the maximum perimeter or area. We provide exact algorithms for these problems for the cases of intervals, circles and squares, generalizing several known results. In the case of intervals, we provide a comprehensive understanding of the complexity landscape of the problem after taking several natural parameters into account. Given that the problem turns out to be W[1]-hard parameterized by the standard parameters, we introduce a new parameter, namely sparsity, and prove new hardness and tractability results in this context. For squares and circles, we use existing algorithms of one smallest color spanning object in order to design algorithms for getting t identical objects of minimum size whose union spans all the colors. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Color spanning sets Computational geometry parameterized complexity Exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Solving hard stable matching problems involving groups of similar agents

引用

THEORETICAL COMPUTER SCIENCE 2020年 844卷 171-194页

作者： Meeks, Kitty Rastegari, Baharak Univ Glasgow Sch Comp Sci Glasgow Lanark Scotland Univ Southampton Dept Elect & Comp Sci Southampton Hants England

Many important stable matching problems are known to be NP-hard, even when strong restrictions are placed on the input. In this paper we seek to identify structural properties of instances of stable matching problems which will allow us to design efficient algorithms using elementary techniques. We focus on the setting in which all agents involved in some matching problem can be partitioned into k different types, where the type of an agent determines his or her preferences, and agents have preferences over types (which may be refined by more detailed preferences within a single type). This situation would arise in practice if agents form preferences solely based on some small collection of agents' attributes. We also consider a generalisation in which each agent may consider some small collection of other agents to be exceptional, and rank these in a way that is not consistent with their types;this could happen in practice if agents have prior contact with a small number of candidates. We show that (for the case without exceptions), several well-studied NP-hard stable matching problems including MAX SMTI (that of finding the maximum cardinality stable matching in an instance of stable marriage with ties and incomplete lists) belong to the parameterised complexity class FPT when parameterised by the number of different types of agents needed to describe the instance. For MAX SMTI this tractability result can be extended to the setting in which each agent promotes at most one "exceptional" candidate to the top of his/her list (when preferences within types are not refined), but the problem remains NP-hard if preference lists can contain two or more exceptions and the exceptional candidates can be placed anywhere in the preference lists, even if the number of types is bounded by a constant. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Stable matchings Stable marriage problem Stable roommate problem NP-hard problems parameterized complexity Fixed-parameter tractable algorithms

来源：评论

学校读者我要写书评

暂无评论

Lower bounds for the happy coloring problems

引用

THEORETICAL COMPUTER SCIENCE 2020年 838卷 94-110页

作者： Bliznets, Ivan Sagunov, Danil Russian Acad Sci St Petersburg Dept Steklov Inst Math St Petersburg Russia

In this paper, we study the MAXIMUM HAPPY VERTICES and the MAXIMUM HAPPY EDGES problems (MHV and MHE for short). Very recently, the problems attracted a lot of attention and were studied in Agrawal '18, Aravind et al. '16, Choudhari and Reddy '18, Misra and Reddy '18. Main focus of our work is lower bounds on the computational complexity of these problems. Established lower bounds can be divided into the following groups: NP-hardness of the above guarantee parameterization, kernelization lower bounds (answering questions of Misra and Reddy '18), exponential lower bounds under the SET COVER CONJECTURE and the EXPONENTIAL TIME HYPOTHESIS, and inapproximability results. Moreover, we present an O*(l(k)) randomized algorithm for MHV and an O*(2(k)) algorithm for MHE, where l is the number of colors used and k is the number of required happy vertices or edges. These algorithms cannot be improved to subexponential taking proved lower bounds into account. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Happy coloring Maximum happy vertices Maximum happy edges Kernelization Exponential time hypothesis parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

complexity of independency and cliquy trees

引用

DISCRETE APPLIED MATHEMATICS 2020年第0期272卷 2-15页

作者： Casel, Katrin Dreier, Jan Fernau, Henning Gobbert, Moritz Kuinke, Philipp Villaamil, Fernando Sanchez Schmid, Markus L. van Leeuwen, Erik Jan Univ Trier CIRT Fachbereich 4 Abt Informatikwissensch D-54286 Trier Germany Univ Utrecht Dept Informat & Comp Sci POB 80-089 NL-3508 TB Utrecht Netherlands Rhein Westfal TH Aachen Lehr & Forschungsgebiet Theoret Informat D-52074 Aachen Germany Univ Potsdam Hasso Plattner Inst D-14482 Potsdam Germany

An independency (cliquy) tree of an n-vertex graph G is a spanning tree of G in which the set of leaves induces an independent set (clique). We study the problems of minimizing or maximizing the number of leaves of such trees, and fully characterize their parameterized complexity. We show that all four variants of deciding if an independency/cliquy tree with at least/most l leaves exists parameterized by l are either Para-NP- or W[1]-hard. We prove that minimizing the number of leaves of a cliquy tree parameterized by the number of internal vertices is Para-NP-hard too. However, we show that minimizing the number of leaves of an independency tree parameterized by the number k of internal vertices has an O*(4(k))-time algorithm and a 2k vertex kernel. Moreover, we prove that maximizing the number of leaves of an independency/cliquy tree parameterized by the number k of internal vertices both have an O*(18(k))-time algorithm and an O(k 2(k)) vertex kernel, but no polynomial kernel unless the polynomial hierarchy collapses to the third level. Finally, we present an O(3(n) . f(n))-time algorithm to find a spanning tree where the leaf set has a property that can be decided in f (n) time and has minimum or maximum size. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Independency tree Cliquy tree parameterized complexity Kernelization algorithms Exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Dual Parameterization of Weighted Coloring

引用

ALGORITHMICA 2020年第8期82卷 2316-2336页

作者： Araujo, Julio Campos, Victor A. Lima, Carlos Vinicius G. C. dos Santos, Vinicius Fernandes Sau, Ignasi Silva, Ana Univ Fed Ceara Dept Matemat Fortaleza Ceara Brazil Univ Fed Ceara Dept Comp Fortaleza Ceara Brazil Univ Fed Minas Gerais Dept Ciencia Comp Belo Horizonte MG Brazil Univ Montpellier LIRMM CNRS Montpellier France

Given a graph G, a properk-coloring of G is a partition c=(Si)i is an element of[1,k] of V(G) into k stable sets S1, horizontal ellipsis ,Sk. Given a weight function w:V(G)-> R+, the weight of a colorSi is defined as w(i)=maxv is an element of Siw(v) and the weight of a coloringc as w(c)= n-ary sumation i=1kw(i). Guan and Zhu (Inf Process Lett 61(2):77-81, 1997) defined the weighted chromatic number of a pair (G, w), denoted by sigma(G,w), as the minimum weight of a proper coloring of G. The problem of determining sigma(G,w) has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on n-vertex trees in time no(logn) unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph (G, w) and an integer k, is sigma(G,w)<= n-ary sumation v is an element of V(G)w(v)-k? This parameterization has been recently considered by Escoffier (in: Proceedings of the 42nd international workshop on graph-theoretic concepts in computer science (WG). LNCS, vol 9941, pp 50-61, 2016), who provided an FPT algorithm running in time 2O(klogk)center dot nO(1), and asked which kernel size can be achieved for the problem. We provide an FPT algorithm in time 9k center dot nO(1), and prove that no algorithm in time 2o(k)center dot nO(1) exists under the ETH. On the other hand, we present a kernel with at most (2k-1+1)(k-1) vertices, and rule out the existence of polynomial kernels unless NP subset of coNP/poly, even on split graphs with only two different weights. Finally, we identify classes of graphs allowing for polynomial kernels, namely interval graphs, comparability graphs, and subclasses of circular-arc and split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.

关键词： Weighted coloring Max coloring parameterized complexity Dual parameterization FPT algorithms Polynomial kernels Split graphs Interval graphs

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithms of fundamental NP-hard problems: a survey

引用

HUMAN-CENTRIC COMPUTING AND INFORMATION SCIENCES 2020年第1期10卷 1-24页

作者： Li, Wenjun Ding, Yang Yang, Yongjie Sherratt, R. Simon Park, Jong Hyuk Wang, Jin Changsha Univ Sci & Technol Dept Comp & Commun Engn Changsha Peoples R China Saarland Univ Saarbrucken Germany Univ Reading Sch Syst Engn Reading Berks England Seoul Natl Univ Sci & Technol Dept Comp Sci & Engn Seoul South Korea

parameterized computation theory has developed rapidly over the last two decades. In theoretical computer science, it has attracted considerable attention for its theoretical value and significant guidance in many practical applications. We give an overview on parameterized algorithms for some fundamental NP-hard problems, including MaxSAT, Maximum Internal Spanning Trees, Maximum Internal Out-Branching, Planar (Connected) Dominating Set, Feedback Vertex Set, Hyperplane Cover, Vertex Cover, Packing and Matching problems. All of these problems have been widely applied in various areas, such as Internet of Things, Wireless Sensor Networks, Artificial Intelligence, Bioinformatics, Big Data, and so on. In this paper, we are focused on the algorithms' main idea and algorithmic techniques, and omit the details of them.

关键词： NP-hard parameterized complexity FPT W[t]-hard AI IoT

来源：评论

学校读者我要写书评

暂无评论

The complexity of Tree Partitioning

引用

ALGORITHMICA 2020年第9期82卷 2606-2643页

作者： An, Zhao Feng, Qilong Kanj, Iyad Xia, Ge Cent South Univ Sch Comp Sci & Engn Changsha Peoples R China Depaul Univ Sch Comp Chicago IL 60604 USA Lafayette Coll Dept Comp Sci Easton PA 18042 USA

Given a tree T on n vertices, and k, b, s 1,., s b. N, the Tree Partitioning problem asks if at most k edges can be removed from T so that the resulting components can be grouped into b groups such that the number of vertices in group i is s i, for i = 1,., b. The case where s 1 =. = s b = n/b, referred to as the Balanced Tree Partitioning problem, was shown to be NP-complete for trees of maximum degree at most 5, and the complexity of the problem for trees of maximum degree 4 and 3 was posed as an open question. The parameterized complexity of Balanced Tree Partitioning was also posed as an open question in another work. In this paper, we answer both open questions negatively. We show that Balanced Tree Partitioning (and hence, Tree Partitioning) is NP-complete for trees of maximum degree 3, thus closing the door on the complexity of Balanced Tree Partitioning, as the simple case when T is a path is in P. In terms of the parameterized complexity of the problems, we show that both Balanced Tree Partitioning and Tree Partitioning are W[1]-complete parameterized by k. Using a compact representation of the solution space for an instance of the problem, we present a dynamic programming algorithm for the weighted version of Tree Partitioning (and hence for that of Balanced Tree Partitioning) that runs in subexponential-time 2O(vn), adding a natural problem to the list of problems that can be solved in subexponential time. Finally, we extend this subexponential-time algorithm to the Weighted Graph Partitioning problem on graphs of treewidth o(n/ lg n), and we also show an application of this subexponential-time algorithm for approximating the Weighted Graph Partitioning problem.

关键词： Tree partitioning parameterized complexity Subexponential-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Quadratic Vertex Kernel for Rainbow Matching

引用

ALGORITHMICA 2020年第4期82卷 881-897页

作者： Gupta, Sushmita Roy, Sanjukta Saurabh, Saket Zehavi, Meirav Natl Inst Sci Educ & Res Bhubaneswar India HBNI Inst Math Sci Chennai Tamil Nadu India Univ Bergen Bergen Norway Ben Gurion Univ Negev Beer Sheva Israel

In this paper, we study the NP-complete colorful variant of the classic matching problem, namely, the Rainbow Matching problem. Given an edge-colored graph G and a positive integer k, the goal is to decide whether there exists a matching of size at least k such that the edges in the matching have distinct colors. Previously, in [MFCS'17], we studied this problem from the view point of parameterized complexity and gave efficient FPT algorithms as well as a quadratic kernel on paths. In this paper we design a quadratic vertex kernel for Rainbow Matching on general graphs;generalizing the earlier quadratic kernel on paths to general graphs. For our kernelization algorithm we combine a graph decomposition method with an application of expansion lemma.

关键词： Rainbow matching parameterized complexity Polynomial kernel

来源：评论

学校读者我要写书评

暂无评论

parameterized Multi-Scenario Single-Machine Scheduling Problems

引用

ALGORITHMICA 2020年第9期82卷 2644-2667页

作者： Hermelin, Danny Manoussakis, George Pinedo, Michael Shabtay, Dvir Yedidsion, Liron Ben Gurion Univ Negev Dept Ind Engn & Management POB 653 IL-8410501 Beer Sheva Israel NYU Stern Sch Business 44 West 4th St New York NY 10012 USA

We study a class of multi-scenario single-machine scheduling problems. In this class of problems, we are given a set of scenarios with each one having a different realization of job characteristics. We consider these multi-scenario problems where the scheduling criterion can be any one of the following three: The total weighted completion time, the weighted number of tardy jobs, and the weighted number of jobs completed exactly at their due-date. As all the resulting problems are NP-hard, our analysis focuses on whether any one of the problems becomes tractable when some specific natural parameters are of limited size. The analysis includes the following parameters: The number of jobs with scenario-dependent processing times, the number of jobs with scenario-dependent weights, and the number of different due-dates.

关键词： Single machine scheduling Multi-scenario scheduling parameterized complexity Fixed-parameter tractability Robust job schedule

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：