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

Fixed-Parameter Tractability of (n - k) List Coloring

THEORY OF COMPUTING SYSTEMS 2020年第7期64卷 1307-1316页

作者： Banik, Aritra Jacob, Ashwin Paliwal, Vijay Kumar Raman, Venkatesh Natl Inst Sci Educ & Res HBNI Bhubaneswar India Inst Math Sci Theoret Comp Sci GB-09CIT Campus Chennai 600113 Tamil Nadu India DE Shaw India Private Ltd Hyderabad India HBNI Inst Math Sci Chennai Tamil Nadu India

We consider the list-coloring problem from the perspective of parameterized complexity. In the classical graph coloring problem we are given an undirected graph and the goal is to color the vertices of the graph with minimum number of colors so that end points of each edge get different colors. In list-coloring, each vertex is given a list of allowed colors with which it can be colored. An interesting parameterization for graph coloring that has been studied is whether the graph can be colored with n - k colors, where k is the parameter and n is the number of vertices. This is known to be fixed parameter tractable. Our main result is that this can be generalized for list-coloring as well. More specifically, we show that, given a graph with each vertex having a list of size n-k, it can be determined in f(k)n(O(1)) time, for some function f of k, whether there is a coloring that respects the lists.

关键词： parameterized complexity List Coloring Coloring Fixed Parameter Tractability

来源：评论

学校读者我要写书评

暂无评论

Chain Minors are FPT

引用

ALGORITHMICA 2017年第3期79卷 698-707页

作者： Blasiok, Jaroslaw Kaminski, Marcin Uniwersytet Warszawski Inst Informatyki Warsaw Poland

Given two finite partially ordered sets P and Q, we say that P is a chain minor of Q if there exists a partial function f from the elements of Q to the elements of P such that for every chain in P there is a chain C-Q in Q with the property that f restricted to C-Q is an isomorphism of chains C and C-Q. We give an algorithm to decide whether a partially ordered set P is a chain minor of a partially ordered set Q, which runs in time O(|Q| log |Q|) for every fixed partially ordered set P. This solves an open problem from the monograph by Downey and Fellows (parameterized complexity. Springer, New York, 1999) who asked whether the problem was fixed parameter tractable.

关键词： Partially ordered sets parameterized complexity Data structures and algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：