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

The complexity of optimizing atomic congestion

ARTIFICIAL INTELLIGENCE 2025年 338卷

作者： Brand, Cornelius Ganian, Robert Kalyanasundaram, Subrahmanyam Inerney, Fionn Mc Regensburg Univ Algorithms & Complex Theory Grp Regensburg Germany TU Wien Algorithms & Complex Grp Vienna Austria IIT Hyderabad Dept Comp Sci & Engn Hyderabad India Tech Univ Wien Favoritenstr 9-11E192-01 A-1040 Vienna Austria

Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory, and are capable of modeling congestion and flow optimization tasks in various application areas. While both the price of anarchy for such games as well as the computational complexity of computing their Nash equilibria are by now well-understood, the computational complexity of computing a system-optimal set of strategies-that is, a centrally planned routing that minimizes the average cost of agents-is severely understudied in the literature. We close this gap by identifying the exact boundaries of tractability for the problem through the lens of the parameterized complexity paradigm. After showing that the problem remains highly intractable even on extremely simple networks, we obtain a set of results which demonstrate that the structural parameters which control the computational (in)tractability of the problem are not vertex- separator based in nature (such as, e.g., treewidth), but rather based on edge separators. We conclude by extending our analysis towards the (even more challenging) min-max variant of the problem.

关键词： Atomic congestion games System optimum Routing parameterized complexity Slim treecut width

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms and a smaller kernel for CLIQUES OR TREES VERTEX DELETION

引用

INFORMATION PROCESSING LETTERS 2025年 190卷

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

In the CLIQUES OR TREES VERTEX DELETION problem, the input is a graph and an integer , and the goal is to decide whether there is a set of at most vertices whose removal from result in a graph in which every connected component is either a clique or a tree. In this paper we give an *(3.46)-time deterministic algorithm, an *(3.103)-time randomized algorithm, and a kernel with (4) vertices for CLIQUES OR TREES VERTEX DELETION.

关键词： Graph algorithms parameterized complexity Branching algorithms Kernelization

来源：评论

学校读者我要写书评

暂无评论

Bandwidth parameterized by Cluster Vertex Deletion Number

引用

ALGORITHMICA 2025年 1-32页

作者： Gima, Tatsuya Kim, Eun Jung Kohler, Noleen Melissinos, Nikolaos Vasilakis, Manolis Hokkaido Univ Sapporo Hokkaido Japan Korea Adv Inst Sci & Technol Daejeon South Korea CNRS Paris France Inst Basic Sci IBS Discrete Math Grp Daejeon South Korea Univ Leeds Leeds England Czech Tech Univ Fac Informat Technol Dept Theoret Comp Sci Prague Czech Republic PSL Univ Univ Paris Dauphine CNRS LAMSADEUMR7243 Paris France

Given a graph G and an integer b, Bandwidth asks whether there exists a bijection pi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\pi $$\end{document} from V(G) to {1,& mldr;,|V(G)|}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{1, \ldots , |V(G)|\}$$\end{document} such that max{u,v}is an element of E(G)|pi(u)-pi(v)|<= b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\max _{\{u, v \} \in E(G)} | \pi (u) - \pi (v) | \le b$$\end{document}. This is a classical NP-complete problem, known to remain NP-complete even on very restricted classes of graphs, such as trees of maximum degree 3 and caterpillars of hair length 3. In the realm of parameterized complexity, these results imply that the problem remains NP-hard on graphs of bounded pathwidth, while it is additionally known to be W[1]-hard when parameterized by the tree-depth of the input graph. In contrast, the problem does become FPT when parameterized by the vertex cover number. In this paper we make progress in understanding the parameterized (in)tractability of Bandwidth. We first show that it is FPT when parameterized by the cluster vertex deletion number cvd plus the clique number omega\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\omega $$\end{document}, thus significantly strengthening the

关键词： Bandwidth Clique number Cluster vertex deletion number parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

An Efficient Algorithm for Power Dominating Set

引用

ALGORITHMICA 2025年第3期87卷 344-376页

作者： Blaesius, Thomas Goettlicher, Max Karlsruhe Inst Technol KIT Karlsruhe Germany

The problem Power Dominating Set (PDS) is motivated by the placement of phasor measurement units to monitor electrical networks. It asks for a minimum set of vertices in a graph that observes all remaining vertices by exhaustively applying two observation rules. Our contribution is twofold. First, we determine the parameterized complexity of PDS by proving it is W[P]-complete when parameterized with respect to the solution size. We note that it was only known to be W[2]-hard before. Our second and main contribution is a new algorithm for PDS that efficiently solves practical instances. Our algorithm consists of two complementary parts. The first is a set of reduction rules for PDS that can also be used in conjunction with previously existing algorithms. The second is an algorithm for solving the remaining kernel based on the implicit hitting set approach. Our evaluation on a set of power grid instances from the literature shows that our solver outperforms previous state-of-the-art solvers for PDS by more than one order of magnitude on average. Furthermore, our algorithm can solve previously unsolved instances of continental scale within a few minutes.

关键词： Power dominating set Implicit hitting set parameterized complexity Reduction rules

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized algorithm for r-pseudoforest deletion

引用

THEORETICAL COMPUTER SCIENCE 2025年 1028卷

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

In the r-PSEUDOFOREST DELETION problem, the input is a graph G and integers k, r, and the goal is to decide whether there is a set of at most k vertices whose removal from G results in a graph in which every connected component can be made into a tree by deleting at most redges. In this paper we give an O<^> * ((8r + 1) <^> k) time algorithm for r-PSEUDOFOREST DELETION for every r >= 1.

关键词： Graph algorithms parameterized complexity Branching algorithms

来源：评论

学校读者我要写书评

暂无评论

Computing Hamiltonian Paths with Partial Order Restrictions

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2025年第1期17卷 1-24页

作者： Beisegel, Jesse Ratajczak, Fabienne Scheffler, Robert Brandenburg Tech Univ Cottbus Inst Math Cottbus Germany Brandenburg Tech Univ Cottbus Inst Math Cottbus Germany

When solving the Hamiltonian path problem it seems natural to be given additional precedence constraints for the order in which the vertices are visited. For example, one could decide whether a Hamiltonian path exists for a fixed starting point, or that some vertices are visited before another vertex. We consider the problem of finding a Hamiltonian path that observes all precedence constraints given in a partial order on the vertex set. We show that this problem is NP-complete even if restricted to complete bipartite graphs and posets of height 2. In contrast, for posets of width k there is a known O(k2nk) algorithm for arbitrary graphs with n vertices. We show that it is unlikely that the running time of this algorithm can be improved significantly, i.e., there is no f(k)no(k) time algorithm under the assumption of the Exponential Time Hypothesis. Furthermore, for the class of outerplanar graphs, we give an O(n2) algorithm for arbitrary posets.

关键词： Hamiltonian path partial order outerplanar graph partial search order TSP-PC 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

来源：评论

学校读者我要写书评

暂无评论

Gerrymandering on Graphs: Computational complexity and parameterized Algorithms 14th

Gerrymandering on Graphs: Computational Complexity and Param...

引用

14th International Symposium on Algorithmic Game Theory (SAGT)

作者： Gupta, Sushmita Jain, Pallavi Panolan, Fahad Roy, Sanjukta Saurabh, Saket HBNI Inst Math Sci Chennai Tamil Nadu India Indian Inst Technol Jodhpur Jodhpur Rajasthan India Indian Inst Technol Hyderabad Hyderabad India TU Wien Vienna Austria

ISBN: (纸本)9783030859466;9783030859473

This paper studies gerrymandering on graphs from a computational viewpoint (introduced by Cohen-Zemach et al. [AAMAS 2018] and continued by Ito et al. [AAMAS 2019]). Our contributions are twofold: conceptual and computational. We propose a generalization of the model studied by Ito et al., where the input consists of a graph on n vertices representing the set of voters, a set of m candidates C, a weight function w(v) : C -> Z(+) for each voter v is an element of V (G) representing the preference of the voter over the candidates, a distinguished candidate p is an element of C, and a positive integer k. The objective is to decide if it is possible to partition the vertex set into k districts (i.e., pairwise disjoint connected sets) such that the candidate p wins more districts than any other candidate. There are several natural parameters associated with the problem: the number of districts (k), the number of voters (n), and the number of candidates (m). The problem is known to be NP-complete even if k = 2, m = 2, and G is either a complete bipartite graph (in fact K-2,K-n, i.e., partitions of size 2 and n) or a complete graph. Moreover, recently we and Bentert et al. [WG 2021], independently, showed that the problem is NP-hard for paths. This means that the search for FPT algorithms needs to focus either on the parameter n, or subclasses of forest (as the problem is NP-complete on K-2,K-n, a family of graphs that can be transformed into a forest by deleting one vertex). Circumventing these intractability results we successfully obtain the following algorithmic results. - A 2(n) (n + m)(O(1)) time algorithm on general graphs. - FPT algorithm with respect to k (an algorithm with running time 2(O(k)) n(O(1))) on paths in both deterministic and randomized settings, even for arbitrary weight functions. Whether the problem is FPT parameterized by k on trees remains an interesting open problem. Our algorithmic results use sophisticated technical tools such as representative

关键词： Gerrymandering parameterized complexity Representative set

来源：评论

学校读者我要写书评

暂无评论

The complexity of Promise Constraint Satisfaction Problem Seen from the Other Side

引用

JOURNAL OF MULTIPLE-VALUED LOGIC AND SOFT COMPUTING 2025年第4期44卷 333-352页

作者： Asimi, Kristina Barto, Libor Dalmau, Victor Univ Durham Dept Comp Sci Durham England Charles Univ Prague Fac Math & Phys Dept Algebra Prague Czech Republic Pompeu Fabra Univ Dept Informat & Commun Technol Barcelona Spain

We introduce the framework of the left-hand side restricted promise constraint satisfaction problem, which includes problems like approximating clique number of a graph. We study the parameterized complexity of problems in this class and provide some initial results. The main technical contribution is a sufficient condition for W[1]-hardness which, in particular, covers left-hand side restricted bounded arity CSPs.

关键词： Constraint satisfaction problem computational complexity parameterized complexity approximating clique homomorphisms promise constraint satisfaction problem

来源：评论

学校读者我要写书评

暂无评论

On Two-Handed Planar Assembly Partitioning with Connectivity Constraints

引用

ACM Transactions on Algorithms 2025年第2期21卷 1-31页

作者： Agarwal, Pankaj K. Aronov, Boris Geft, Tzvika Halperin, Dan Department of Computer Science Duke University Durham NC United States Department of Computer Science and Engineering New York University Tandon School of Engineering New York NY United States Tel Aviv University Tel Aviv Israel

Assembly planning is a fundamental problem in robotics and automation, which involves designing a sequence of motions to bring the separate constituent parts of a product into their final placement in the product. Assembly planning is naturally cast as a disassembly problem, giving rise to the assembly partitioning sub-problem: Given a set A of parts, find a subset S ⊂ A, referred to as a subassembly, such that S can be rigidly translated to infinity along a prescribed direction without colliding with A\S . While assembly partitioning is efficiently solvable, it is further desirable for the parts of a subassembly to be easily held together. This motivates the problem that we study, called connected-assembly-partitioning, which additionally requires each of the two subassemblies, S and A\S, to be connected. We obtain the following results. - We show that this problem is NP-complete, settling an open question posed by Wilson et al. 30 years ago, even when consists of unit-grid squares (i.e., is polyomino-shaped). For assemblies composed of polygons, we also show that deciding whether complete (dis)assembly is possible by repeatedly applying connected-assembly-partitioning, is NP-complete. Toward these results, we prove the NP-hardness of a new Planar 3-SAT variant having an adjacency requirement for variables appearing in the same clause, which may be of independent interest. - On the positive side, we give an O(2^kn²)-time fixed-parameter tractable algorithm (requiring low degree polynomial-time preprocessing) for an assembly consisting of polygons in the plane, where n = |A| and k = |S| . We also describe a special case of unit-grid square assemblies, where a connected partition can always be found in O(n)-time. © 2025 Copyright held by the owner/author(s). Publication rights licensed to ACM.

关键词： assembly partitioning assembly planning assembly sequencing NP-hardness parameterized complexity Planar SAT

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：