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

Subset Feedback Vertex Set in Chordal and Split Graphs

ALGORITHMICA 2019年第9期81卷 3586-3629页

作者： Philip, Geevarghese Rajan, Varun Saurabh, Saket Tale, Prafullkumar Chennai Math Inst Chennai Tamil Nadu India UMI ReLaX Chennai Tamil Nadu India HBNI Inst Math Sci Chennai Tamil Nadu India Univ Bergen Dept Informat Bergen Norway

In the Subset Feedback Vertex Set (Subset-FVS) problem the input is a graph G on n vertices, a subset T of vertices of G called the "terminal" vertices, and an integer k. The task is to determine whether there exists a subset of vertices of cardinality at most k which together intersect all cycles which pass through the terminals. Subset-FVS generalizes several well studied problems including Feedback Vertex Set and Multiway Cut. This problem is known to be NP-Complete, even in split graphs. Cygan et al. (SIAM J Discrete Math 27(1):290-309, 2013) proved that Subset-FVS is fixed parameter tractable in general graphs when parameterized by k. In split graphs a simple observation reduces the problem to an equivalent instance of the 3-Hitting Set problem with the same solution size. This directly implies, for Subset-FVS restricted to split graphs, (i) an FPT algorithm which solves the problem inO (2.076k) time (TheO () notation hides polynomial factors.) (Wahlstrom inAlgorithms, measures and upper bounds for satisfiability and related problems. Ph. D. Thesis, Department of Computer and Information Science, Linkopings universitet, 2007), and (ii) a kernel of sizeO(k3). We improve both these results for Subset-FVS on split graphs;we derive (i) a kernel of size O(k2) which is the best possible unless NP. coNP/ poly, and (ii) an algorithm which solves the problem in time O* (2k). Our algorithm, in fact, solves Subset-FVS on the more general class of chordal graphs, also in O* (2k) time. To the best of our knowledge, the fastest known exact algorithm for Subset- FVS on chordal graphs is based on the 3-Hitting Set algorithm of Fomin et al. (JACM66(2): 8, 2019) which runs inO* (1.5182n) time. Applying the results of Fomin et al. (2019) to our FPT algorithm yields two exact exponential-time algorithms for Subset-FVS on chordal graphs: a randomized algorithmwhich runs inO* (1.5n) time, and a deterministic algorithm which runs in O* ((1.5+ e) n) time for any fixed epsilon > O.

关键词： Subset feedback vertex set Chordal and split graphs parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity of Stabbing Rectangles

引用

ALGORITHMICA 2012年第1-2期62卷 564-594页

作者： Dom, Michael Fellows, Michael R. Rosamond, Frances A. Sikdar, Somnath Rhein Westfal TH Aachen Dept Comp Sci D-52074 Aachen Germany Univ Jena Inst Informat D-07743 Jena Germany Charles Darwin Univ Sch Engn & Informat Technol Darwin NT 0909 Australia

The NP-complete geometric covering problem Rectangle Stabbing is defined as follows: Given a set R of axis-parallel rectangles in the plane, a set L of horizontal and vertical lines in the plane, and a positive integer k, select at most k of the lines such that every rectangle is intersected by at least one of the selected lines. While it is known that the problem can be approximated in polynomial time within a factor of two, its parameterized complexity with respect to the parameter k was open so far. Giving two fixed-parameter reductions, one from the W[1]-complete problem Multicolored Clique and one to the W[1]-complete problem Short Turing Machine Acceptance, we prove that Rectangle Stabbing is W[1]-complete with respect to the parameter k, which in particular means that there is no hope for an algorithm running in f(k)a <...|(RaL)-L-a| (O(1)) time. Our reductions also show the W[1]-completeness of the more general problem Set Cover on instances that "almost have the consecutive-ones property", that is, on instances whose matrix representation has at most two blocks of 1s per row. We also show that the special case of Rectangle Stabbing where all rectangles are squares of the same size is W[1]-hard. The case where the input consists of non-overlapping rectangles was open for some time and has recently been shown to be fixed-parameter tractable (Heggernes et al., Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing, 2009). By giving an algorithm running in (2k) (k) a <...|(RaL)-L-a| (O(1)) time, we show that Rectangle Stabbing is fixed-parameter tractable in the still NP-hard case where both these restrictions apply, that is, in the case of disjoint squares of the same size. This algorithm is faster than the one in Heggernes et al. (Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing, 2009) for the disjoint rectangles case. Moreover, we show fixed-parameter tractability for the restrictions where the rect

关键词： parameterized complexity Fixed-parameter algorithms Geometric covering problems Whardness

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of the repetition free longest common subsequence problem

引用

INFORMATION PROCESSING LETTERS 2012年第7期112卷 272-276页

作者： Blin, Guillaume Bonizzoni, Paola Dondi, Riccardo Sikora, Florian Univ Bergamo Dipartimento Sci Linguaggi Comunicaz & Culturali I-24129 Bergamo Italy Univ Paris Est LIGM UMR CNRS 8049 Paris France Univ Milano Bicocca DISCo Milan Italy Univ Jena Lehrstuhl Bioinformat D-6900 Jena Germany

Longest common subsequence is a widely used measure to compare strings, in particular in computational biology. Recently, several variants of the longest common subsequence have been introduced to tackle the comparison of genomes. In particular, the Repetition Free Longest Common Subsequence (RFLCS) problem is a variant of the LCS problem that asks for a longest common subsequence of two input strings with no repetition of symbols. In this paper, we investigate the parameterized complexity of RFLCS. First, we show that the problem does not admit a polynomial kernel. Then, we present a randomized FPT algorithm for the RFLCS problem, improving the time complexity of the existent FPT algorithm. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Algorithms Combinatorial problems Repetition free longest common subsequence Longest common subsequence parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Preserving Consistency for Liquid Knapsack Voting 21

Preserving Consistency for Liquid Knapsack Voting

引用

Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems

作者： Pallavi Jain Krzysztof Sornat Nimrod Talmon Indian Institute of Technology Jodhupar Jodhpur India Massachusetts Institute of Technology Cambridge MA USA Ben-Gurion University of the Negev Be'er-Sheva Israel

ISBN: (纸本)9781450383073

Liquid Democracy (LD) uses transitive delegations in voting. In its simplest form, it is used for binary decisions, however its promise holds also for more advanced voting settings. Here we consider LD in the context of Participatory Budgeting (PB), which is a direct democracy approach to budgeting, most usually done in municipal budgeting processes. In particular, we study Knapsack Voting, in which PB voters approve projects, such that the sum of costs of projects each voter approves must respect the budget limit. We observe possible inconsistencies, as the cost of voter-approved projects may go over the budget limit after resolving delegations. We offer ways to overcome them by studying the computational complexity of updating as few delegations as possible to arrive---after following all project delegations---to a consistent profile.

关键词： parameterized complexity knapsack voting liquid democracy participatory budgeting

来源：评论

学校读者我要写书评

暂无评论

How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?

引用

ALGORITHMICA 2019年第10期81卷 4043-4068页

作者： Bougeret, Marin Sau, Ignasi Univ Montpellier LIRMM Montpellier France CNRS LIRMM Montpellier France Univ Fed Ceara Dept Matemat Fortaleza Ceara Brazil

In the last years, kernelization with structural parameters has been an active area of research within the field of parameterized complexity. As a relevant example, Gajarsky et al. (J Comput Syst Sci 84:219-242, 2017) proved that every graph problem satisfying a property called finite integer index admits a linear kernel on graphs of bounded expansion and an almost linear kernel on nowhere dense graphs, parameterized by the size of a c-treedepth modulator, which is a vertex set whose removal results in a graph of treedepth at most c, where c >= 1 is a fixed integer. The authors left as further research to investigate this parameter on general graphs, and in particular to find problems that, while admitting polynomial kernels on sparse graphs, behave differently on general graphs. In this article we answer this question by finding two very natural such problems: we prove that VERTEX COVER admits a polynomial kernel on general graphs for any integer c >= 1, and that DOMINATING SET does not for any integer c >= 2 even on degenerate graphs, unless NP subset of coNP/poly. For the positive result, we build on the techniques of Jansen and Bodlaender (Proceedings of the 28th symposium on theoretical aspects of computer science (STACS), volume 9 of LIPIcs, pp 177-188, 2011), and for the negative result we use a polynomial parameter transformation for c >= 3 and an or-cross-composition for c = 2. As existing results imply that DOMINATING SET admits a polynomial kernel on degenerate graphs for c = 1, our result provides a dichotomy about the existence of polynomial kernels for DOMINATING SET on degenerate graphs with this parameter.

关键词： parameterized complexity Polynomial kernels Structural parameters Treedepth Treewidth Sparse graphs

来源：评论

学校读者我要写书评

暂无评论

Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality is the Key to Single-Exponential parameterized Algorithms

引用

ALGORITHMICA 2019年第10期81卷 3890-3935页

作者： Bonnet, Edouard Brettell, Nick Kwon, O-joung Marx, Daniel Univ Claude Bernard Lyon 1 Univ Lyon CNRS ENS LyonLIP UMR5668 Lyon France Eindhoven Univ Technol Dept Math & Comp Sci Eindhoven Netherlands Incheon Natl Univ Dept Math Incheon South Korea Hungarian Acad Sci MTA SZTAKI Inst Comp Sci & Control Budapest Hungary

It has long been known that Feedback Vertex Set can be solved in time 2 O-(w log w) n(O(1)) on n-vertex graphs of treewidth w, but it was only recently that this running time was improved to 2(O(w))n(O(1)), that is, to single-exponential parameterized by treewidth. We investigate which generalizations of Feedback Vertex Set can be solved in a similar running time. Formally, for a class P of graphs, the Bounded P-Block Vertex Deletion problem asks, given a graph G on n vertices and positive integers k and d, whether G contains a set S of at most k vertices such that each block of G -S has at most d vertices and is in P. Assuming that P is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of d: - if P consists only of chordal graphs, then the problem can be solved in time 2(O(wd2))n(O(1)), - if P contains a graph with an induced cycle of length l >= 4, then the problem is not solvable in time 2(o(w log w))n(O(1)) even for fixed d = l, unless the ETH fails. We also study a similar problem, called Bounded P-Component Vertex Deletion, where the target graphs have connected components of small size rather than blocks of small size, and we present analogous results. For this problem, we also show that if d is part of the input and P contains all chordal graphs, then it cannot be solved in time f(w)n(o(w)) for some function f, unless the ETH fails.

关键词： parameterized complexity Feedback Vertex Set Treewidth Chordal graph

来源：评论

学校读者我要写书评

暂无评论

Track Layouts, Layered Path Decompositions, and Leveled Planarity

引用

ALGORITHMICA 2019年第4期81卷 1561-1583页

作者： Bannister, Michael J. Devanny, William E. Dujmovic, Vida Eppstein, David Wood, David R. Pinterest 808 Brannan St San Francisco CA 94103 USA Univ Calif Irvine Dept Comp Sci Irvine CA USA Univ Ottawa Sch Comp Sci & Elect Engn Ottawa ON Canada Monash Univ Sch Math Sci Melbourne Vic Australia

We investigate two types of graph layouts, track layouts and layered path decompositions, and the relations between their associated parameters track-number and layered pathwidth. We use these two types of layouts to characterize leveled planar graphs, which are the graphs with planar leveled drawings with no dummy vertices. It follows from the known NP-completeness of leveled planarity that track-number and layered pathwidth are also NP-complete, even for the smallest constant parameter values that make these parameters nontrivial. We prove that the graphs with bounded layered pathwidth include outerplanar graphs, Halin graphs, and squaregraphs, but that (despite having bounded track-number) series-parallel graphs do not have bounded layered pathwidth. Finally, we investigate the parameterized complexity of these layouts, showing that past methods used for book layouts do not work to parameterize the problem by treewidth or almost-tree number but that the problem is (non-uniformly) fixed-parameter tractable for tree-depth.

关键词： Track layouts Layered path decompositions Track-number Layered pathwidth Leveled planar graphs Outerplanar graphs Halin graphs Squaregraphs Unit disc graphs parameterized complexity Treewidth Almost-tree number Tree-depth

来源：评论

学校读者我要写书评

暂无评论

parameterized Algorithms for List K-Cycle

引用

ALGORITHMICA 2019年第3期81卷 1267-1287页

作者： Panolan, Fahad Saurabh, Saket Zehavi, Meirav Univ Bergen Dept Informat Bergen Norway HBNI Inst Math Sci Chennai Tamil Nadu India

The classic K-Cycle problem asks if a graph G, with vertex-set V(G), has a simple cycle containing all vertices of a given set KV(G). In terms of colored graphs, it can be rephrased as follows: Given a graph G, a set KV(G) and an injective coloring c:K{1,2,...,|K|}, decide if G has a simple cycle containing each color in {1,2,...,|K|} exactly once. Another problem widely known since the introduction of color coding is Colorful Cycle. Given a graph G and a coloring c:V(G){1,2,...,k} for some kN, it asks if G has a simple cycle of length k containing each color in {1,2,...,k} exactly once. We study a generalization of these problems: Given a graph G, a set KV(G), a list-coloring L:K2{1,2,...,k} for some kN and a parameter kN, ListK-Cycle asks if one can assign a color to each vertex in K so that G has a simple cycle (of arbitrary length) containing exactly k vertices from K with distinct colors. We design a randomized algorithm for ListK-Cycle running in time 2knO(1) on an n-vertex graph, matching the best known running times of algorithms for both K-Cycle and Colorful Cycle. Moreover, unless the Set Cover Conjecture is false, our algorithm is essentially optimal. We also study a variant of ListK-Cycle that generalizes the classic Hamiltonicity problem, where one specifies the size of a solution. Our results integrate three related algebraic approaches, introduced by Bjorklund, Husfeldt and Taslaman (SODA'12), Bjorklund, Kaski and Kowalik (STACS'13), and Bjorklund (FOCS'10).

关键词： parameterized complexity K-cycle Colorful path k-path

来源：评论

学校读者我要写书评

暂无评论

Weighted proper orientations of trees and graphs of bounded treewidth

引用

THEORETICAL COMPUTER SCIENCE 2019年 771卷 39-48页

作者： Araujo, Julio Sales, Claudia Linhares Sau, Ignasi Silva, Ana Univ Fed Ceara Dept Matemat Fortaleza Ceara Brazil Univ Fed Ceara Dept Comp Fortaleza Ceara Brazil Univ Montpellier CNRS LIRMM Montpellier France

Given a simple graph G, a weight function w : E (G) -> N \ (0), and an orientation D of G, we define mu(-)(D) = max(vev(G)) w(D)(-)(v), where w(D)(-)(v) = Sigma(-)(mu is an element of ND)(v)w(uv). We say that D is a weighted proper orientation of G if w(D)(-)(u) not equal w(D)(-),(v) whenever u and v are adjacent. We introduce the parameter weighted proper orientation number of G, denoted by (X) over right arrow (G, w), which is the minimum, over all weighted proper orientations D of G, of mu(-) (D). When all the weights are equal to 1, this parameter is equal to the proper orientation number of G, which has been object of recent studies and whose determination is NP -hard in general, but polynomial -time solvable on trees. Here, we prove that the equivalent decision problem of the weighted proper orientation number (i.e., (X) over right arrow (G, w) <= k?) is (weakly) NP -complete on trees but can be solved by a pseudo -polynomial time algorithm whose running time depends on k. Furthermore, we present a dynamic programming algorithm to determine whether a general graph G on n vertices and treewidth at most tw satisfies (X) over right arrow (G, w) <= k, running in time O(2t(w2) . k(3tw) . tw n), and we complement this result by showing that the problem is W[11 -hard on general graphs parameterized by the treewidth of G, even if the weights are polynomial in n. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Proper orientation number Weighted proper orientation number Minimum maximum indegree Trees Treewidth parameterized complexity W[1]-hardness

来源：评论

学校读者我要写书评

暂无评论

Knapsack problems: A parameterized point of view

引用

THEORETICAL COMPUTER SCIENCE 2019年 775卷 93-108页

作者： Gurski, Frank Rehs, Carolin Rethmann, Jochen Heinrich Heine Univ Dusseldorf Inst Comp Sci D-40225 Dusseldorf Germany Niederrhein Univ Appl Sci Fac Elect Engn & Comp Sci D-47805 Krefeld Germany

The knapsack problem (KP) is a very famous NP-hard problem in combinatorial optimization. Also its generalization to multiple dimensions named d-dimensional knapsack problem (d-KP) and to multiple knapsacks named multiple knapsack problem (MKP) are well known problems. In this paper we give a first study on the fixed-parameter tractability of these three problems. The idea behind fixed-parameter tractability is to split the complexity into two parts - one part that depends purely on the size of the input and one part that depends on some parameter of the problem that tends to be small in practice. Further we consider the closely related question, whether the sizes and the values can be reduced, such that their bit-length is bounded polynomially or even constantly in a given parameter, i.e. the existence of kernelizations is studied. We give several upper and some lower bounds on the parameterized complexity and kernel sizes for the following parameters: the number of items, the threshold value for the profit, the sizes, the profits, the number d of dimensions, and the number m of knapsacks. We also consider the connection of parameterized knapsack problems to linear programming, approximation, and pseudo-polynomial algorithms. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Knapsack problem d-Dimensional knapsack problem Multiple knapsack problem parameterized complexity Kernelization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：