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

作者： Liu, Yang Texas A&M University

NP-hard problems have numerous applications in various fields such as networks, computer systems, circuit design, etc. However, no efficient algorithms have been found for NP-hard problems. It has been commonly believed that no efficient algorithms for NP-hard problems exist, i.e., that P6=NP. Recently, it has been observed that there are parameters much smaller than input sizes in many instances of NP-hard problems in the real world. In the last twenty years, researchers have been interested in developing efficient algorithms, i.e., fixed-parameter tractable algorithms, for those instances with small parameters. Fixed-parameter tractable algorithms can practically find exact solutions to problem instances with small parameters, though those problems are considered intractable in traditional computational theory. In this dissertation, we propose a new approach of algorithm design and analysis: discovering better measures for problems. In particular we use two measures instead of the traditional single measure?input size to design algorithms and analyze their time complexity. For several classical NP-hard problems, we present improved algorithms designed and analyzed with this new approach, First we show that the new approach is extremely powerful for designing fixedparameter tractable algorithms by presenting improved fixed-parameter tractable algorithms for the 3D-matching and 3D-packing problems, the multiway cut problem, the feedback vertex set problems on both directed and undirected graph and the max-leaf problems on both directed and undirected graphs. Most of our algorithms are practical for problem instances with small parameters. Moreover, we show that this new approach is also good for designing exact algorithms (with no parameters) for NP-hard problems by presenting an improved exact algorithm for the well-known satisfiability problem. Our results demonstrate the power of this new approach to algorithm design and analysis for NP-hard problems. In the end,

关键词： Algorithm NP-hard Measure parameterized algorithms Fixed-parameter Tractable Book Thesis

来源：评论

学校读者我要写书评

暂无评论

Packing arc-disjoint cycles in oriented graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2024年 143卷

作者： Babu, Jasine Jacob, Ajay Saju Krithika, R. Rajendraprasad, Deepak Indian Inst Technol Palakkad Palakkad India Microsoft India Dev Ctr Noida India

ARC-DISJOINT CYCLE PACKING is a classical NP-complete problem and we study it from two perspectives: (1) by restricting the cycles in the packing to be of a fixed length, and (2) by restricting the inputs to bipartite tournaments. Focusing first on ARC-DISJOINT r-CYCLE PACKING (where the cycles in the packing are required to be of length r), we show NP-completeness in oriented graphs with girth rfor each r >= 3 and study the parameterized complexity of the problem with respect to two parameterizations (solution size and vertex cover size) for r = 4 in oriented graphs. Moving on to ARC-DISJOINT CYCLE PACKING in bipartite tournaments, we show that every bipartite tournament either contains k arc-disjoint cycles or has a feedback arc set of size at most 7(k - 1). This result adds to the set of Erdos-Posa-type results known in the combinatorics literature for packing and covering problems. (c) 2024 Elsevier Inc. All rights reserved.

关键词： Arc-disjoint cycles parameterized algorithms Kernels Erdos-Posa-type theorems

来源：评论

学校读者我要写书评

暂无评论

Representative Families of Product Families

引用

ACM TRANSACTIONS ON algorithms 2017年第3期13卷 36-36页

作者： Fomin, Fedor V. Lokshtanov, Daniel Panolan, Fahad Saurabh, Saket Univ Bergen Dept Informat N-5020 Bergen Norway HBNI Inst Math Sci Madras Tamil Nadu India HBNI Inst Math Sci Theoret Comp Sci Madras 600113 Tamil Nadu India Univ Bergen Bergen Norway

A subfamily F' of a set family F is said to q-represent F if for every A is an element of F and B of size q such that A boolean AND B = empty set there exists a set A' is an element of F' such that A' boolean AND B = empty set. Recently, we provided an algorithm that, for a given family F of sets of size p together with an integer q, efficiently computes a q-representative family F' of F of size approximately (p+q/p). In this article, we consider the efficient computation of q-representative families for product families F. A family F is a product family if there exist families A and 15 such that F = {A boolean OR B : A is an element of A, B is an element of B, A boolean AND B = empty set}. Our main teclutical contribution is an algorithm that, given A, B and q, computes a q-representative family F' of F. The running time of our algorithm is sublineur in vertical bar F vertical bar for many choices of A, B, and q that occur naturally in several dynamic programming algorithms. We also give an algorithm for the computation of q-representative families for product families F in the more general setting where q-representation also involves independence in a matroid in addition to disjointness. This algorithm considerably outperforms the naive approach where one first computes F from A and B and then computes the q-representative family F' from F. We give two applications of our new algorithms for computing q-representative families for product families. The first is a 3.8408(k)n(O(1)) deterministic algorithm for the MULTILINEAR MONOMIAL DETECTION (k-MLD) problem. The second is a significant improvement of deterministic dynamic programming algorithms for "connectivity problems" on graphs of bounded treewidth.

关键词： Matroids representative families parameterized algorithms multi-linear monomial detection tree-width bounded graphs

来源：评论

学校读者我要写书评

暂无评论

Temporal reachability minimization: Delaying vs. deleting

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2024年 144卷

作者： Molter, Hendrik Renken, Malte Zschoche, Philipp Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel Tech Univ Berlin Algorithm & Computat Complex Berlin Germany

We study spreading processes in temporal graphs, that is, graphs whose connections change over time. More precisely, we investigate how such a spreading process, emerging from a given set of sources, can be contained to a small part of the graph. We consider two ways of modifying the graph, which are (1) deleting and (2) delaying connections. We show a close relationship between the two associated problems. It is known that both problems are W[1]-hard when parameterized by the number of modifications. We consider the number of vertices to which the spread is contained as a parameter. Surprisingly, we prove W[1]-hardness for the deletion variant but fixed-parameter tractability for the delaying variant. Furthermore, we give a polynomial time algorithm for both problem variants when the graph has a tree structure and show how to generalize this result to an FPT-algorithm for the so-called timed feedback vertex number as a parameter. (c) 2024 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Temporal graphs Temporal paths Disease spreading Network flows parameterized algorithms NP-hard problems

来源：评论

学校读者我要写书评

暂无评论

A Double-Exponential Lower Bound for the Distinct Vectors Problem

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2020年第4期22卷 1页

作者： Pilipczuk, Marcin Sorge, Manuel Univ Warsaw Warsaw Poland

In the (binary) DISTINCT VECTORS problem we are given a binary matrix A with pairwise different rows and want to select at most k columns such that, restricting the matrix to these columns, all rows are still pairwise different. A result by Froese et al. [JCSS] implies a 2(2O(k)) center dot poly (vertical bar A vertical bar)-time brute-force algorithm for DISTINCT VECTORS. We show that this running time bound is essentially optimal by showing that there is a constant c such that the existence of an algorithm solving DISTINCT VECTORS with running time 2(O(2ck)) center dot poly (vertical bar A vertical bar) would contradict the Exponential Time Hypothesis.

关键词： feature selection data mining computational complexity parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Solving Projected Model Counting by Utilizing Treewidth and its Limits

引用

ARTIFICIAL INTELLIGENCE 2023年 314卷

作者： Fichte, Johannes K. Hecher, Markus Morak, Michael Thier, Patrick Woltran, Stefan TU Wien Database & Artificial Intelligence Grp Favoritenstr 9-11 A-1040 Vienna Austria Univ Klagenfurt Dept Artificial Intelligence & Cybersecur Univ Str 65-67 A-9020 Klagenfurt Am Worthersee Austria

In this paper, we introduce a novel algorithm to solve projected model counting (PMC). PMC asks to count solutions of a Boolean formula with respect to a given set of projection variables, where multiple solutions that are identical when restricted to the projection variables count as only one solution. Inspired by the observation that the so-called "treewidth" is one of the most prominent structural parameters, our algorithm utilizes small treewidth of the primal graph of the input instance. More precisely, it runs in time O(22k+4n2) where k is the treewidth and n is the input size of the instance. In other words, we obtain that the problem PMC is fixed-parameter tractable when parameterized by treewidth. Further, we take the exponential time hypothesis (ETH) into consideration and establish lower bounds of bounded treewidth algorithms for PMC, yielding asymptotically tight runtime bounds of our algorithm. While the algorithm above serves as a first theoretical upper bound and although it might be quite appealing for small values of k, unsurprisingly a naive implementation adhering to this runtime bound suffers already from instances of relatively small width. Therefore, we turn our attention to several measures in order to resolve this issue towards exploiting treewidth in practice: We present a technique called nested dynamic programming, where different levels of abstractions of the primal graph are used to (recursively) compute and refine tree decompositions of a given instance. Further, we integrate the concept of hybrid solving, where subproblems hidden by the abstraction are solved by classical search-based solvers, which leads to an interleaving of parameterized and classical solving. Finally, we provide a nested dynamic programming algorithm and an implementation that relies on database technology for PMC and a prominent special case of PMC, namely model counting (#SAT). Experiments indicate that the advancements are promising, allowing us to solve instanc

关键词： Tree decompositions High treewidth Lower bounds Exponential time hypothesis Graph problems Boolean logic Counting Projected model counting Nested dynamic programming Hybrid solving parameterized algorithms parameterized complexity Computational complexity Database management systems

来源：评论

学校读者我要写书评

暂无评论

SAT backdoors: Depth beats size

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2024年 142卷

作者： Dreier, Jan Ordyniak, Sebastian Szeider, Stefan TU Wien Algorithms & Complex Grp Vienna Austria Univ Leeds Algorithms & Complex Grp Leeds England

For several decades, much effort has been put into identifying classes of CNF formulas whose satisfiability can be decided in polynomial time. Classic results are the lineartime tractability of Horn formulas (Aspvall, Plass, and Tarjan, 1979) and Krom (i.e., 2CNF) formulas (Dowling and Gallier, 1984). Backdoors, introduced by Williams, Gomes and Selman (2003), gradually extend such a tractable class to all formulas of bounded distance to the class. Backdoor size provides a natural but rather crude distance measure between a formula and a tractable class. Backdoor depth, introduced by Mahlmann, Siebertz, and Vigny (2021), is a more refined distance measure, which admits the utilization of different backdoor variables in parallel. We propose FPT approximation algorithms to compute backdoor depth into the classes Horn and Krom. This leads to a linear-time algorithm for deciding the satisfiability of formulas of bounded backdoor depth into these classes. (c) 2024 The Authors. Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： SAT Satisfiability Backdoor Elimination distance parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

A 5k-vertex kernel for 3-path vertex cover

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期959卷

作者： Xiao, Mingyu Kou, Shaowei Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China

A 3-path vertex cover in a graph is a vertex subset C such that every path of three vertices contains at least one vertex from C. The parameterized 3-path vertex cover problem asks whether a graph has a 3-path vertex cover of size at most k. We give a kernel of 5k vertices for this problem, improving the previously known bounds.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Kernelization parameterized algorithms 3-Path vertex cover

来源：评论

学校读者我要写书评

暂无评论

Further improvements for SAT in terms of formula length

引用

INFORMATION AND COMPUTATION 2023年第1期294卷

作者： Peng, Junqiang Xiao, Mingyu Univ Elect Sci & Technol China Sch Comp Sci & Engn Chnegdu Peoples R China

In this paper, we prove that the general CNF satisfiability problem can be solved in O*(1.0638L) time, where L is the length of the input CNF-formula (i.e., the total number of literals in the formula), which improves the previous result of O*(1.0652L) obtained in 2009. Our algorithm was analyzed by using the measure-and-conquer method. Our improvements are mainly attributed to the following two points: we carefully design branching rules to deal with degree-5 and degree-4 variables to avoid previous bottlenecks;we show that some worst cases will not always happen, and then we can use an amortized technique to get further improvements. In our analyses, we provide some general frameworks for analysis and several lower bounds on the decreasing of the measure to simplify the arguments. These techniques may be used to analyze more algorithms based on the measure-and-conquer method.(c) 2023 Elsevier Inc. All rights reserved.

关键词： Satisfiability parameterized algorithms Measure-and-conquer Amortized analysis Worst-case analysis

来源：评论

学校读者我要写书评

暂无评论

Default logic and bounded treewidth

引用

INFORMATION AND COMPUTATION 2022年 283卷 104675-104675页

作者： Fichte, Johannes K. Hecher, Markus Schindler, Irina Tech Univ Dresden Sch Engn Sci Fac Comp Sci D-01062 Dresden Germany TU Wien Database & Artificial Intelligence Grp Inst Log & Computat Favoritenstr 9-11 A-1040 Vienna Austria Univ Potsdam Inst Comp Sci August Bebel Str 89 D-14482 Potsdam Germany Leibniz Univ Hannover Inst Theoret Informat Appelstr 4 D-30167 Hannover Germany

In this paper, we study Reiter's propositional default logic when the treewidth of a certain graph representation (semi-primal graph) of the input theory is bounded. We establish a dynamic programming algorithm on tree decompositions that decides whether a theory has a consistent stable extension (Cons). Our algorithm can even be used to enumerate all generating defaults (EnumSD) that lead to stable extensions. We show that our algorithm decides Cons in linear time in the input theory and triple exponential time in the treewidth Further, our algorithm solves EnumSD with a pre-computation step that is linear in the input theory and triple exponential in the treewidth followed by a linear delay to output solutions. Finally, we take the exponential time hypothesis (ETH) into consideration and establish lower bounds of bounded treewidth algorithms for Cons.

关键词： parameterized algorithms Tree decompositions Dynamic programming Reiter's default logic Propositional logic Lower bounds

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：