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

Univariate Ideal Membership parameterized by Rank, Degree, and Number of Generators

THEORY OF COMPUTING SYSTEMS 2022年第1期66卷 56-88页

作者： Arvind, V Chatterjee, Abhranil Datta, Rajit Mukhopadhyay, Partha Inst Math Sci HBNI Chennai Tamil Nadu India Chennai Math Inst Chennai Tamil Nadu India

Let F[X] be the polynomial ring in the variables X = {x(1), x(2), ..., x(n)} over a field F. An ideal I = generated by univariate polynomials {p(i)(x(i))}(i=1)(n) is a univariate ideal. Motivated by Alon's Combin... 详细信息

Let F[X] be the polynomial ring in the variables X = {x(1), x(2), ..., x(n)} over a field F. An ideal I = < p(1)(x(1)),..., p(n)(x(n))> generated by univariate polynomials {p(i)(x(i))}(i=1)(n) is a univariate ideal. Motivated by Alon's Combinatorial Nullstellensatz we study the complexity of univariate ideal membership: Given f is an element of F[X] by a circuit and polynomials p(i) the problem is test if f is an element of I. We obtain the following results. Suppose f is a degree-d, rank-r polynomial given by an arithmetic circuit where l(i) : 1 <= i <= r are linear forms in X. We give a deterministic time d(O(r)) . poly(n) division algorithm for evaluating the (unique) remainder polynomial f (X) mod I at any point (a) over right arrow is an element of F-n. This yields a randomized n(O(r)) algorithm for minimum vertex cover in graphs with rank-r adjacency matrices. It also yields a new n(O(r)) algorithm for evaluating the permanent of a nxn matrix of rank r, over any field F. Let f be over rationals with deg(f) = k treated as fixed parameter. When the ideal I = < x(1)(e1) ,..., x(n)(en)>, we can test ideal membership in randomized O* ((2e)(k)). On the other hand, if each p(i) has all distinct rational roots we can check if f is an element of I in randomized O * (n(k/2)) time, improving on the brute-force ((k) (n + k))-time search. If I = < p(1)(x(1)),..., p(k)(x(k))>, with k as fixed parameter, then ideal membership testing is W[2]-hard. The problem is MINI[1]-hard in the special case when I = < x(1)(e1),..., x(k)(ek)>.

关键词： Ideal membership Algorithms parameterized complexity Combinatorial Nullstellensatz

来源：评论

学校读者我要写书评

暂无评论

Finding Disjoint Paths in Split Graphs

引用

THEORY OF COMPUTING SYSTEMS 2015年第1期57卷 140-159页

作者： Heggernes, Pinar Van't Hof, Pim van Leeuwen, Erik Jan Saei, Reza Univ Bergen Dept Informat N-5020 Bergen Norway MPI Informat D-66123 Saarbrucken Germany

The well-known DISJOINT PATHS problem takes as input a graph G and a set of k pairs of terminals in G, and the task is to decide whether there exists a collection of k pairwise vertex-disjoint paths in G such that the vertices in each terminal pair are connected to each other by one of the paths. This problem is known to be NP-complete, even when restricted to planar graphs or interval graphs. Moreover, although the problem is fixed-parameter tractable when parameterized by k due to a celebrated result by Robertson and Seymour, it is known not to admit a polynomial kernel unless NP subset of coNP/poly. We prove that DISJOINT PATHS remains NP-complete on split graphs, and show that the problem admits a kernel with O(k(2)) vertices when restricted to this graph class. We furthermore prove that, on split graphs, the edge-disjoint variant of the problem is also NP-complete and admits a kernel with O(k(3)) vertices. To the best of our knowledge, our kernelization results are the first non-trivial kernelization results for these problems on graph classes.

关键词： Disjoint paths Computational complexity parameterized complexity Polynomial kernel Split graphs

来源：评论

学校读者我要写书评

暂无评论

Deciding first-order properties of locally tree-decomposable structures

引用

JOURNAL OF THE ACM 2001年第6期48卷 1184-1206页

作者： Frick, M Grohe, M Univ Freiburg Inst Math Logik D-79104 Freiburg Germany Univ Edinburgh Lab Fdn Comp Sci Edinburgh EH9 3JZ Midlothian Scotland

We introduce the concept of a class of graphs, or more generally, relational structures, being locally tree-decomposable. There are numerous examples of locally tree-decomposable classes, among them the class of planar graphs and all classes of bounded valence or of bounded tree-width, We also consider a slightly more general concept of a class of structures having bounded local tree-width. We show that for each property phi of structures that is definable in first-order logic and for each locally tree-decomposable class C of structures, there is a linear time algorithm deciding whether a given structure A is an element of C has property phi. For classes C of bounded local tree-width, we show that for every k greater than or equal to 1 there is an algorithm solving the same problem in time O(n(1+(1/k))) (where it is the cardinality of the input structure).

关键词： algorithms theory first-order logic locality model-checking parameterized complexity planar graphs query evaluation tree-width

来源：评论

学校读者我要写书评

暂无评论

Recognizing k-Clique Extendible Orderings

引用

ALGORITHMICA 2021年第11期83卷 3338-3362页

作者： Francis, Mathew Neogi, Rian Raman, Venkatesh Chennai Ctr Indian Stat Inst Chennai Tamil Nadu India HBNI Inst Math Sci Chennai Tamil Nadu India

We consider the complexity of recognizing k-clique-extendible graphs (k-C-E graphs) introduced by Spinrad (Efficient Graph Representations, AMS 2003), which are generalizations of comparability graphs. A graph is k-clique-extendible if there is an ordering of the vertices such that whenever two overlapping k-cliques A and B have k - 1 common vertices, and these common vertices appear between the two vertices a, b is an element of (A\B) boolean OR (B\A) in the ordering, there is an edge between a and b, implying that A. B is a (k + 1)-clique. Such an ordering is said to be a k-C-E ordering. These graphs arise in applications related to modelling preference relations. Recently, it has been shown that a maximum clique in such a graph can be found in n(O(k)) time [Hamburger et al. 2017] when the ordering is given. When k is 2, such graphs are precisely the well-known class of comparability graphs and when k is 3 they are called triangle-extendible graphs. It has been shown that triangle-extendible graphs appear as induced subgraphs of visibility graphs of simple polygons, and the complexity of recognizing them has been mentioned as an open problem in the literature. While comparability graphs (i.e. 2-C-E graphs) can be recognized in polynomial time, we show that recognizing k-C-E graphs is NP-hard for any fixed k >= 3 and co-NP-hard when k is part of the input. While our NP-hardness reduction for k >= 4 is from the betweenness problem, for k = 3, our reduction is an intricate one from the 3-colouring problem. We also show that the problems of determining whether a given ordering of the vertices of a graph is a k-C-E ordering, and that of finding a maximum clique in a k-C-E graph, given a k-C-E ordering, are hard for the parameterized complexity classes co-W[1] and W[1] respectively, when parameterized by k. However we show that the former is fixed-parameter tractable when parameterized by the treewidth of the graph. We also show that the dual parameterizations of all th

关键词： k-clique extendible orderings k-clique extendible graphs Comparability graphs Hardness of recognition parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Defensive alliances in graphs of bounded treewidth

引用

DISCRETE APPLIED MATHEMATICS 2018年 251卷 334-339页

作者： Bliem, Bernhard Woltran, Stefan TU Wien Vienna Austria

The DEFENSIVE ALLIANCE problem has been studied extensively during the last fifteen years, but the question whether it is FPT when parameterized by treewidth has still remained open. We show that this problem is W[1]-hard. This puts it among the few problems that are FPT when parameterized by solution size but not when parameterized by treewidth (unless FPT = W[1]). (C) 2018 Elsevier B.V. All rights reserved.

关键词： Defensive alliance Treewidth parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Improved Analysis of Highest-Degree Branching for Feedback Vertex Set

引用

ALGORITHMICA 2021年第8期83卷 2503-2520页

作者： Iwata, Yoichi Kobayashi, Yusuke Natl Inst Informat Tokyo Japan Kyoto Univ Kyoto Japan

Recent empirical evaluations of exact algorithms for Feedback Vertex Set have demonstrated the efficiency of a highest-degree branching algorithm with a degree-based pruning. In this paper, we prove that this empirically fast algorithm runs in O(3.460(k)n) time, where k is the solution size. This improves the previous best O(3.619(k)n)-time deterministic algorithm obtained by Kociumaka and Pilipczuk (Inf Process Lett 114:556-560, 2014. https://***/10.1016/***.2014.05.001).

关键词： parameterized complexity Feedback vertex set Branch and bound Measure and conquer

来源：评论

学校读者我要写书评

暂无评论

Enumerate and expand:: Improved algorithms for connected Vertex Cover and Tree Cover

引用

THEORY OF COMPUTING SYSTEMS 2008年第2期43卷 234-253页

作者： Moelle, Daniel Richter, Stefan Rossmanith, Peter Univ Aachen Rhein Westfal TH Aachen Dept Comp Sci D-5100 Aachen Germany

We present a new method of solving graph problems related to VERTEX COVER by enumerating and expanding appropriate sets of nodes. As an application, we obtain dramatically improved runtime bounds for two variants of the VERTEX COVER problem. In the case of CONNECTED VERTEX COVER, we take the upper bound from O*(6k) to O*(2.7606(k)) without large hidden factors. For TREE COVER, we show a complexity of O*(3.2361(k)), improving over the previous bound of O*((2k)(k)). In the process, faster algorithms for solving subclasses of the Steiner tree problem on graphs are investigated.

关键词： exact algorithms parameterized complexity enumerate and expand Vertex cover

来源：评论

学校读者我要写书评

暂无评论

Grundy Coloring and Friends, Half-Graphs, Bicliques

引用

ALGORITHMICA 2023年第1期85卷 1-28页

作者： Aboulker, Pierre Bonnet, Edouard Kim, Eun Jung Sikora, Florian PSL Univ DI ENS Paris France Univ Claude Bernard Lyon 1 Univ Lyon CNRS ENS LyonLIP UMR5668 Lyon France PSL Univ Univ Paris Dauphine LAMSADE CNRSUMR7243 Lyon France

The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order sigma, the smallest available color. The problem GRUNDY COLORING asks how many colors are needed for the most adversarial vertex ordering sigma, i.e., the maximum number of colors that the first-fit coloring requires over all possible vertex orderings. Since its inception by Grundy in 1939, GRUNDY COLORING has been examined for its structural and algorithmic aspects. A brute-force f (k)n(2k-1) -time algorithm for GRUNDY COLORING on general graphs is not difficult to obtain, where k is the number of colors required by the most adversarial vertex ordering. It was asked several times whether the dependency on k in the exponent of n can be avoided or reduced, and its answer seemed elusive until now. We prove that GRUNDY COLORING is W[1]-hard and the brute-force algorithm is essentially optimal under the Exponential Time Hypothesis, thus settling this question by the negative. The key ingredient in our W[1]-hardness proof is to use so-called half-graphs as a building block to transmit a color from one vertex to another. Leveraging the half-graphs, we also prove that b-CHROMATIC CORE is W[1]-hard, whose parameterized complexity was posed as an open question by Panolan et al. [JCSS '17]. A natural follow-up question is, how the parameterized complexity changes in the absence of (large) half-graphs. We establish fixed-parameter tractability on K-t,K-t-free graphs for b-CHROMATIC CORE and PARTIAL GRUNDY COLORING, making a step toward answering this question. The key combinatorial lemma underlying the tractability result might be of independent interest.

关键词： Grundy coloring parameterized complexity ETH lower bounds K-t,K-t-tree graphs Half-graphs

来源：评论

学校读者我要写书评

暂无评论

Fixed-parameter tractability, definability, and model-checking

引用

SIAM JOURNAL ON COMPUTING 2001年第1期31卷 113-145页

作者： Flum, J Grohe, M Inst Math Log D-79104 Freiburg Germany Univ Illinois Dept Math Stat & Comp Sci Chicago IL 60607 USA

In this article, we study parameterized complexity theory from the perspective of logic, or more specifically, descriptive complexity theory. We propose to consider parameterized model-checking problems for various fragments of first-order logic as generic parameterized problems and show how this approach can be useful in studying both fixed-parameter tractability and intractability. For example, we establish the equivalence between the model-checking for existential first-order logic, the homomorphism problem for relational structures, and the substructure isomorphism problem. Our main tractability result shows that model-checking for first-order formulas is fixed-parameter tractable when restricted to a class of input structures with an excluded minor. On the intractability side, for every t greater than or equal to 0 we prove an equivalence between model-checking for first-order formulas with t quanti er alternations and the parameterized halting problem for alternating Turing machines with t alternations. We discuss the close connection between this alternation hierarchy and Downey and Fellows W-hierarchy. On a more abstract level, we consider two forms of definability, called Fagin definability and slicewise definability, that are appropriate for describing parameterized problems. We give a characterization of the class FPT of all fixed-parameter tractable problems in terms of slicewise definability in finite variable least fixed-point logic, which is reminiscent of the Immerman-Vardi theorem characterizing the class PTIME in terms of definability in least fixed-point logic.

关键词： parameterized complexity model-checking descriptive complexity

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds for Kernelizations and Other Preprocessing Procedures

引用

THEORY OF COMPUTING SYSTEMS 2011年第4期48卷 803-839页

作者： Chen, Yijia Flum, Joerg Mueller, Moritz Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai 200240 Peoples R China Univ Freiburg Abt Math Log D-79104 Freiburg Germany Ctr Recerca Matemat Barcelona Bellaterra 08193 Spain

We first present a method to rule out the existence of parameter non-increasing polynomial kernelizations of parameterized problems under the hypothesis P not equal NP. This method is applicable, for example, to the problem SAT parameterized by the number of variables of the input formula. Then we obtain further improvements of corresponding results in (Bodlaender et al. in Lecture Notes in Computer Science, vol. 5125, pp. 563-574, Springer, Berlin, 2008;Fortnow and Santhanam in Proceedings of the 40th ACM Symposium on the Theory of Computing (STOC'08), ACM, New York, pp. 133-142, 2008) by refining the central lemma of their proof method, a lemma due to Fortnow and Santhanam. In particular, assuming that the polynomial hierarchy does not collapse to its third level, we show that every parameterized problem with a "linear OR" and with NP-hard underlying classical problem does not have polynomial self-reductions that assign to every instance x with parameter k an instance y with vertical bar y vertical bar = k(O(1)) . vertical bar x vertical bar(1-epsilon) (here e is any given real number greater than zero). We give various applications of these results. On the structural side we prove several results clarifying the relationship between the different notions of pre-processing procedures, namely the various notions of kernelizations, self-reductions and compressions.

关键词： Kernelization parameterized complexity Lower bound

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：