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

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

来源：评论

学校读者我要写书评

暂无评论

Galactic token sliding

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2023年第1期136卷 220-248页

作者： Bartier, Valentin Bousquet, Nicolas Mouawad, Amer E. Univ Claude Bernard Lyon 1 Univ Lyon CNRS ENS LyonUMR5668 Lyon France Univ Lyon CNRS UCBL INSA LyonLIRISUMR5205 Lyon France Amer Univ Beirut Dept Comp Sci Beirut Lebanon Univ Bremen Bremen Germany

Given a graph G and two independent sets Is and It of size k, the INDEPENDENT SET RECONFIGURATION problem asks whether there exists a sequence of independent sets that transforms Is to It such that each independent set is obtained from the previous one using a so-called reconfiguration step. Viewing each independent set as a collection of k tokens placed on the vertices of a graph G, the two most studied reconfiguration steps are token jumping and token sliding. Over a series of papers, it was shown that the TOKEN JUMPING problem is fixed-parameter tractable (for parameter k) when restricted to sparse graph classes, such as planar, bounded treewidth, and nowhere dense graphs. As for the TOKEN SLIDING problem, almost nothing is known. We remedy this situation by showing that TOKEN SLIDING is fixed-parameter tractable on graphs of bounded degree, planar graphs, and chordal graphs of bounded clique number. (c) 2023 Elsevier Inc. All rights reserved.

关键词： Combinatorial reconfiguration Token sliding Graph classes parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Kernels for storage capacity and dual index coding

引用

JOURNAL OF COMBINATORIAL THEORY SERIES A 2025年 216卷

作者： Haviv, Ishay Acad Coll Tel Aviv Yaffo IL-61083 Tel Aviv Israel

The storage capacity of a graph measures the maximum amount of information that can be stored across its vertices, such that the information at any vertex can be recovered from the information stored at its neighborhood. The study of this graph quantity is motivated by applications in distributed storage and by its intimate relations to the index coding problem from the area of network information theory. In the latter, one wishes to minimize the amount of information that has to be transmitted to a collection of receivers, in a way that enables each of them to discover its required data using some prior side information. In this paper, we initiate the study of the STORAGE CAPACITY and INDEX CODING problems from the perspective of parameterized complexity. We prove that the STORAGE CAPACITY problem parameterized by the solution size admits a kernelization algorithm producing kernels of linear size. We also provide such a result for the INDEX CODING problem, in the linear and non-linear settings, where it is parameterized by the dual value of the solution, i.e., the length of the transmission that can be saved using the side information. A key ingredient in the proofs is the crown decomposition technique due to Chor, Fellows, and Juedes [14,11]. As an application, we significantly extend an algorithmic result of Dau, Skachek, and Chee [13]. (c) 2025 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Storage capacity Index coding Minrank Kernelization parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

The Shortest Path Reconfiguration Problem Based on Relaxation of Reconfiguration Rules 1

引用

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

作者： Domon, Naoki Suzuki, Akira Tamura, Yuma Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Sendai Miyagi Japan

ISBN: (数字)9789819705665

ISBN: (纸本)9789819705658;9789819705665

The shortest path problem is the most classical and fundamental problem in the field of graph algorithm. Recently, its reconfiguration variant, namely the Shortest Path Reconfiguration problem, has received a lot of attention. In this paper, we study the complexity of k-SPR, which generalizes the Shortest Path Reconfiguration problem, with respect to k. In k-SPR, we are allowed to replace at most k consecutive vertices of the current shortest path at a time. We first show that, for any fixed rational numbers c and epsilon such that c > 0 and 0 < epsilon <= 1, k-SPR with k = cn(1-epsilon) is polynomially solvable if epsilon = 1 and c < 1;otherwise, PSPACE-complete. This intractability holds even when given graphs are restricted to bipartite graphs and r-th power graphs, where r is any positive integer. Furthermore, when we restrict 0 < epsilon < 1, the PSPACE-completeness holds for graphs with maximum degree 3. Then, we design an FPT algorithm parameterized by mu = n/2 - k >= 0 that runs in O(m + 6.730(mu) mu(4) n) time. Finally, we show that, for any k, k-SPR can be solved in linear time for K-2,K-3-minor-free graphs.

关键词： Reconfiguration problem Graph algorithm parameterized complexity Shortest path

来源：评论

学校读者我要写书评

暂无评论

Sparsity in Covering Solutions 16th

Sparsity in Covering Solutions

引用

16th Latin American Symposium on Theoretical Informatics (LATIN)

作者： Jain, Pallavi Rathore, Manveer Singh Indian Inst Technol Jodhpur Jodhpur India

ISBN: (纸本)9783031556005;9783031556012

In the classical covering problems, the goal is to find a subset of vertices/edges that "covers" a specific structure of the graph. In this work, we initiate the study of the covering problems where given a graph G, in addition to the covering, the solution needs to be sparse, i.e., the number of edges with both the endpoints in the solution are minimized. We consider two well-studied covering problems, namely VERTEX COVER and FEEDBACK VERTEX SET. In Sparse VERTEX COVER, given a graph G, and integers k, t, the goal is to find a minimal vertex cover S of size at most k such that the number of edges in G[S] is at most t. Analogously, we can define SPARSE FEEDBACK VERTEX SET. Both the problems are NP-hard. We studied these problems in the realm of parameterized complexity. Our results are as follows: 1. SPARSE VERTEX COVER ADMITS an O(k(2)) vertex kernel and an algorithm that runs in O(1.3953(k) . n(O(1))) time. 2. SPARSE FEEDBACK VERTEX SET admits an O(k(4)) vertex kernel and an algorithm that runs in O(5(k) . n(O(1))) time.

关键词： parameterized complexity Kernelization Vertex Cover Feedback Vertex Set Sparsity

来源：评论

学校读者我要写书评

暂无评论

Counting Small Induced Subgraphs with Edge-Monotone Properties 2024

Counting Small Induced Subgraphs with Edge-Monotone Properti...

引用

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

作者： Doering, Simon Marx, Daniel Wellnitz, Philip Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany Saarbrucken Grad Sch Comp Sci Saarland Informat Campus Saarbrucken Germany CISPA Helmholtz Ctr Informat Secur Saarbrucken Germany

ISBN: (纸本)9798400703836

We study the parameterized complexity of #IndSub(Phi), where given a graph G and an integer k, the task is to count the number of induced subgraphs on k vertices that satisfy the graph property Phi. Focke and Roth [STOC 2022] completely characterized the complexity for each F that is a hereditary property (that is, closed under vertex deletions): #IndSub(Phi) is #W[1]-hard except in the degenerate cases when every graph satisfies Phi or only finitely many graphs satisfy Phi. We complement this result with a classification for each Phi that is edge-monotone (that is, closed under edge deletions): #IndSub(Phi) is #W[1]-hard except in the degenerate case when there are only finitely many integers k such that Phi is nontrivial on k-vertex graphs. Our result generalizes earlier results for specific properties F that are related to the connectivity or density of the graph. Further, we extend the #W[1]-hardness result by a lower bound which shows that #IndSub(F) cannot be solved in time f(k) center dot vertical bar V(G)vertical bar(o(root log) (k/loglog) (k)) for any function f, unless the Exponential-Time Hypothesis (ETH) fails. For many natural properties, we obtain even a tight bound f(k) center dot vertical bar V(G)vertical bar(o(k));for example, this is the case for every property F that is nontrivial on k-vertex graphs for each k greater than some k(0).

关键词： Counting complexity Fine-grained complexity Graph Homomorphisms Induced Subgraphs parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

A new perspective on single-machine scheduling problems with late work related criteria

引用

ANNALS OF OPERATIONS RESEARCH 2023年第2期322卷 947-966页

作者： Shabtay, Dvir Ben Gurion Univ Negev Dept Ind Engn & Management Beer Sheva Israel

This paper provides two new perspectives on single-machine scheduling problems in which the objective involves penalties regarding late work. Both of this perspectives have been neglected in the previous literature. We begin by presenting a parameterized complexity analysis of the NP-hard problem of minimizing the total late work on a single machine. We do so with respect to the following four parameters: (i) the number of different processing times (upsilon p);(ii) the number of different due dates (upsilon d);(iii) the maximal processing time (pmax);and (iv) the maximal due date (dmax). We use results from the literature to conclude that the problem is hard with respect to (wrt.) parameter upsilon d and is tractable (i.e., solvable in FPT time) wrt. pmax. We then provide two FPT algorithms showing that the problem is also tractable wrt. to upsilon p and dmax. We continue by analyzing a single-machine scheduling problem with assignable due dates where the cost function to be minimized includes penalties due to weighted early and tardy work. We assume that each job can be assigned a different due-date, the value of which is subject to a job-dependent upper bound. We provide an efficient method to optimally assign due dates for a given job schedule. We then use this result to reduce the problem to a purely combinatorial problem, which we show is NP-hard in general, but solvable in either FPT time or polynomial time for some special cases.

关键词： Scheduling Single machine Late work Due date assignment parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

XNLP-Hardness of parameterized Problems on Planar Graphs 50th

XNLP-Hardness of Parameterized Problems on Planar Graphs

引用

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

作者： Bodlaender, Hans L. Szilagyi, Krisztina Univ Utrecht Utrecht Netherlands

ISBN: (纸本)9783031754081;9783031754098

The class XNLP consists of (parameterized) problems that can be solved nondeterministically in f(k)n(O(1)) time and g(k) log n space, where n is the size of the input instance and k the parameter. The class XALP consists of problems that can be solved in the above time and space with access to an additional stack. These two classes are a "natural home" for many standard graph problems and their generalizations. In this paper, we show the hardness of several problems on planar graphs, parameterized by outerplanarity, treewidth and pathwidth, thus strengthening several existing results. In particular, we show XNLP-hardness of the following problems parameterized by outerplanarity: ALL-OR-NOTHING FLOW, TARGET OUTDEGREE ORIENTATION, CAPACITATED (RED-BLUE) DOMINATING SET, TARGET SET SELECTION etc. We also show the XNLP-completeness of SCATTERED SET parameterized by pathwidth and XALP-completeness parameterized by treewidth and outerplanarity.

关键词： parameterized complexity XNLP XALP Planar Graphs Outerplanarity

来源：评论

学校读者我要写书评

暂无评论

On Polynomial Kernelization for Stable Cutset 50th

On Polynomial Kernelization for Stable Cutset

引用

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

作者： Kratsch, Stefan Le, Van Bang Humboldt Univ Inst Informat Berlin Germany Univ Rostock Inst Informatik Rostock Germany

ISBN: (纸本)9783031754081;9783031754098

A stable cutset in a graph G is a set S subset of V (G) such that vertices of S are pairwise non-adjacent and such that G - S is disconnected, i.e., it is both stable (or independent) set and a cutset (or separator). Unlike general cutsets, it is NP-complete to determine whether a given graph G has any stable cutset. Recently, Rauch et al. [FCT 2023] gave a number of fixed-parameter tractable (FPT) algorithms, time f(k) . vertical bar V(G)vertical bar(c), for STABLE CUTSET under a variety of parameters k such as the size of a (given) dominating set, the size of an odd cycle transversal, or the deletion distance to P-5-free graphs. Earlier works imply FPT algorithms relative to clique-width and relative to solution size. We complement these findings by giving the first results on the existence of polynomial kernelizations for STABLE CUTSET, i.e., efficient pre-processing algorithms that return an equivalent instance of size polynomial in the parameter value. Under the standard assumption that NP not subset of coNP/poly, we show that no polynomial kernelization is possible relative to the deletion distance to a single path, generalizing deletion distance to various graph classes, nor by the size of a (given) dominating set. We also show that under the same assumption no polynomial kernelization is possible relative to solution size, i.e., given (G, k) answering whether there is a stable cutset of size at most k. On the positive side, we show polynomial kernelizations for parameterization by modulators to a single clique, to a cluster or a co-cluster graph, and by twin cover.

关键词： stable cutset kernelization parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Offensive Alliances in Signed Graphs 18th

Offensive Alliances in Signed Graphs

引用

18th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Feng, Zhidan Fernau, Henning Mann, Kevin Qi, Xingqin Shandong Univ Sch Math & Stat Weihai 264209 Peoples R China Univ Trier FB Informat Wissensch 4 D-54286 Trier Germany

ISBN: (纸本)9789819723393;9789819723409

Signed graphs have been introduced to enrich graph structures expressing relationships between persons or general social entities, introducing edge signs to reflect the nature of the relationship, e.g., friendship or enmity. Independently, offensive alliances have been defined and studied for undirected, unsigned graphs. We join both lines of research and define offensive alliances in signed graphs, hence considering the nature of relationships. Apart from some combinatorial results, mainly on k-balanced and k-anti-balanced signed graphs (a newly introduced family of signed graphs), we focus on the algorithmic complexity of finding smallest offensive alliances, looking at a number of parameterizations. While the parameter solution size leads to an FPT result for unsigned graphs, we obtain W[2]-completeness for the signed setting. We introduce new parameters for signed graphs, e.g., distance to weakly balanced signed graphs, that could be of independent interest. We show that these parameters yield FPT results. Here, we make use of the recently introduced parameter neighborhood diversity for signed graphs.

关键词： Offensive Alliance parameterized complexity Fixed Parameter Tractable Signed Graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：