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

APPROXIMATELY COUNTING AND SAMPLING SMALL WITNESSES USING A COLORFUL DECISION ORACLE

SIAM JOURNAL ON COMPUTING 2022年第4期51卷 849-899页

作者： Dell, Holger Lapinskas, John Meeks, Kitty Goethe Univ Frankfurt Frankfurt Germany IT Univ Copenhagen Copenhagen Denmark BARC Copenhagen Denmark Univ Bristol Dept Comp Sci Bristol BS8 1UB England Univ Glasgow Sch Comp Sci Glasgow G12 8RZ Scotland

In this paper, we design efficient algorithms to approximately count the number of edges of a given k-hypergraph, and to sample an approximately uniform random edge. The hypergraph is not given explicitly and can be accessed only through its colorful independence or-acle: The colorful independence oracle returns yes or no depending on whether a given subset of the vertices contains an edge that is colorful with respect to a given vertex-coloring. Our results extend and/or strengthen recent results in the graph oracle literature due to Beame et al. [ACM Trans. Algorithms , 16 (2020), 52], Dell and Lapinskas [Proceedings of STOC , ACM, 2018, pp. 281-288], and Bhattacharya et al. [Proceedings of ISAAC , 2019]. Our results have consequences for approximate counting/sampling: We can turn certain kinds of decision algorithms into approximate counting/sampling algorithms without causing much overhead in the running time. We apply this ap-proximate counting/sampling-to-decision reduction to key problems in fine-grained complexity (such as k-SUM, k-OV, and weighted k-Clique) and parameterized complexity (such as induced subgraphs of size k or weight -k solutions to constraint satisfaction problems).

关键词： approximate counting FPTRAS fine-grained complexity parameterized complexity graph oracles

来源：评论

学校读者我要写书评

暂无评论

On the Fine Grained complexity of Finite Automata Non-emptiness of Intersection 1

引用

24th International Conference on Developments in Language Theory (DLT)

作者： Oliveira, Mateus de Oliveira Wehar, Michael Univ Bergen Bergen Norway Swarthmore Coll Swarthmore PA 19081 USA

ISBN: (数字)9783030485160

ISBN: (纸本)9783030485153;9783030485160

We study the fine grained complexity of the DFA non-emptiness of intersection problem parameterized by the number k of input automata (k-DFA-NEI). More specifically, we are given a list < A(1),..., A(k)> of DFA's over a common alphabet Sigma, and the goal is to determine whether boolean AND(k)(i=1) L(A(i)) not equal empty set. This problem can be solved in time O(n(k)) by applying the classic Rabin-Scott product construction. In this work, we show that the existence of algorithms solving k-DFA-NEI in time slightly faster than O(n(k)) would imply the existence of deterministic sub-exponential time algorithms for the simulation of nondeterministic linear space bounded computations. This consequence strengthens the existing conditional lower bounds for k-DFA-NEI and implies new non-uniform circuit lower bounds.

关键词： Finite automata Intersection non-emptiness Fine grained complexity parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Synchronizing series-parallel deterministic finite automata with loops and related problems

引用

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2021年 55卷

作者： Bruchertseifer, Jens Fernau, Henning Holzer, Markus Sempere, Jose M. Univ Trier Abt Informat Wissensch CIRT Theoret Informat Fachbereich 4 Trier Germany

We study the problem DFA-SW of determining if a given deterministic finite automaton A possesses a synchronizing word of length at most k for automata whose (multi-)graphs are TTSPL, i.e., series-parallel, plus allowing some self-loops. While DFA-SW remains NP-complete on TTSPL automata, we also find (further) restrictions with efficient (parameterized) algorithms. We also study the (parameterized) complexity of related problems, for instance, extension variants of the synchronizing word problem, or the problem of finding smallest alphabet-induced synchronizable sub-automata.

关键词： Synchronizing words series-parallel graphs parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Grundy Coloring & Friends, Half-Graphs, Bicliques 37

Grundy Coloring & Friends, Half-Graphs, Bicliques

引用

37th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Aboulker, Pierre Bonnet, Edouard Kim, Eun Jung Sikora, Florian PSL Univ DI ENS Paris France Univ Claude Bernard Lyon 1 Univ Lyon CNRS ENS LyonLIPUMR5668 Villeurbanne France PSL Univ Univ Paris Dauphine CNRS UMR7243LAMSADE Paris France

ISBN: (纸本)9783959771405

The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order a, the smallest available color. The problem GRUNDY COLORING asks how many colors are needed for the most adversarial vertex ordering a , 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 K-t,K-t-hard arid 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 hall-gmphs 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 WW-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-free graphs half-graphs

来源：评论

学校读者我要写书评

暂无评论

Decremental Optimization of Dominating Sets Under the Reconfiguration Framework 31st

Decremental Optimization of Dominating Sets Under the Reconf...

引用

31st International Workshop on Combinatorial Algorithms (IWOCA)

作者： Blanche, Alexandre Mizuta, Haruka Ouvrard, Paul Suzuki, Akira Univ Bordeaux Bordeaux INP LaBRI CNRSUMR5800 F-33400 Talence France Tohoku Univ Grad Sch Informat Sci Aoba Ku Aoba 6-6-05 Sendai Miyagi 9808579 Japan

ISBN: (纸本)9783030489656;9783030489663

Given a dominating set, how much smaller a dominating set can we find through elementary operations? Here, we proceed by iterative vertex addition and removal while maintaining the property that the set forms a dominating set of bounded size. This can be seen as the optimization variant of the dominating set reconfiguration problem, where two dominating sets are given and the question is merely whether they can be reached from one another through elementary operations. We show that this problem is PSPACE-complete, even if the input graph is a bipartite graph, a split graph, or has bounded pathwidth. On the positive side, we give linear-time algorithms for cographs, trees and interval graphs. We also study the parameterized complexity of this problem. More precisely, we show that the problem is W[2]-hard when parameterized by the upper bound on the size of an intermediary dominating set. On the other hand, we give fixed-parameter algorithms with respect to the minimum size of a vertex cover, or d + s where d is the degeneracy and s is the upper bound of the output solution.

关键词： Combinatorial reconfiguration Dominating set parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

The complexity landscape of decompositional parameters for ILP: Programs with few global variables and constraints

引用

ARTIFICIAL INTELLIGENCE 2021年 300卷 103561-103561页

作者： Dvorak, Pavel Eiben, Eduard Ganian, Robert Knop, Dusan Ordyniak, Sebastian Charles Univ Prague Comp Sci Inst Prague Czech Republic Royal Holloway Univ London London England Vienna Univ Technol Algorithms & Complex Grp Vienna Austria Czech Tech Univ Prague Czech Republic Univ Sheffield Dept Comp Sci Sheffield S Yorkshire England

Integer Linear Programming (ILP) has a broad range of applications in various areas of artificial intelligence. Yet in spite of recent advances, we still lack a thorough understanding of which structural restrictions make ILP tractable. Here we study ILP instances consisting of a small number of "global" variables and/or constraints such that the remaining part of the instance consists of small and otherwise independent components;this is captured in terms of a structural measure we call fracture backdoors which generalizes, for instance, the well-studied class of N-fold ILP instances. Our main contributions can be divided into three parts. First, we formally develop fracture backdoors and obtain exact and approximation algorithms for computing these. Second, we exploit these backdoors to develop several new parameterized algorithms for ILP;the performance of these algorithms will naturally scale based on the number of global variables or constraints in the instance. Finally, we complement the developed algorithms with matching lower bounds. Altogether, our results paint a near-complete complexity landscape of ILP with respect to fracture backdoors.(1) (C) 2021 The Author(s). Published by Elsevier B.V.

关键词： Integer linear programming parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Kernel for K_t-FREE EDGE DELETION

引用

INFORMATION PROCESSING LETTERS 2021年 167卷 106082-106082页

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

In the K-t-FREE EDGE DELETION problem the input is a graph G and an integer k, and the goal is to decide whether there is a set of at most k edges of G whose removal results in a graph with no clique of size t. In this paper we give a kernel to this problem with O(k(t-1)) vertices and edges. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Graph algorithms parameterized complexity Kernelization

来源：评论

学校读者我要写书评

暂无评论

Hitting forbidden induced subgraphs on bounded treewidth graphs

引用

INFORMATION AND COMPUTATION 2021年 281卷 104812-104812页

作者： Sau, Ignasi Souza, Ueverton dos Santos Univ Montpellier CNRS LIRMM Montpellier France Univ Fed Fluminense Inst Comp Niteroi RJ Brazil

For a fixed graph H, the H-IS-DELETION problem asks, given a graph G, for the minimum size of a set S subset of V(G) such that G \ S excludes Has an induced subgraph. We are interested in determining, for a fixed H, the smallest function f(H)(t) such that H-IS-DELETION can be solved in time f(H)(t) . n(O(1)) assuming the Exponential Time Hypothesis, where t and n denote the treewidth and the number of vertices of G, respectively. We show that f(H)(t) = 2(O(th-2)) for every H on h >= 3 vertices, and that f(H)(t) = 2(O(t)) if H is a clique or an independent set. When H deviates slightly from a clique, the function f(H)(t) suffers a sharp jump: if His obtained from a clique of size h by removing one edge, then f(H)(t) = 2(Theta(th-2)). Moreover, f(H)(t) = 2(Omega(th)) when H=K-h,K-h, answering a question of Pilipczuk [MFCS 2011]. (C) 2021 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Induced subgraphs Treewidth Hitting subgraphs Dynamic programming Lower bound Exponential time hypothesis

来源：评论

学校读者我要写书评

暂无评论

Synchronizing Words and Monoid Factorization: A parameterized Perspective 16th

Synchronizing Words and Monoid Factorization: A Parameterize...

引用

16th International Conference on Theory and Applications of Models of Computation (TAMC)

作者： Bruchertseifer, Jens Fernau, Henning Univ Trier Fachber Abt Informatikwissensch 4 D-54286 Trier Germany

ISBN: (纸本)9783030592660;9783030592677

The concept of a synchronizing word is a very important notion in the theory of finite automata. We consider the associated decision problem to decide if a given DFA possesses a synchronizing word of length at most k, where k is the standard parameter. We show that this problem DFA-SW is equivalent to the problem MONOID FACTORIZATION introduced by Cai, Chen, Downey and Fellows. Apart from the knownW[2]-hardness results, we show that these problems belong to A[2], W[P] and WNL. This indicates that DFA-SW is not complete for any of these classes and hence, we suggest a new parameterized complexity class W[Sync] as a proper home for these (and more) problems.

关键词： Synchronizing word Deterministic Finite Automaton (DFA) parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Iterated Type Partitions 31st

Iterated Type Partitions

引用

31st International Workshop on Combinatorial Algorithms (IWOCA)

作者： Cordasco, Gennaro Gargano, Luisa Rescigno, Adele A. Univ Campania L Vanvitelli Caserta Italy Univ Salerno Fisciano Italy

ISBN: (纸本)9783030489656;9783030489663

This paper introduces a novel parameter, called iterated type partition, that can be computed in polynomial time and nicely places between modular-width and neighborhood diversity. We prove that the Equitable Coloring problem is W[1]-hard when parametrized by the iterated type partition. This result extends to modular-width, answering an open question on the complexity of Equitable Coloring when parametrized by modular-width. On the contrary, we show that the Equitable Coloring problem is FPT when parameterized by neighborhood diversity. Furthermore, we present a scheme for devising FPT algorithms parameterized by iterated type partition, which enables us to find optimal solutions for several graph problems. While the considered problems are already known to be FPT with respect to modular-width, the novel algorithms are both simpler and more efficient. As an example, in this paper, we give an algorithm for the Dominating Set problem that outputs an optimal set in time O(2(t) + poly(n)), where n and t are the size and the iterated type partition of the input graph, respectively.

关键词： parameterized complexity Fixed-parameter tractable algorithms W[1]-hardness Neighborhood diversity Modular-width

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：