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

ALGORITHMICA 2023年第10期85卷 2923-2961页

作者： Haak, Anselm Meier, Arne Prakash, Om Rao, B. V. Raghavendra Leibniz Univ Hannover Inst Theoret Informat Appelstr 9A D-30167 Hannover Germany IIT Madras Dept Comp Sci & Engn BSB 354 Chennai 600036 India Goethe Univ Frankfurt Theoret Comp Sci Grp Robert Mayer Str 11-15 D-60325 Frankfurt Germany

Logarithmic space-bounded complexity classes such as L and NL play a central role in space-bounded computation. The study of counting versions of these complexity classes have lead to several interesting insights into the structure of computational problems such as computing the determinant and counting paths in directed acyclic graphs. Though parameterised complexity theory was initiated roughly three decades ago by Downey and Fellows, a satisfactory study of parameterised logarithmic space bounded computation was developed only in the last decade by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). In this paper, we introduce a new framework for parameterised counting in logspace, inspired by the parameterised space-bounded models developed by Elberfeld, Stockhusen and Tantau. They defined the operators para(W) and parab for parameterised space complexity classes by allowing bounded nondeterminism with multiple-read and read-once access, respectively. Using these operators, they characterised the parameterised complexity of natural problems on graphs. In the spirit of the operators para(W) and parab by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism, para(W[1]) and parab (tail). Then, we consider counting versions of all four operators and apply them to the class L. We obtain several natural complete problems for the resulting classes: counting of paths in digraphs, counting first-order models for formulas, and counting graph homomorphisms. Furthermore, we show that the complexity of a parameterised variant of the determinant function for (0, 1)-matrices is #parab(tail)L-hard and can be written as the difference of two functions in #parab(tail)L. These problems exhibit the richness of the introduced counting classes. Our results further indicate interesting structural characteristics of these classes. For example, we show that the closure of #parab L-tail under parameterised logspace parsimonious reductions coincides with #

关键词： parameterized complexity Counting complexity Logspace

来源：评论

学校读者我要写书评

暂无评论

Almost optimal query algorithm for hitting set using a subset query

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2023年第1期137卷 50-65页

作者： Bishnu, Arijit Ghosh, Arijit Kolay, Sudeshna Mishra, Gopinath Saurabh, Saket Indian Stat Inst Kolkata India Indian Inst Technol Kharagpur Kharagpur India Univ Warwick Coventry England HBNI Inst Math Sci Chennai India

In this paper, we focus on HITTING-SET, a fundamental problem in combinatorial optimization, through the lens of sublinear time algorithms. Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for HITTING-SET with almost tight parameterized query complexity. In parameterized query complexity, we estimate the number of queries to the oracle based on the parameter k, the size of the HITTING-SET. The subset query oracle we use in this paper is called Generalized d-partite Independent Set query oracle (GPIS) and it was introduced by Bishnu et al. (ISAAC'18). GPIS is a generalization to hypergraphs of the Bipartite Independent Set query oracle (BIS) introduced by Beame et al. (ITCS'18 and TALG'20) for estimating the number of edges in graphs. Since its introduction GPIS query oracle has been used for estimating the number of hyperedges independently by Dell et al.(SODA'20 and SICOMP'22) and Bhattacharya et al. (STACS'22), and for estimating the number of triangles in a graph by Bhattacharya et al. (ISAAC'19 and TOCS'21). Formally, GPIS is defined as follows: GPIS oracle for a d-uniform hypergraph H takes as input d pairwise disjoint non-empty subsets A(1),..., A(d) of vertices in Hand answers whether there is a hyperedge in Hthat intersects each set A(i), where i is an element of{1, 2,..., d}. For d = 2, the GPIS oracle is nothing but BIS oracle. We show that d-Hitting-Set, the hitting set problem for d-uniform hypergraphs, can be solved using (O) over tilde (d)(k(d) log n) GPIS queries. Additionally, we also showed that d-DECISION-HITTING-SET, the decision version of d-HITTING-SET can be solved with (O) over tilde (d) (min {k(d) log n, k(2d2)} GPIS queries. We complement these parameterized upper bounds with an almost matching parameterized lower bound that states that any algorithm that solves d-Decision HITTING-SET requires Omega ((k+d d)) GPIS queries. (c) 2023 Elsevier Inc. All rights reserved.

关键词： Query complexity Subset queries Hitting set parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized algorithms for variants of 3-Hitting Set

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2025年第4期49卷 1-14页

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

In the A-Multi3-Hitting Set problem (A-M3HS), where A subset of{1,2,3}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A \subseteq \{1,2,3\}$$\end{document}, the input is a hypergraph G in which the hyperedges have sizes at most 3 and an integer k, and the goal is to decide if there is a set S of at most k vertices such that |S boolean AND e|is an element of A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|S \cap e| \in A$$\end{document} for every hyperedge e. In this paper we give O & lowast;(2.027k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O<^>*(2.027<^>k)$$\end{document}-time algorithms for {1}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{1\}$$\end{document}-M3HS and {1,3}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{1,3\}$$\end{document}-M3HS, and an O & lowast;(1.381k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O<^>*(1.381<^>k)$$\end{document}-time algorithm for {2}\docume

关键词： Graph algorithms parameterized complexity Branching algorithms

来源：评论

学校读者我要写书评

暂无评论

Structural parameterizations of budgeted graph coloring

引用

THEORETICAL COMPUTER SCIENCE 2023年第PartA期940卷 209-221页

作者： Bandopadhyay, Susobhan Banerjee, Suman Banik, Aritra Raman, Venkatesh Natl Inst Sci Educ & Res Bhubaneswar 752050 Odisha India Indian Inst Technol Dept Comp Sci & Engn Jammu India HBNI Inst Math Sci Chennai India

We introduce a variant of the graph coloring problem, which we denote as BUDGETED COLORING PROBLEM (BCP). Given a graph G, an integer c and an ordered list of integers (b1, b2, ... , bc), BCP asks whether there exists a proper coloring of G where the i-th color is used to color at most bi many vertices. This problem generalizes two well-studied graph coloring problems, BOUNDED COLORING PROBLEM (BOCP) and EQUITABLE COLORING PROBLEM (ECP) and as in the case of other coloring problems, the BCP is NP-hard even for constant values of c. So we study BCP under the paradigm of parameterized complexity, particularly with respect to (structural) parameters that specify how far (the deletion distance) the input graph is from a tractable graph *** dot We show that BCP is FPT (fixed-parameter tractable) parameterized by the vertex cover size. This generalizes a similar result for ECP and immediately extends to the BoCP, which was earlier not *** dot We show that BCP is polynomial time solvable for cluster graphs generalizing a similar result for ECP. However, we show that BCP is FPT, but unlikely to have polynomial kernel, when parameterized by the deletion distance to clique, contrasting the linear kernel for ECP for the same *** dot While the BoCP is known to be polynomial time solvable on split graphs, we show that BCP is NP-hard on split graphs. As BoCP is hard on bipartite graphs when c > 3, the result follows for BCP as well. We provide a dichotomy result by showing that BCP is polynomial time solvable on bipartite graphs when c = 2. We also show that BCP is NP-hard on co-cluster graphs, contrasting the polynomial time algorithm for ECP and *** we present an O*(2|V(G)|) algorithm for the BCP, generalizing the known algorithm with a similar bound for the standard chromatic number.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Graph coloring Exact exponential algorithm parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Advanced tools and methods for treewidth-based problem solving

引用

IT-INFORMATION TECHNOLOGY 2023年第1-2期65卷 65-73页

作者： Hecher, Markus MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

Computer programs, so-called solvers, for solving the well-known Boolean satisfiability problem (Sat) have been improving for decades. Among the reasons, why these solvers are so fast, is the implicit usage of the formula's structural properties during solving. One of such structural indicators is the so-called treewidth, which tries to measure how close a formula instance is to being easy (tree-like). This work focuses on logic-based problems and treewidth-based methods and tools for solving them. Many of these problems are also relevant for knowledge representation and reasoning (KR) as well as artificial intelligence (AI) in general. We present a new type of problem reduction, which is referred to by decomposition-guided (DG). This reduction type forms the basis to solve a problem for quantified Boolean formulas (QBFs) of bounded treewidth that has been open since 2004. The solution of this problem then gives rise to a new methodology for proving precise lower bounds for a range of further formalisms in logic, KR, and AI. Despite the established lower bounds, we implement an algorithm for solving extensions of Sat efficiently, by directly using treewidth. Our implementation is based on finding abstractions of instances, which are then incrementally refined in the process. Thereby, our observations confirm that treewidth is an important measure that should be considered in the design of modern solvers.

关键词： AI ETH lower bounds logic parameterized complexity quantitative reasoning treewidth

来源：评论

学校读者我要写书评

暂无评论

Reducing the vertex cover number via edge contractions *,**

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2023年 136卷 63-87页

作者： Lima, Paloma T. dos Santos, Vinicius F. Sau, Ignasi Souza, Ueverton S. Tale, Prafullkumar IT Univ Copenhagen Comp Sci Dept Copenhagen Denmark Univ Fed Minas Gerais Dept Ciencia Comp Belo Horizonte Brazil Univ Montpellier LIRMM CNRS Montpellier France Univ Fed Fluminense Inst Comp Niteroi Brazil Univ Warsaw Inst Informat Warsaw Poland Indian Inst Sci Educ & Res Pune Dept Math Pune India

Given a graph G on n vertices and two integers k and d, the Contraction(VC) problem asks whether one can contract at most k edges to reduce the vertex cover number of G by at least d. Recently, Lima et al. [JCSS 2021] proved that Contraction(VC) admits an XP algorithm running in time f (d) center dot nO(d). They asked whether this problem is FPT under this parameterization. In this article, we prove that: (i) Contraction(VC) is W[1]-hard parameterized by k + d. Moreover, unless the ETH fails, the problem does not admit an algorithm running in time f (k + d) center dot no(k+d) for any function f. This answers negatively the open question stated in Lima et al. [JCSS 2021]. (ii) Contraction(VC) is NP-hard even when k = d. (iii) Contraction(VC) can be solved in time 2O(d) center dot nk-d+O(1). This improves the algorithm of Lima et al. [JCSS 2021], and shows that when k = d, Contraction(VC) is FPT parameterized by d (or by k). (c) 2023 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： Blocker problems Edge contraction Vertex cover parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Discrete Morse Theory 13

Parameterized Complexity of Discrete Morse Theory

引用

29th Annual Symposium on Computational Geometry (SoCG)

作者： Burton, Benjamin A. Lewiner, Thomas Paixao, Joao Spreer, Jonathan Univ Queensland Sch Math & Phys Brisbane Qld Australia Pontificia Univ Catolica Rio de Janeiro Dept Math Rio de Janeiro Brazil

ISBN: (纸本)9781450320313

Optimal Morse matchings reveal essential structures of cell complexes which lead to powerful tools to study discrete geometrical objects, in particular discrete 3-manifolds. However, such matchings are known to be NP-hard to compute on 3-manifolds, through a reduction to the erasability problem. Here, we refine the study of the complexity of problems related to discrete Morse theory in terms of parameterized complexity. On the one hand we prove that the erasability problem is W[P]-complete on the natural parameter. On the other hand we propose an algorithm for computing optimal Morse matchings on triangulations of 3-manifolds which is fixed-parameter tractable in the treewidth of the bipartite graph representing the adjacency of the 1- and 2-simplexes. This algorithm also shows fixed parameter tractability for problems such as erasability and maximum alternating cycle-free matching. We further show that these results are also true when the treewidth of the dual graph of the triangulated 3-manifold is bounded. Finally, we investigate the respective treewidths of simplicial and generalized triangulations of 3-manifolds.

关键词： discrete Morse theory alternating cycle-free matching parameterized complexity fixed parameter tractability W[P]-completeness treewidth erasability collapsibility computational topology

来源：评论

学校读者我要写书评

暂无评论

On data reduction for dynamic vector bin packing

引用

OPERATIONS RESEARCH LETTERS 2023年第4期51卷 446-452页

作者： van Bevern, Rene Melnikov, Andrey Smirnov, Pavel V. Tsidulko, Oxana Yu. Huawei Technol Co Ltd Novosibirsk Russia

We study a dynamic vector bin packing (DVBP) problem. We show hardness for shrinking arbitrary DVBP instances to size polynomial in the number of request types or in the maximal number of requests overlapping in time. We also present a simple polynomial-time data reduction algorithm that allows to recover (1 + & epsilon;)-approximate solutions for arbitrary & epsilon;> 0. It shrinks instances from Microsoft Azure and Huawei Cloud by an order of magnitude for & epsilon;= 0.02.& COPY;2023 Elsevier B.V. All rights reserved.

关键词： Approximation & amp heuristics parameterized complexity Lossy kernelization Resource allocation N

来源：评论

学校读者我要写书评

暂无评论

A Cubic Vertex-Kernel for TRIVIALLY PERFECT EDITING

引用

ALGORITHMICA 2023年第4期85卷 1091-1110页

作者： Dumas, Mael Perez, Anthony Todinca, Ioan Univ Orleans INSA Ctr Val Loire LIFO EA 4022 F-45067 Orleans France

We consider the TRIVIALLY PERFECT EDITING problem, where one is given an undirected graph G = (V, E) and a parameter k is an element of N and seeks to edit (add or delete) at most k edges from G to obtain a trivially perfect graph. The related TRIVIALLY PERFECT COMPLETION and TRIVIALLY PERFECT DELETION problems are obtained by only allowing edge additions or edge deletions, respectively. Trivially perfect graphs are both chordal and cographs, and have applications related to the tree-depth width parameter and to social network analysis. All variants of the problem are known to be NP-complete (Burzyn et al., in Discret Appl Math 154(13):1824-1844, 2006;Nastos and Gao, in Soc Netw 35(3):439-450, 2013) and to admit so-called polynomial kernels (Drange and Pilipczuk, in Algorithmica 80(12):3481-3524, 2018;Guo, in: Tokuyama, (ed) Algorithms and Computation, 18th International Symposium, ISAAC. Lecture Notes in Computer Science, Springer, Sendai, 2007. haps://***110.1007/978-3-540-77120-3_79;Bathie et al., in Algorithmica 1-27, 2022). More precisely, Drange and Pilipczuk (Algorithmica 80(12):3481-3524, 2018) provided O(k(7)) vertex-kernels for these problems and left open the existence of cubic vertex-kernels. In this work, we answer positively to this question for all three variants of the problem. Notice that a quadratic vertex-kernel was recently obtained for TRIVIALLY PERFECT COMPLETION by Bathie et al. (Algorithmica 1-27, 2022).

关键词： parameterized complexity Kernelization algorithms Graph modification problems Trivially perfect graphs

来源：评论

学校读者我要写书评

暂无评论

Grid recognition: Classical and parameterized computational perspectives

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2023年 136卷 17-62页

作者： Gupta, Siddharth Sa'ar, Guy Zehavi, Meirav Univ Warwick Coventry England Ben Gurion Univ Negev Beer Sheva Israel

Over the past few decades, a large body of works studied the (in)tractability of various computational problems on grid graphs, which often yield substantially faster algorithms than general graphs. Unfortunately, the recognition of a grid graph is hard-it was shown to be NP-hard already in 1987. In this paper, we provide several positive results in this regard in the framework of parameterized complexity. Specifically, our contribution is threefold. First, we show that the problem is FPT parameterized by k + mcc where mcc is the maximum size of a connected component of G. Second, we present a new parameterization, denoted aG, relating graph distance to geometric distance. We show that the problem is para-NP-hard parameterized by aG, but FPT parameterized by aG on trees, as well as FPT parameterized by k + a(G). Third, we show that the recognition of k x r grid graphs is NP-hard on graphs of pathwidth 2 where k = 3. (c) 2023 Elsevier Inc. All rights reserved.

关键词： Grid recognition Grid graph parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：