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

Faster algorithms for finding and counting subgraphs

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2012年第3期78卷 698-706页

作者： Fomin, Fedor V. Lokshtanov, Daniel Raman, Venkatesh Saurabh, Saket Rao, B. V. Raghavendra Univ Bergen Dept Informat N-5008 Bergen Norway Inst Math Sci Madras 600113 Tamil Nadu India Univ Saarland Dept Comp Sci D-6600 Saarbrucken Germany

In the SUBGRAPH ISOMORPHISM problem we are given two graphs F and G on k and n vertices respectively as an input, and the question is whether there exists a subgraph of G isomorphic to F. We show that if the treewidth of F is at most t, then there is a randomized algorithm for the SUBGRAPH ISOMORPHISM problem running in time O*(2(k)(n(2t)). Our proof is based on a novel construction of an arithmetic circuit of size at most n(O)(t) for a new multivariate polynomial, Homomorphism Polynomial, of degree at most k, which in turn is used to solve the SUBGRAPH ISOMORPHISM problem. For the counting version of the SUBGRAPH ISOMORPHISM problem, where the objective is to count the number of distinct subgraphs of G that are isomorphic to F, we give a deterministic algorithm running oki in time and space O*(((n)(k/2))n(2p)) or ((n)(k/2))nO((tlogk)). We also give an algorithm running in time O*(2(k)((n)(k/2))n(5p)) and taking O*(n(p)) space. Here p and t denote the pathwidth and the treewidth of F, respectively. Our work improves on the previous results on SUBGRAPH ISOMORPHISM, it also extends and unifies most of the known results on sub-path and sub-tree isomorphisms. (C) 2011 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Subgraph Isomorphism Homomorphism Counting Treewidth

来源：评论

学校读者我要写书评

暂无评论

Polynomial Kernel for Interval Vertex Deletion

引用

ACM TRANSACTIONS ON ALGORITHMS 2023年第2期19卷 1-68页

作者： Agrawal, Akanksha Lokshtanov, Daniel Misra, Pranabendu Saurabh, Saket Zehavi, Meirav Indian Inst Technol Madras Chennai Tamil Nadu India Univ Calif Santa Barbara Santa Barbara CA 93106 USA Chennai Math Inst Chennai Tamil Nadu India Homi Bhabha Natl Inst Chennai Tamil Nadu India Univ Bergen Bergen Norway Ben Gurion Univ Negev Beer Sheva Israel

Given a graph G and an integer k, the Interval Vertex Deletion (IVD) problem asks whether there exists a subset S subset of V (G) of size at most k such that G - S is an interval graph. This problem is known to be NP-complete (according to Yannakakis at STOC 1978). Originally in 2012, Cao and Marx showed that IVD is fixed parameter tractable: they exhibited an algorithm with running time 10(k)n(O)(1). The existence of a polynomial kernel for IVD remained a well-known open problem in parameterized complexity. In this article, we settle this problem in the affirmative.

关键词： Interval Vertex Deletion kernelization polynomial kernel parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the complexity of finding common approximate substrings

引用

THEORETICAL COMPUTER SCIENCE 2003年第1-3期306卷 407-430页

作者： Evans, PA Smith, AD Wareham, HT Univ New Brunswick Fac Comp Sci Fredericton NB E3B 5A3 Canada Mem Univ Newfoundland Dept Comp Sci St John NF A1B 3X5 Canada

Problems associated with finding strings that are within a specified Hamming distance of a given set of strings occur in several disciplines. In this paper, we use techniques from parameterized complexity to assess non-polynomial time algorithmic options and complexity for the COMMON APPROXIMATE SUBSTRING (CAS) problem. Our analyses indicate under which parameter restrictions useful algorithms are possible, and include both class membership and parameterized reductions to prove class hardness. In order to achieve fixed-parameter tractability, either a fixed string length or both a fixed size alphabet and fixed substring length are sufficient. Fixing either the string length or the alphabet size and Hamming distance is shown to be necessary, unless W[I] = FPT. An assortment of parameterized class membership and hardness results cover all other parameterized variants, showing in particular the effect of fixing the number of strings. (C) 2003 Elsevier B.V. All rights reserved.

关键词： parameterized complexity pattern matching common approximate substring

来源：评论

学校读者我要写书评

暂无评论

A refined complexity analysis of degree anonymization in graphs

引用

INFORMATION AND COMPUTATION 2015年 243卷 249-262页

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

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

来源：评论

学校读者我要写书评

暂无评论

Tractable cases of the extended global cardinality constraint

引用

CONSTRAINTS 2011年第1期16卷 1-24页

作者： Samer, Marko Szeider, Stefan Tech Univ Darmstadt Dept Comp Sci Darmstadt Germany Univ Durham Dept Comp Sci Durham England

We study the consistency and domain consistency problem for extended global cardinality (EGC) constraints. An EGC constraint consists of a set X of variables, a set D of values, a domain D(x) subset of D for each variable x, and a "cardinality set" K(d) of non-negative integers for each value d. The problem is to instantiate each variable x with a value in D(x) such that for each value d, the number of variables instantiated with d belongs to the cardinality set K(d). It is known that this problem is NP-complete in general, but solvable in polynomial time if all cardinality sets are intervals. First we pinpoint connections between EGC constraints and general factors in graphs. This allows us to extend the known polynomial-time case to certain non-interval cardinality sets. Second we consider EGC constraints under restrictions in terms of the treewidth of the value graph (the bipartite graph representing variable-value pairs) and the cardinality-width (the largest integer occurring in the cardinality sets). We show that EGC constraints can be solved in polynomial time for instances of bounded treewidth, where the order of the polynomial depends on the treewidth. We show that (subject to the complexity theoretic assumption FPT not equal W[1]) this dependency cannot be avoided without imposing additional restrictions. If, however, also the cardinality-width is bounded, this dependency gets removed and EGC constraints can be solved in linear time.

关键词： Global constraints General factor problem Domain consistency Bounded treewidth parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

High-multiplicity scheduling on one machine with forbidden start and completion times

引用

JOURNAL OF SCHEDULING 2016年第5期19卷 609-616页

作者： Gabay, Michael Rapine, Christophe Brauner, Nadia Univ Grenoble Alpes G SCOP F-38000 Grenoble France CNRS G SCOP F-38000 Grenoble France Univ Lorraine Lab LGIPM Ile Saulcy F-57045 Metz France

We are interested in a single machine scheduling problem where jobs can neither start nor end on some specified instants, and the aim is to minimize the makespan. This problem models the situation where an additional resource, subject to unavailability constraints, is required to start and to finish a job. We consider in this paper the high-multiplicity version of the problem, when the input is given using a compact encoding. We present a polynomial time algorithm for large diversity instances (when the number of different processing times is greater than the number of forbidden instants). We also show that this problem is fixed-parameter tractable when the number of forbidden instants is fixed, regardless of jobs characteristics.

关键词： Scheduling High-multiplicity Availability constraints parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

When Can Graph Hyperbolicity be Computed in Linear Time?

引用

ALGORITHMICA 2019年第5期81卷 2016-2045页

作者： Fluschnik, Till Komusiewicz, Christian Mertzios, George B. Nichterlein, Andre Niedermeier, Rolf Talmon, Nimrod TU Berlin Fak 4 Algorithm & Computat Complex Berlin Germany Philipps Univ Marburg Fachbereich Math & Informat Marburg Germany Univ Durham Dept Comp Sci Durham England Ben Gurion Univ Negev Beer Sheva Israel

Hyperbolicity is a distance-based measure of how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen intensive research over the last years. Unfortunately, the best known algorithms used in practice for computing the hyperbolicity number of an n-vertex graph have running time O(n(4)). Exploiting the framework of parameterized complexity analysis, we explore possibilities for "linear-time FPT" algorithms to compute hyperbolicity. For example, we show that hyperbolicity can be computed in 2(O(k)) + O(n + m) time (where m and k denote the number of edges and the size of a vertex cover in the input graph, respectively) while at the same time, unless the Strong Exponential Time Hypothesis (SETH) fails, there is no 2(o(k)) . n(2-epsilon)-time algorithm for every epsilon > 0.

关键词： parameterized complexity Polynomial-time algorithm FPT in P Strong Exponential Time Hypothesis Vertex cover number Cographs

来源：评论

学校读者我要写书评

暂无评论

Counting Linear Extensions: Parameterizations by Treewidth

引用

ALGORITHMICA 2019年第4期81卷 1657-1683页

作者： Eiben, E. Ganian, R. Kangas, K. Ordyniak, S. Univ Bergen Dept Informat Bergen Norway TU Wien Algorithms & Complex Grp Vienna Austria Univ Helsinki Helsinki Inst Informat Technol Helsinki Finland Univ Sheffield Dept Comp Sci Sheffield S Yorkshire England

We consider the #P-complete problem of counting the number of linear extensions of a poset (LE is fixed-parameter intractable parameterized by the treewidth of the cover graph. This resolves an open problem recently p... 详细信息

We consider the #P-complete problem of counting the number of linear extensions of a poset (complexity of parameterized by the well-known decompositional parameter treewidth for two natural graphical representations of the input poset, i.e., the cover and the incomparability graph. Our main result shows that <>LE is fixed-parameter intractable parameterized by the treewidth of the cover graph. This resolves an open problem recently posed in the Dagstuhl seminar on Exact Algorithms. On the positive side we show that <>LE becomes fixed-parameter tractable parameterized by the treewidth of the incomparability graph.

关键词： Partially ordered sets Linear extensions parameterized complexity Structural parameters Treewidth

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

1.5D terrain guarding problem parameterized by guard range

引用

THEORETICAL COMPUTER SCIENCE 2017年 661卷 65-69页

作者： Khodakarami, Farnoosh Didehvar, Farzad Mohades, Ali Amirkabir Univ Technol Dept Math & Comp Sci Lab Algorithms & Computat Geometry Tehran Iran

The 1.5D terrain guarding problem examines a 1.5D terrain as an x-monotone polygonal chain in a plane to find the minimum guarding set for a given input terrain. This problem is NP-complete. In real world applications, guard power is limited and can only cover things within a range. Considering this limitation, the present study introduces the "terrain guard range" as a new geometric parameter by discretizing the definition of range, then presents a fixed-parameter algorithm to demonstrate that the 1.5D terrain guarding problem is fixed-parameter tractable with respect to the introduced parameter. (C) 2016 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Dynamic programming Guarding 1.5D terrain

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：