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

8th International Symposium on Combinatorial Optimization (ISCO)

作者： Mallem, Maher Hanen, Claire Munier-Kordon, Alix Sorbonne Univ LIP6 CNRS F-75005 Paris France Univ Paris Nanterre UPL F-92000 Nanterre France

ISBN: (纸本)9783031609237;9783031609244

In this paper we study the single machine scheduling problem with release dates, deadlines and precedence relations where the objective is to minimize the makespan. This is a well-known strongly NP-hard scheduling problem [18]. We analyze the problem from the parameterized complexity point of view. We propose parameter q which is the maximum number of time windows [r(j), d(j)) that can strictly include a time window [r(i), d(i)) on both ends. We show that problems 1|prec, r(j), d(j)|C-max and 1 vertical bar prec, r(j) |L-max are fixed-parameter tractable parameterized by q. We use a dynamic programming approach and define a new dominance rule, which we call the weak earliest deadline rule. This rule narrows down the number of relevant scheduling prefixes enough to complete the search via a fixed-parameter tractable number of dynamic programming states.

关键词： parameterized complexity scheduling single machine

来源：评论

学校读者我要写书评

暂无评论

Computing Twin-Width parameterized by the Feedback Edge Number 41

Computing Twin-Width Parameterized by the Feedback Edge Numb...

引用

41st International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Balaban, Jakub Ganian, Robert Rocton, Mathis Masaryk Univ Fac Informat Brno Czech Republic TU Wien Algorithms & Complex Grp Vienna Austria

ISBN: (纸本)9783959773119

The problem of whether and how one can compute the twin-width of a graph - along with an accompanying contraction sequence - lies at the forefront of the area of algorithmic model theory. While significant effort has been aimed at obtaining a fixed-parameter approximation for the problem when parameterized by twin-width, here we approach the question from a different perspective and consider whether one can obtain (near-)optimal contraction sequences under a larger parameterization, notably the feedback edge number k. As our main contributions, under this parameterization we obtain (1) a linear bikernel for the problem of either computing a 2-contraction sequence or determining that none exists and (2) an approximate fixed-parameter algorithm which computes an l-contraction sequence (for an arbitrary specified l) or determines that the twin-width of the input graph is at least l. These algorithmic results rely on newly obtained insights into the structure of optimal contraction sequences, and as a byproduct of these we also slightly tighten the bound on the twin-width of graphs with small feedback edge number.

关键词： twin-width parameterized complexity kernelization feedback edge number

来源：评论

学校读者我要写书评

暂无评论

Fast Winning Strategies for the Attacker in Eternal Domination 50th

Fast Winning Strategies for the Attacker in Eternal Dominati...

引用

50th International Workshop on Graph-Theoretic Concepts in Computer Science

作者： Bagan, Guillaume Bousquet, Nicolas Oijid, Nacim Pierron, Theo Univ Claude Bernard Lyon 1 CNRS INSA Lyon LIRISUMR5205 F-69622 Villeurbanne France

ISBN: (纸本)9783031754081;9783031754098

Dominating sets in graphs are often used to model monitoring problems, by posting guards on the vertices of the dominating set. If an (unguarded) vertex is attacked, at least one guard can then react by moving there. This yields a new set of guards, which may not be dominating anymore. A dominating set is eternal if one can endlessly resist to attacks. From the attacker's perspective, if we are given a non-eternal dominating set, the question is to determine how fast can we provoke an attack that cannot be handled by a neighboring guard. We investigate this question from a computational complexity point of view, by showing that this question is PSPACE-hard, even for graph classes where finding a minimum eternal dominating set is in P. We then complement this result by giving polynomial time algorithms for cographs and trees, and showing a connection with treedepth for the latter. We also investigate the problem from a parameterized complexity perspective, mainly considering two parameters: the number of guards and the number of steps.

关键词： eternal dominating set treedepth PSPACE-completeness parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the complexity of solution extension of optimization problems

引用

THEORETICAL COMPUTER SCIENCE 2022年 904卷 48-65页

作者： Casel, Katrin Fernau, Henning Ghadikolaei, Mehdi Khosravian Monnot, Jerome Sikora, Florian Univ Potsdam Hasso Plattner Inst D-14482 Potsdam Germany Univ Trier Informat wissensch Theoret Informat Fachbereich 4 D-54286 Trier Germany Univ Paris 09 PSL Univ LAMSADE CNRS F-75016 Paris France

The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating minimal vertex covers of a graph G = (V, E), one usually arrives at the problem to decide for a vertex set U subset of V (pre-solution), if there exists a minimal vertex cover S (i.e., a vertex cover S subset of V such that no proper subset of S is a vertex cover) with U subset of S (minimal extension of U). We propose a general, partial-order based formulation of such extension problems which allows to model parameterization and approximation aspects of extension, and also highlights relationships between extension tasks for different specific problems. As examples, we study a number of specific problems which can be expressed and related in this framework. In particular, we discuss extension variants of the problems dominating set and feedback vertex/edge set. All these problems are shown to be NP-complete even when restricted to bipartite graphs of bounded degree, with the exception of our extension version of feedback edge set on undirected graphs which is shown to be solvable in polynomial time. For the extension variants of dominating and feedback vertex set, we also show NP-completeness for the restriction to planar graphs of bounded degree. As non-graph problem, we also study an extension version of the bin packing problem. We further consider the parameterized complexity of all these extension variants, where the parameter is a measure of the pre-solution as defined by our framework. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Extension problems NP-hardness parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Faster deterministic algorithms for CO-PATH PACKING and CO-PATH/CYCLE PACKING

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第5期44卷 3701-3710页

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

In the CO-PATH PACKING (resp., CO-PATH/CYCLE PACKING) 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 vertices whose removal from G results in a graph which is a collection of induced paths (resp., induced paths and cycles). In this paper we give deterministic O* (3(k))-time algorithms for CO-PATH PACKING and CO-PATH/CYCLE PACKING.

关键词： Graph algorithms parameterized complexity Branching algorithms

来源：评论

学校读者我要写书评

暂无评论

Almost-Linear Time parameterized Algorithm for Rankwidth via Dynamic Rankwidth 2024

Almost-Linear Time Parameterized Algorithm for Rankwidth via...

引用

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Korhonen, Tuukka Sokolowski, Marek Univ Bergen Bergen Norway Univ Warsaw Warsaw Poland

ISBN: (纸本)9798400703836

We give an algorithm that given a graph G with n vertices and m edges and an integer k, in time O-k(n(1+o(1))) + O(m) either outputs a rank decomposition of G of width at most k or determines that the rankwidth of G is larger than k;the O-k(center dot)-notation hides factors depending on k. Our algorithm returns also a (2(k+1) - 1)-expression for cliquewidth, yielding a (2(k+1) -1)-approximation algorithm for cliquewidth with the same running time. This improves upon the O-k(n(2)) time algorithm of Fomin and Korhonen [STOC 2022]. The main ingredient of our algorithm is a fully dynamic algorithm for maintaining rank decompositions of bounded width: We give a data structure that for a dynamic n-vertex graph G that is updated by edge insertions and deletions maintains a rank decomposition of G of width at most 4k under the promise that the rankwidth of G never grows above k. The amortized running time of each update is O-k(2(root log n log log n)). The data structure furthermore can maintain whether G satisfies some fixed CMSO1 property within the same running time. We also give a framework for performing dense edge updates inside a given set of vertices X, where the new edges inside X are described by a given CMSO1 sentence and vertex labels, in amortized O-k(vertical bar X vertical bar center dot 2(root log n log log n)) time. Our dynamic algorithm generalizes the dynamic treewidth algorithm of Korhonen, Majewski, Nadara, Pilipczuk, and Sokolowski [FOCS 2023].

关键词： rankwidth cliquewidth parameterized complexity monadic second-order logic

来源：评论

学校读者我要写书评

暂无评论

Structural Parameterizations of Vertex Integrity [Best Paper] 18th

Structural Parameterizations of Vertex Integrity [Best Paper...

引用

18th International Conference and Workshops on Algorithms and Computation (WALCOM)

作者： Gima, Tatsuya Hanaka, Tesshu Kobayashi, Yasuaki Murai, Ryota Ono, Hirotaka Otachi, Yota Nagoya Univ Nagoya Aichi Japan Kyushu Univ Fukuoka Japan Hokkaido Univ Sapporo Hokkaido Japan

ISBN: (纸本)9789819705658;9789819705665

The graph parameter vertex integrity measures how vulnerable a graph is to a removal of a small number of vertices. More precisely, a graph with small vertex integrity admits a small number of vertex removals to make the remaining connected components small. In this paper, we initiate a systematic study of structural parameterizations of the problem of computing the unweighted/weighted vertex integrity. As structural graph parameters, we consider well-known parameters such as clique-width, treewidth, pathwidth, treedepth, modular-width, neighborhood diversity, twin cover number, and cluster vertex deletion number. We show several positive and negative results and present sharp complexity contrasts.

关键词： Vertex integrity Vulnerability of graphs Structural graph parameter parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Counting Vanishing Matrix-Vector Products 18th

Counting Vanishing Matrix-Vector Products

引用

18th International Conference and Workshops on Algorithms and Computation (WALCOM)

作者： Brand, Cornelius Korchemna, Viktoriia Simonov, Kirill Skotnica, Michael Univ Regensburg Algorithms & Complex Theory Grp Regensburg Germany TU Wien Algorithms & Complex Grp Vienna Austria Univ Potsdam Hasso Plattner Inst Potsdam Germany Charles Univ Prague Dept Appl Math Prague Czech Republic

ISBN: (纸本)9789819705658;9789819705665

Consider the following parameterized counting variation of the classic subset sum problem, which arises notably in the context of higher homotopy groups of topological spaces: Let v is an element of Q(d) be a rational vector, (T-1, T-2... T-m) a list of d x d rational matrices, S is an element of Q(hxd) a rational matrix not necessarily square and k a parameter. The goal is to compute the number of ways one can choose k matrices T-i1, T-i2,..., T-ik from the list such that STik center dot center dot center dot T(i1)v = 0 is an element of Q(h). In this paper, we show that this problem is #W[2]-hard for parameter k. As a consequence, computing the k-th homotopy group of a d-dimensional 1-connected topological space for d > 3 is #W[2]-hard for parameter k. We also discuss a decision version of the problem and its several modifications for which we show W[1]/W[2]-hardness. This is in contrast to the parameterized k-sum problem, which is only W[1]-hard (Abboud-Lewi-Williams, ESA'14). In addition, we show that the decision version of the problem without parameter is an undecidable problem, and we give a fixed-parameter tractable algorithm for matrices of bounded size over finite fields, parameterized by the matrix dimensions and the order of the field.

关键词： parameterized complexity W[2]-hardness undecidability k-sum homotopy group

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

TARGET SET SELECTION IN DENSE GRAPH CLASSES

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2022年第1期36卷 536-572页

作者： Dvorak, Pavel Knop, Dusan Toufar, Tomas Charles Univ Prague Inst Comp Sci Prague 11636 Czech Republic Czech Tech Univ Fac Informat Technol Prague 16000 Czech Republic Charles Univ Prague Fac Math & Phys Prague 11636 Czech Republic

In this paper, we study the TARGET SET SELECTION problem from a parameterized complexity perspective. Here for a given graph and a threshold for each vertex, the task is to find a set of vertices (called a target set) that activates the whole graph during the following iterative process. A vertex outside the active set becomes active if the number of so far activated vertices in its neighborhood is at least its threshold. We give two parameterized algorithms for a special case where each vertex has the threshold set to half of its neighbors (the so-called MAJORITY TARGET SET SELECTION problem) for parameterizations by the neighborhood diversity and the twin cover number of the input graph. We complement these results from the negative side. We give a hardness proof for the MAJORITY TARGET SET SELECTION problem when parameterized by (a restriction of) the modular-width -a natural generalization of both previous structural parameters. We also show the TARGET SET SELECTION problem parameterized by the neighborhood diversity or by the twin cover number is W[1]-hard when there is no restriction on the thresholds.

关键词： parameterized complexity target set selection dense graphs opinion diffusion

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：