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

Inductive k-independent graphs and c-colorable subgraphs in scheduling: a review

JOURNAL OF SCHEDULING 2019年第1期22卷 3-20页

作者： Bentert, Matthias van Bevern, Rene Niedermeier, Rolf TU Berlin Fac 4 Algorithm & Computat Complex Berlin Germany Novosibirsk State Univ Dept Mech & Math Novosibirsk Russia Russian Acad Sci Siberian Branch Sobolev Inst Math Novosibirsk Russia

Inductive k-independent graphs generalize chordal graphs and have recently been advocated in the context of interference-avoiding wireless communication scheduling. The NP-hard problem of finding maximum-weight induced c-colorable subgraphs, which is a generalization of finding maximum independent sets, naturally occurs when selecting csets of pairwise non-conflicting jobs (modeled as graph vertices). We investigate the parameterized complexity of this problem on inductive k-independent graphs. We show that the MaximumIndependentSet problem is W[1]-hard even on 2-simplicial 3-minoesa subclass of inductive 2-independent graphs. In contrast, we prove that the more general Max-Weightc-Colorable Subgraph problem is fixed-parameter tractable on edge-wise unions of cluster and chordal graphs, which are 2-simplicial. In both cases, the parameter is the solution size. Aside from this, we survey other graph classes between inductive 1-independent and inductive 2-independent graphs with applications in scheduling.

关键词： Independent set Job interval selection Interval graphs Chordal graphs Inductive k-independent graphs NP-hard problems parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the parameterized tractability of single machine scheduling with rejection

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2019年第1期273卷 67-73页

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

In this paper we study a single machine scheduling problem with rejection. In such a scheduling problem, the scheduler can reject to process a job in the shop at a certain cost. Our objective is to minimize the total completion time of the jobs to be processed in the shop, given that the total rejection cost will not exceed a certain predefined threshold. The problem is known to be NP-hard, and to better investigate its hardness our objective is to study whether the problem becomes tractable when some specific natural parameters are of a limited size. The analysis is done by using the theory of parameterized complexity and includes the following parameters: the cardinality of the set of accepted jobs, the number of different processing times, the number of different rejection costs, the maximal processing time, and the maximal rejection cost. We show that the problem is W[1]-hard for the first parameter, while it is fixed-parameterized tractable for all other parameters. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Single machine scheduling Scheduling with rejection parameterized complexity Fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

LOSSY KERNELS FOR CONNECTED DOMINATING SET ON SPARSE GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2019年第3期33卷 1743-1771页

作者： Eiben, Eduard Kumar, Mithilesh Mouawad, Amer E. Panolan, Fahad Siebertz, Sebastian TU Wien Algorithms & Complex Grp Vienna Austria Univ Bergen Dept Informat Bergen Norway Univ Warsaw Fac Math Informat & Mech Warsaw Poland

For alpha > 1, an a-approximate (bi)kernel is a polynomial-time algorithm that takes as input an instance (I, k) of a problem 2 and outputs an instance (I', k') (of a problem Q') of size bounded by a function of k such that, for every c >= 1, a c-approximate solution for the new instance can be turned into a (c . alpha)-approximate solution of the original instance in polynomial time. This framework of lossy kernelization was recently introduced by Lokshtanov and co-authors. We study CONNECTED DOMINATING SET (and its distance-r variant) parameterized by solution size on sparse graph classes like biclique-free graphs, classes of bounded expansion, and nowhere dense classes. We prove that for every alpha > 1, CONNECTED DOMINATING SET admits a polynomial-size alpha-approximate (bi)kernel on all the aforementioned classes. Our results are in sharp contrast to the kernelization complexity of CONNECTED DOMINATING SET, which is known to not admit a polynomial kernel even on 2-degenerate graphs and graphs of bounded expansion, unless NP subset of coNP/poly. We complement our results by the following conditional lower bound. We show that if a class C is somewhere dense and closed under taking subgraphs, then for some value of r is an element of N there cannot exist an alpha-approximate bi-kernel for the (CONNECTED) DISTANCE-r DOMINATING SET problem on C for any alpha > 1 (assuming FPT not equal W[1]).

关键词： parameterized complexity lossy kernelization connected dominating set sparse graph classes

来源：评论

学校读者我要写书评

暂无评论

Path-contractions, edge deletions and connectivity preservation

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2019年 101卷 1-20页

作者： Gutin, Gregory Ramanujan, M. S. Reidl, Felix Wahlstrom, Magnus Univ London Royal Holloway Univ Egham Surrey England TU Wien Algorithms & Complex Grp Vienna Austria Univ Warwick Coventry W Midlands England

We study several problems related to graph modification under connectivity constraints from the perspective of parameterized complexity. In particular, we study (a) (Weighted) Biconnectivity Deletion, where we are tasked with deleting k edges while preserving biconnectivity in an undirected graph, and (b) Path-contraction Preserving Strong Connectivity, where we want to maintain strong connectivity of a digraph while path-contracting k arcs. The parameterized tractability of this last problem was posed in Bang-Jensen and Yeo (2008) [1] as an open question and we answer it here in the negative. On the other hand, we show that preserving (weighted) biconnectivity is fixed-parameter tractable (FPT) and the unweighted case even admits a randomized polynomial kernel. Finally, we show that the most general case of the (unweighted) problem where one would like to preserve rho-vertex connectivity for any rho is (non-uniformly) FPT parameterized by k and rho. (C) 2018 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Graph connectivity Vertex deletion Path contraction

来源：评论

学校读者我要写书评

暂无评论

parameterized dichotomy of choosing committees based on approval votes in the presence of outliers

引用

THEORETICAL COMPUTER SCIENCE 2019年第0期783卷 53-70页

作者： Dey, Palash Misra, Neeldhara Narahari, Y. Indian Inst Technol Kharagpur W Bengal India Indian Inst Technol Gandhinagar India Indian Inst Sci Bangalore Karnataka India

Approval voting provides an opportunity for the agents to make a comment about every candidate, without incurring the overhead of determining a full ranking on the entire set of candidates. This makes approval voting a natural choice for many practical applications. In this work, we focus on the use of approval voting for selecting a committee in scenarios where we can have few outrageous voters whom we call outliers. More specifically, we study the computational complexity of the committee selection problem for commonly used 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). Our main contribution in this paper is dichotomous results, which establish the parameterized complexity of the problem of selecting a committee under approval, net approval, and minisum approval voting rules for all subsets of the above five parameters considered here (by showing either FPT or W[1]-hardness for all subsets of parameters). (C) 2019 Elsevier B.V. All rights reserved.

关键词： Voting Approval ballot Committee selection Outliers parameterized complexity parameterized dichotomy

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized algorithm for pumpkin vertex deletion set

引用

INFORMATION PROCESSING LETTERS 2019年 147卷 74-76页

作者： Tsur, Dekel Ben Gurion Univ Negev Beer Sheva Israel

A directed graph G is called a pumpkin if G is a union of induced directed paths with a common start vertex s and a common end vertex t, and the internal vertices of every two paths are disjoint. We give an algorithm that given a directed graph G and an integer k, decides whether a pumpkin can be obtained from G by deleting at most k vertices. The algorithm runs in O*(2(k)) time. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Graph algorithms parameterized complexity Branching algorithms

来源：评论

学校读者我要写书评

暂无评论

On structural parameterizations of firefighting

引用

THEORETICAL COMPUTER SCIENCE 2019年第0期782卷 79-90页

作者： Das, Bireswar Enduri, Murali Krishna Kiyomi, Masashi Misra, Neeldhara Otachi, Yota Reddy, I. Vinod Yoshimura, Shunya IIT Gandhinagar Gandhinagar India SRM Univ Amaravati India Yokohama City Univ Yokohama Kanagawa Japan Kumamoto Univ Kumamoto Japan IIT Bhilai Sejbahar Chhattisgarh India Kyushu Univ Fukuoka Fukuoka Japan

The FIREFIGHTING problem is defined as follows. At time t = 0, a fire breaks out at a vertex of a graph. At each time step t >= 1, a firefighter permanently defends (protects) an unburned vertex, and the fire then spreads to all undefended neighbors from the vertices on fire. This process stops when the fire cannot spread anymore. The goal is to find a sequence of vertices for the firefighter that maximizes the number of saved (non burned) vertices. The FIREFIGHTING problem turns out to be NP-hard even when restricted to bipartite graphs or trees of maximum degree three. We study the parameterized complexity of the FIREFIGHTING problem for various structural parameterizations. All our parameters measure the distance to a graph class (in terms of vertex deletion) on which the FIREFIGHTING problem admits a polynomial-time algorithm. To begin with, we show that the problem is W[1]-hard when parameterized by the size of a modulator to diameter at most two graphs and split graphs. In contrast to the above intractability results, we show that FIREFIGHTING is fixed parameter tractable (FPT) when parameterized by the size of a modulator to cographs, threshold graphs and disjoint unions of stars. We further investigate the kernelization complexity of the problem and show that it does not admit a polynomial kernel when parameterized by the size of a modulator to a disjoint union of stars under some complexity-theoretic assumptions. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Firefighting parameterized complexity NP-complete Kemelization

来源：评论

学校读者我要写书评

暂无评论

complexity and approximability of extended Spanning Star Forest problems in general and complete graphs

引用

THEORETICAL COMPUTER SCIENCE 2019年 775卷 1-15页

作者： Khoshkhah, Kaveh Ghadikolaei, Mehdi Khosravian Monnot, Jerome Theis, Dirk Oliver Tartu Univ Inst Comp Sci Tartu Estonia Univ Paris 09 PSL Res Univ CNRS UMR 7243 LAMSADE F-75016 Paris France

A solution extension problem consists in an instance and a partial feasible solution which is given in advance and the goal is to extend this partial solution to a feasible one. Many well-known problems like Coloring Extension Problems, Traveling Salesman Problem and Routing problems, have been studied in this framework. In this paper, we focus on the edge-weighted spanning star forest problem for both minimization and maximization versions. The goal here is to find a vertex partition of an edge-weighted graph into disjoint non-trivial stars and the value of a solution is given by the sum of the edge-weights of the stars. We propose NP-hardness, parameterized complexity, positive and negative approximation results. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Computational complexity parameterized complexity Approximation algorithms Graphs Extended solution Spanning Star Forest

来源：评论

学校读者我要写书评

暂无评论

On approximate preprocessing for domination and hitting subgraphs with connected deletion sets

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2019年第0期105卷 158-170页

作者： Eiben, Eduard Hermelin, Danny Ramanujan, M. S. Univ Bergen Bergen Norway Ben Gurion Univ Negev Beer Sheva Israel Univ Warwick Coventry W Midlands England

In this paper, we study the CONNECTED H-HITTING SET and DOMINATING SET problems from the perspective of approximate kernelization, a framework recently introduced by Lokshtanov et al. [STOC 2017]. For the CONNECTED H-HITTING SET problem, we obtain an alpha-approximate kernel for every alpha > 1 and complement it with a lower bound for the natural weighted version. We then perform a refined analysis of the tradeoff between the approximation factor and kernel size for the DOMINATING SET problem on d-degenerate graphs, and provide an interpolation of approximate kernels between the known 3d-approximate kernel of constant size and 1-approximate kernel of size k(O(d2)). (C) 2019 Published by Elsevier Inc.

关键词： parameterized complexity Kemelization Vertex deletion problems

来源：评论

学校读者我要写书评

暂无评论

PACKING CYCLES FASTER THAN ERDOS-POSA

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2019年第3期33卷 1194-1215页

作者： Lokshtanov, Daniel Mouawad, Amer E. Saurabh, Saket Zehavi, Meirav Univ Bergen Bergen Norway Amer Univ Beirut Beirut Lebanon HBNI Inst Mathmat Sci Mumbai Maharashtra India Ben Gurion Univ Negev Beer Sheva Israel

The CYCLE PACKING problem asks whether a given undirected graph G = (V, E) contains k vertex-disjoint cycles. Since the publication of the classic Erdos-Posa theorem in 1965, this problem received significant attention in the fields of graph theory and algorithm design. In particular, this problem is one of the first problems studied in the framework of parameterized complexity. The nonuniform fixed-parameter tractability of CYCLE PACKING follows from the Robertson-Seymour theorem, a fact already observed by Fellows and Langston in the 1980s. In 1994, Bodlaender showed that CYCLE PACKING can be solved in time 2(O(k2)). vertical bar V vertical bar using exponential space. In the case a solution exists, Bodlaender's algorithm also outputs a solution (in the same time). It has later become common knowledge that CYCLE PACKING admits a 2(O(k log2 k)). vertical bar V vertical bar-time (deterministic) algorithm using exponential space, which is a consequence of the Erdos-Posa theorem. Nowadays, the design of this algorithm is given as an exercise in textbooks on parameterized complexity. Yet, no algorithm that runs in time 2(o(k log2 k)). vertical bar V vertical bar(O(1)), beating the bound 2(O(k log2 k)).vertical bar V vertical bar(O(1)), has been found. In light of this, it seems natural to ask whether the 2(O(k log2 k)).( )vertical bar V vertical bar(O(1)) bound is essentially optimal. In of this paper, we answer this question negatively by developing a 2(O)(k log(2) k/log log k).vertical bar V vertical bar-time (deterministic) algorithm for CYCLE PACKING. In the case a solution exists, our algorithm also outputs a solution (in the same time). Moreover, apart from beating the bound 2(O(k log2 k)).vertical bar V vertical bar(O(1)), our algorithm runs in time linear in vertical bar V vertical bar, and its space complexity is polynomial in the input size.

关键词： parameterized complexity graph algorithms cycle packing Erdos-Posa theorem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：