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

Detecting maximum k-durable structures on temporal graphs

KNOWLEDGE-BASED SYSTEMS 2023年第1期271卷

作者： Li, Faming Zou, Zhaonian Liu, Xianmin Li, Jianzhong Yang, Xiaochun Wang, Bin Northeastern Univ Sch Comp Sci & Engn Shenyang Peoples R China Harbin Inst Technol Sch Comp Sci & Technol Harbin Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen Peoples R China Natl Frontiers Sci Ctr Ind Intelligence & Syst Opt Shenyang Peoples R China Northeastern Univ Key Lab Data Analyt & Optimizat Smart Ind Minist Educ Shenyang Peoples R China

In this paper, we study the problem of detecting maximum k-durable structures on temporal graphs, which can be used to mine and analyze more knowledge behind the temporal graphs. We first prove that this problem is NP-complete and hard to approximate. Next, we propose an efficient algorithm to detect maximum k-durable structures. The algorithm accelerates the detection process by using an auxiliary graph and several well-designed pruning strategies. Massive experiments on five large temporal social networks demonstrate that our algorithm can save 2-4 orders of magnitude number of recursive invocation and is at least 30x faster than the baseline algorithm.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Temporal graph Durable structure parameterized complexity Biclique

来源：评论

学校读者我要写书评

暂无评论

Solving infinite-domain CSPs using the patchwork property

引用

ARTIFICIAL INTELLIGENCE 2023年 317卷

作者： Dabrowski, Konrad K. Jonsson, Peter Ordyniak, Sebastian Osipov, George Newcastle Univ Sch Comp Newcastle upon Tyne England Univ Leeds Sch Comp Leeds England Linkopings Univ Dept Comp & Informat Sci Linkoping Sweden

The constraint satisfaction problem (CSP) has important applications in computer science and AI. In particular, infinite-domain CSPs have been intensively used in subareas of AI such as spatio-temporal reasoning. Since constraint satisfaction is a computationally hard problem, much work has been devoted to identifying restricted problems that are efficiently solvable. One way of doing this is to restrict the interactions of variables and constraints, and a highly successful approach is to bound the treewidth of the underlying primal graph. Bodirsky & Dalmau (2013) [14] and Huang et al. (2013) [47] proved that CSP(Gamma) can be solved in nf (w) time (where n is the size of the instance, w is the treewidth of the primal graph and f is a computable function) for certain classes of constraint languages Gamma. We improve this bound to f (w) middot nO (1) , where the function f only depends on the language r, for CSPs whose basic relations have the patchwork property. Hence, such problems are fixed-parameter tractable and our algorithm is asymptotically faster than the previous ones. Additionally, our approach is not restricted to binary constraints, so it is applicable to a strictly larger class of problems than that of Huang et al. However, there exist natural problems that are covered by Bodirsky & Dalmau's algorithm but not by ours, and we begin investigating ways of generalising our results to larger families of languages. We also analyse our algorithm with respect to its running time and show that it is optimal (under the Exponential Time Hypothesis) for certain languages such as Allen's Interval Algebra.(c) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： Constraint satisfaction problem parameterized complexity Treewidth Infinite domain Lower bound

来源：评论

学校读者我要写书评

暂无评论

The complexity of mixed-connectivity

引用

ANNALS OF OPERATIONS RESEARCH 2021年第1-2期307卷 25-35页

作者： Bonnet, Edouard Cabello, Sergio Univ Claude Bernard Lyon 1 Univ Lyon CNRS ENS LyonLIPUMR 5668 Lyon France Univ Ljubljana Fac Math & Phys Ljubljana Slovenia Inst Math Phys & Mech Ljubljana Slovenia

We investigate the parameterized complexity in a and b of determining whether a graph G has a subset of a vertices and b edges whose removal disconnects G, or disconnects two prescribed vertices s, t is an element of ... 详细信息

关键词： Mixed-connectivity Mixed-cut Vertex-connectivity Edge-connectivity NP-completeness parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期951卷

作者： Branson, Luke Sutton, Andrew M. Univ Minnesota Duluth Dept Comp Sci Duluth MN 55812 USA

Repair operators are often used for constraint handling in constrained combinatorial optimization. We investigate the (1+1) EA equipped with a tailored jump-and-repair operation that can be used to probabilistically repair infeasible offspring in graph problems. Instead of evolving candidate solutions to the entire graph, we expand the genotype to allow the (1+1) EA to develop in parallel a feasible solution together with a growing subset of the instance (an induced subgraph). With this approach, we prove that the EA is able to probabilistically simulate an iterative compression process used in classical fixed-parameter algorithmics to obtain a randomized FPT performance guarantee on three NP-hard graph problems. For k-VERTEXCOVER, we prove that the (1+1) EA using focused jump-and-repair can find a k-vertex cover (if one exists) in O (2kn2 log n) iterations in expectation. This leads to an exponential (in k) improvement over the best-known parameterized bound for evolutionary algorithms on VERTEXCOVER. For the k-FEEDBACKVERTEXSET problem in tournaments, we prove that the EA finds a feasible feedback set in O (2kk!n2 log n) iterations in expectation, and for ODDCYCLETRANSVERSAL, we prove the optimization time for the EA is O (3kkmn2 log n). For the latter two problems, this constitutes the first parameterized result for any evolutionary algorithm. We discuss how to generalize the framework to other parameterized graph problems closed under induced subgraphs and report experimental results that illustrate the behavior of the algorithm on a concrete instance class.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Theory of evolutionary algorithms Runtime analysis parameterized complexity Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

On Structural Parameterizations of the Offensive Alliance Problem 15th

On Structural Parameterizations of the Offensive Alliance Pr...

引用

15th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Gaikwad, Ajinkya Maity, Soumen Indian Inst Sci Educ & Res Pune Maharashtra India

ISBN: (纸本)9783030926816;9783030926809

The OFFENSIVE ALLIANCE problem has been studied extensively during the last twenty years. A set S subset of V of vertices is an offensive alliance in an undirected graph G = (V, E) if each v is an element of N(S) has at least as many neighbours in S as it has neighbours (including itself) outside S. We study the parameterzied complexity of the OFFENSIVE ALLIANCE problem, where the aim is to find a minimum size offensive alliance. Our focus here lies on parameters that measure the structural properties of the input instance. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that the OFFENSIVE ALLIANCE problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, treewidth, pathwidth, and treedepth of the input graph. We also prove that the STRONG OFFENSIVE ALLIANCE problem parameterized by the vertex cover number of the input graph does not admit a polynomial compression unless coNP subset of NP/poly.

关键词： Defensive and offensive alliance parameterized complexity FPT W[1]-hard Treewidth

来源：评论

学校读者我要写书评

暂无评论

On the absolute and relative oriented clique problems’ time complexity

引用

Procedia Computer Science 2023年 223卷 275-282页

作者： E.M.M. Coelho H. Coelho L. Faria M.P. Ferreira S. Klein Universidade Federal de Goiás Goiânia - 74690-900 Brazil Universidade do Estado do Rio de Janeiro Rio de Janeiro - 20950-000 Brazil Universidade Federal do Rio de Janeiro - 21941-630 Brazil

Let ⃗ G = (V, A) be an oriented graph. An oriented k-coloring of ⃗ G is a partition of V into k color classes, such that there is no pair of adjacent vertices belonging to the same class and all the arcs between a pair of color classes have the same orientation. The smallest k such that ⃗ G admits an oriented k -coloring is the oriented chromatic number X o (⃗ G) = k of ⃗ G . In an oriented coloring of ⃗ G every pair of vertices with oriented distance at most 2 in ⃗ G have different colors. In 2004, Klostermeyer and MacGillivray defined the concept of an “analogue of clique” for oriented coloring in which a subgraph ⃗ H of ⃗ G is an oriented clique if every pair of vertices of ⃗ H is in an oriented distance of at most 2 in ⃗ H. The authors defined the absolute oriented clique number of ⃗ G as the number of vertices |V(H)| =  ω ao ( ⃗ G) of the largest oriented clique ⃗ H of ⃗ G and satisfies that ω ao ( ⃗ G) ≤ X o ( ⃗ G). Ever since, for almost 20 years, the time complexity status of this parameter remained unknown. The relative oriented clique number ω ao ( ⃗ G) of an oriented graph ⃗ G is the size of the largest set of vertices R, such that every pair of vertices of R is at a maximum oriented distance of 2 in R. For every oriented graph ⃗G, ω ao ( ⃗ G) ≤ ω ro ( ⃗ G) ≤ X o (⃗G ). In this paper we classify Absolute Oriented Clique - the Klostermeyer and Mac Gillivray's decision problem - proving that given an oriented graph ⃗G and a positive integer k it is NP-complete to decide whether ω ao ( ⃗ G) ≥ k. We prove that for all ε > 0, there is no polynomial-time approximation for Relative Oriented Clique and for Absolute Oriented Clique within a factor of n 1_ε , unless P = NP. Finally, we prove that Relative Oriented Clique is W[1]-complete and that Absolute Oriented Clique belongs to W[2] and is W[1]-hard.

关键词： oriented chromatic number oriented absolute clique oriented relative clique NP-complete non-appromability parameterized complexity 05C15 68Q15 68W25

来源：评论

学校读者我要写书评

暂无评论

Kernelization results for Equitable Coloring 11

Kernelization results for Equitable Coloring

引用

11th Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS)

作者： Gomes, Guilherme C. M. dos Santos, Vinicius F. Univ Fed Minas Gerais Dept Ciencia Comp Belo Horizonte MG Brazil

An n-vertex graph is equitably k-colorable if there is a proper coloring of its vertices such that each color is used either left perpendicularn/kright perpendicular or inverted right perpendicularn/kleft perpendicular times. While classic VERTEX COLORING is fixed parameter tractable under well established parameters such as pathwidth and feedback vertex set, equitable coloring is W[1]-hard. Little is known, however, about kernelization aspects of EQUITABLE COLORING. In this work, we begin this investigation by first presenting a linear kernel for the parameter distance to clique, which contrasts with the quadratic kernel for VERTEX COLORING under the same parameterization. Our main technical contribution is an OR-cross composition from MULTICOLORED CLIQUE to NUMBER LIST COLORING parameterized by vertex cover and number of colors which, along with two simple PPT reductions, implies that EQUITABLE COLORING has no polynomial kernel under the same parameterization unless NP subset of coNP/poly. (C) 2021 The Authors. Published by Elsevier B.V.

关键词： equitable coloring parameterized complexity kernelization distance to clique vertex cover cross-composition

来源：评论

学校读者我要写书评

暂无评论

r-Simple k-Path and Related Problems parameterized by k/r

引用

ACM TRANSACTIONS ON ALGORITHMS 2021年第1期17卷 1–64页

作者： Gutin, Gregory Wahlstrom, Magnus Zehavi, Meirav Royal Holloway Univ London Dept Comp Sci Egham TW20 0EX Surrey England Ben Gurion Univ Negev Dept Comp Sci Ben Gurion St 1 IL-8410501 Beer Sheva Israel

Abasi et aL (2014) introduced the following two problems. In the r-SIMPLE k-PATH problem, given a digraph G on n vertices and positive integers r, k, decide whether G has an r-simple k-path, which is a walk where every vertex occurs at most r times and the total number of vertex occurrences is k. In the (r. k)-MONOMIAL DETECTION problem, given an arithmetic circuit that succinctly encodes some polynomial P on n variables and positive integers k, r, decide whether P has a monomial of total degree k where the degree of each variable is at most r. Abasi et al. obtained randomized algorithms of running time 4((k/r)log) (r). n(O (1)) for both problems. Gabizon et al. (2015) designed deterministic 2(O((k/r)) (log r) . n(O(1)) - time algorithms for both problems (however, for the (r, k)-MONOMIAL DETECTION problem the input circuit is restricted to be non-canceling). Gabizon et al. also studied the following problem. In the p-SET (r, q)-PACKING PROBLEM, given a universe V, positive integers p, q, r, and a collection H of sets of size p whose elements belong to V, decide whether there exists a subcollection H' of H of size q where each element occurs in at most r sets of H'. Gabizon et al. obtained a deterministic 2O(((Pq/r)log r) . n(O(1))- time algorithm for p-SET (r. q)-PAcKING. The above results prove that the three problems are single-exponentially fixed-parameter tractable (FPT) parameterized by the product of two parameters, that is, k/r and log r, where k = pq for p-SET (r, q)-PACKING. Abasi et al. and Gabizon et al. asked whether the log r factor in the exponent can be avoided. Bonamy et al. (2017) answered the question for (r, k)-MONOMIAL DETEcrioN by proving that unless the Exponential Time Hypothesis (ETH) fails there is no 2(O((k/r) log r) . (n + log k)(O(1)) -time algorithm for (r, k)-MONOMIAL DETECTION, i.e., (r, k)-MONOMIAL DETECTION is unlikely to be single-exponentially FPT when parameterized by k/r alone. The question remains open for r-SIMPLE k-PATH and p

关键词： r-simple k-path (r, k)-monomial detection p-set (r, q)-packing parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Controlling Delegations in Liquid Democracy 24

Controlling Delegations in Liquid Democracy

引用

Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems

作者： Shiri Alouf-Heffetz Tanmay Inamdar Pallavi Jain Nimrod Talmon Yash More Hiren Ben Gurion University Beer Sheva Israel Indian Institute of Technology Jodhpur Jodhpur India Ben-Gurion University Beer Sheva Israel Indian Institute of Technology Gandhinagar Gandhinagar India

ISBN: (纸本)9798400704864

In liquid democracy, agents can either vote directly or delegate their vote to a different agent of their choice. This results in a power structure in which certain agents possess more voting weight than others. As a result, it opens up certain possibilities of vote manipulation, including control and bribery, that do not exist in standard voting scenarios of direct democracy. Here we formalize a certain kind of election control - in which an external agent may change certain delegation arcs - and study the computational complexity of the corresponding combinatorial problem.

关键词： computational complexity computational social choice liquid democracy manipulation parameterized complexity proxy voting

来源：评论

学校读者我要写书评

暂无评论

Completion to Chordal Distance-Hereditary Graphs: A Quartic Vertex-Kernel 1

引用

47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Crespelle, Christophe Gras, Benjamin Perez, Anthony Univ Lyon DANTE INRIA UCBL LIP UMR CNRS 5668 Lyon France Univ Trier Informat Wissensch Fachbereich 4 D-54296 Trier Germany Univ Orleans INSA Ctr Val Loire LIFO EA 4022 F-45067 Orleans France

ISBN: (数字)9783030868383

ISBN: (纸本)9783030868376;9783030868383

Given a class of graphs G and a graph G = (V, E), the aim of the G-completion problem is to find a set of at most k non-edges whose addition in G results in a graph that belongs to G. Completion to chordal or to natural subclasses of chordal graphs cover a broad range of classical NP-Complete problems, that have been extensively studied. When G coincides with the class of chordal graphs, the problem is the wellknown Minimum Fill-In problem. Other notable examples include completion to proper interval, threshold or trivially perfect graphs. Aforementioned problems are known to admit polynomial kernels, and it has been conjectured that completion to subclasses of chordal graphs further characterized by a finite number of forbidden induced subgraphs admits polynomial kernels. We investigate this line of research by considering completion to an important subclass of chordal graphs, namely chordal distance-hereditary graphs. Chordal distance-hereditary graphs are a natural generalization of trivially perfect graphs and have been extensively studied from the structural viewpoint. However, to the best of our knowledge, completion to chordal distance-hereditary graphs has not received attention so far. We thus initiate the first algorithmic study of this problem, and prove its NP-Completeness and that it admits a kernel with O(k(4)) vertices. To that aim, we rely on several known characterizations of chordal distance-hereditary graphs. In particular, such graphs admit a tree-like decomposition, so-called clique laminar tree. Unlike all aforementioned subclasses of chordal graphs, this decomposition does not correspond to a partition of the vertex set at hand. To circumvent this, we propose an approach based on the notion of clique (minimal) separator decomposition and a new characterization of chordal distance-hereditary graphs that might be of independent interest.

关键词： parameterized complexity Kernelization algorithms Chordal graphs Distance-hereditary graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：