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

Token Sliding on Graphs of Girth Five

ALGORITHMICA 2024年第2期86卷 638-655页

作者： Bartier, Valentin Bousquet, Nicolas Hanna, Jihad Mouawad, Amer E. Siebertz, Sebastian Univ Claude Bernard Lyon 1 Univ Lyon CNRS LIRIS Villeurbanne France Amer Univ Beirut Dept Comp Sci Beirut Lebanon Univ Bremen Fachbereich Math & Informat 3 Bremen Germany

In the Token Sliding problem we are given a graph G and two independent sets I-s and I-t in G of size k >= 1. The goal is to decide whether there exists a sequence of independent sets such that for all j is an ele... 详细信息

In the Token Sliding problem we are given a graph G and two independent sets I-s and I-t in G of size k >= 1. The goal is to decide whether there exists a sequence < I-1, I-2,..., I-l > of independent sets such that for all j is an element of {1,..., l - 1} the set I-j is an independent set of size k, I-1 = I-s, I-l = I-t and I-j Delta I (j+)1 = {u, v} is an element of E(G). Intuitively, we view each independent set as a collection of tokens placed on the vertices of the graph. Then, the problem asks whether there exists a sequence of independent sets that transforms I-s into I-t where at each step we are allowed to slide one token from a vertex to a neighboring vertex. In this paper, we focus on the parameterized complexity of Token Sliding parameterized by k. As shown by Bartier et al. (Algorithmica 83(9):2914-2951, 2021. https://***/10.1007/s00453-021-00848-1), the problem is W[1]-hard on graphs of girth four or less, and the authors posed the question of whether there exists a constant p >= 5 such that the problem becomes fixed-parameter tractable on graphs of girth at least p. We answer their question positively and prove that the problem is indeed fixed-parameter tractable on graphs of girth five or more, which establishes a full classification of the tractability of Token Sliding parameterized by the number of tokens based on the girth of the input graph.

关键词： Token sliding Independent set Girth Combinatorial reconfiguration parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Long directed detours: Reduction to 2-Disjoint Paths

引用

INFORMATION PROCESSING LETTERS 2024年 186卷

作者： Jacob, Ashwin Wlodarczyk, Michal Zehavi, Meirav Ben Gurion Univ Negev Beer Sheva Israel

In the L ONGEST ( s, t ) -D ETOUR problem, we look for an ( s, t ) -path that is at least k vertices longer than a shortest one. We study the parameterized complexity of L ONGEST ( s, t )-D ETOUR when parameterized by k : this falls into the research paradigm of 'parameterization above guarantee'. Whereas the problem is known to be fixedparameter tractable (FPT) on undirected graphs, the status of L ONGEST ( s, t ) -D ETOUR on directed graphs remains highly unclear: it is not even known to be solvable in polynomial time for k = 1. Recently, Fomin et al. made progress in this direction by showing that the problem is FPT on every class of directed graphs where the 3 -D ISJOINT P ATHS problem is solvable in polynomial time. We improve upon their result by weakening this assumption: we show that only a polynomial -time algorithm for 2 -D ISJOINT P ATHS is required.

关键词： Longest Path parameterized complexity Graph algorithms Disjoint paths

来源：评论

学校读者我要写书评

暂无评论

2k-Vertex Kernels for Cluster Deletion and Strong Triadic Closure

引用

Journal of Computer Science & Technology 2023年第6期38卷 1431-1439页

作者：高文宇高航 School of Information Guangdong University of Finance and EconomicsGuangzhou 510320China Department of Computer Science Rutgers UniversityPiscataway 08854U.S.A.

Cluster deletion and strong triadic closure are two important NP-complete problems that have received sig-nificant attention due to their applications in various areas,including social networks and data *** cluster deletion and strong triadic closure are closely linked by induced paths on three vertices,there are subtle differences be-tween *** some cases,the solutions of strong triadic closure and cluster deletion are quite *** this paper,we study the parameterized algorithms for these two *** specifically,we focus on the kernels of these two *** of separating the critical clique and its neighbors for analysis,we consider them as a whole,which allows us to more effectively bound the number of related *** addition,in analyzing the kernel of strong triadic closure,we introduce the concept of edge-disjoint induced path on three vertices,which enables us to obtain the lower bound of weak edge number in a more concise *** analysis demonstrates that cluster deletion and strong triadic closure both admit 2k-vertex *** results represent improvements over previously best-known kernels for both ***-more,our analysis provides additional insights into the relationship between cluster deletion and strong triadic closure.

关键词： cluster deletion strong triadic closure kernelization parameterized complexity social network

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems

引用

JOURNAL OF GLOBAL OPTIMIZATION 2024年第4期89卷 1033-1067页

作者： Gribanov, Dmitry Shumilov, Ivan Malyshev, Dmitry Zolotykh, Nikolai HSE Univ Lab Algorithms & Technol Network Anal 136 Rodionova Ulitsa Nizhnii Novgorod 603093 Russia Lobachevsky State Univ Nizhny Novgorod 23 Gagarina Ave Nizhnii Novgorod 603950 Russia Lobachevsky State Univ Nizhni Novgorod Math Future Technol Ctr 23 Gagarina Ave Nizhnii Novgorod 603950 Russia

In our paper, we consider the following general problems: check feasibility, count the number of feasible solutions, find an optimal solution, and count the number of optimal solutions in P boolean AND Zn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{\mathcal {P}}\,}}\cap {{\,\mathrm{\mathbb {Z}}\,}}<^>n$$\end{document}, assuming that P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{\mathcal {P}}\,}}$$\end{document} is a polyhedron, defined by systems Ax <= b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A x \le b$$\end{document} or Ax=b,x >= 0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Ax = b,\, x \ge 0$$\end{document} with a sparse matrix A. We develop algorithms for these problems that outperform state-of-the-art ILP and counting algorithms on sparse instances with bounded elements in terms of the computational complexity. Assuming that the matrix A has bounded elements, our complexity bounds have the form sO(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s<^>{O(n)}$$\end{document}, where s is the minimum between numbers of non-zeroes in

关键词： Integer linear programming Counting problem parameterized complexity Multipacking Multicover Stable set Vertex cover Dominating set Multiset multicover Hypergraph matching Sparse matrix

来源：评论

学校读者我要写书评

暂无评论

Digraph Coloring and Distance to Acyclicity

引用

THEORY OF COMPUTING SYSTEMS 2024年第4期68卷 986-1013页

作者： Harutyunyan, Ararat Lampis, Michael Melissinos, Nikolaos PSL Res Univ Univ Paris Dauphine CNRS UMR 7243LAMSADE Paris France

In k-DIGRAPH COLORING we are given a digraph and are asked to partition its vertices into at most k sets, so that each set induces a DAG. This well-known problem is NP-hard, as it generalizes (undirected) k-COLORING, but becomes trivial if the input digraph is acyclic. This poses the natural parameterized complexity question of what happens when the input is "almost" acyclic. In this paper we study this question using parameters that measure the input's distance to acyclicity in either the directed or the undirected sense. In the directed sense perhaps the most natural notion of distance to acyclicity is directed feedback vertex set. It is already known that, for all k >= 2, k-DIGRAPH COLORING is NP-hard on digraphs of directed feedback vertex set of size at most k + 4. We strengthen this result to show that, for all k >= 2, k-DIGRAPH COLORING is already NP-hard for directed feedback vertex set of size exactly k. This immediately provides a dichotomy, as k-DIGRAPH COLORING is trivial if directed feedback vertex set has size at most k - 1. Refining our reduction we obtain three further consequences: (i) 2-DIGRAPH COLORING is NP-hard for oriented graphs of directed feedback vertex set at most 3;(ii) for all k >= 2, k-DIGRAPH COLORING is NP-hard for graphs of feedback arc set of size at most k(2);interestingly, this leads to a second dichotomy, as we show that the problem is FPT by k if feedback arc set has size at most k(2) - 1;(iii) k-DIGRAPH COLORING is NP-hard for graphs of directed feedback vertex k, even if the maximum degree Delta is at most 4k -1;we show that this is also almost tight, as the problem becomes FPT for digraphs of directed feedback vertex set of size k and Delta <= 4k - 3. Since these results imply that the problem is also NP-hard on graphs of bounded directed treewidth, we then consider parameters that measure the distance from acyclicity of the underlying graph. On the positive side, we show that k-DIGRAPH COLORING admits an FPT algorithm parame

关键词： Digraph coloring Dichromatic number NP-completeness parameterized complexity Feedback vertex and arc sets

来源：评论

学校读者我要写书评

暂无评论

Smaller kernels for two vertex deletion problems

引用

INFORMATION PROCESSING LETTERS 2024年 186卷

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

In this paper we consider two vertex deletion problems. In the B LOCK V ERTEX D ELETION 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 result in a block graph (a graph in which every biconnected component is a clique). In the P ATHWIDTH O NE V ERTEX D ELETION 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 result in a graph with pathwidth at most one. We give a kernel for B LOCK V ERTEX D ELETION with 0(k 3 ) vertices and a kernel for P ATHWIDTH O NE V ERTEX D ELETION with 0(k 2 ) vertices. Our results improve the previous 0(k 4 ) -vertex kernel for B LOCK V ERTEX D ELETION (Agrawal et al., 2016 [1]) and the 0(k 3 ) -vertex kernel for P ATHWIDTH O NE V ERTEX D ELETION (Cygan et al., 2012 [3]).

关键词： Algorithms Graph algorithms parameterized complexity Kernelization

来源：评论

学校读者我要写书评

暂无评论

Structural Parameterizations for Two Bounded Degree Problems Revisited

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2024年第3期16卷 1-51页

作者： Lampis, Michael Vasilakis, Manolis PSL Univ Univ Paris Dauphine CNRS UMR7243 LAMSADE Paris France

We revisit two well-studied problems, Bounded Degree Vertex Deletion and Defective Coloring, where the input is a graph G and a target degree Delta, and we are asked either to edit or partition the graph so that the maximum degree becomes bounded by Delta. Both problems are known to be parameterized intractable for the most well-known structural parameters, such as treewidth. We revisit the parameterization by treewidth, as well as several related parameters and present a more fine-grained picture of the complexity of both problems. In particular, we present the following: -Both problems admit straightforward DP algorithms with table sizes (Delta+2)tw and (chi d(Delta+1))tw , respectively, where tw is the input graph's treewidth and chi d the number of available colors. We show that, under the SETH, both algorithms are essentially optimal, for any non-trivial fixed values of Delta,chi d , even if we replace treewidth by pathwidth. Along the way, we obtain an algorithm for Defective Coloring with complexity quasi-linear in the table size, thus settling the complexity of both problems for treewidth and pathwidth. -Given that the standard DP algorithm is optimal for treewidth and pathwidth, we then go on to consider the more restricted parameter tree-depth. Here, previously known lower bounds imply that, under the ETH, Bounded Vertex Degree Deletion and Defective Coloring cannot be solved in time no(td4) and no(td) , respectively, leaving some hope that a qualitatively faster algorithm than the one for treewidth may be possible. We close this gap by showing that neither problem can be solved in time no(td) , under the ETH, by employing a recursive low tree-depth construction that may be of independent interest. -Finally, we consider a structural parameter that is known to be restrictive enough to render both problems FPT: vertex cover. For both problems the best known algorithm in this setting has a super-exponential dependence of the form vcO(vc) . We show that this i

关键词： ETH parameterized complexity SETH

来源：评论

学校读者我要写书评

暂无评论

Energy Distribution Optimization in Heterogeneous Networks with Min-Max and Local Constraints as Support of Ambient Intelligence

引用

SENSORS 2025年第9期25卷 2721-2721页

作者： Aloisio, Alessandro Bloisi, Domenico D. Romano, Marco Vinci, Cosimo Univ Int Studies Rome UNINT Dept Int Humanities & Social Sci I-00147 Rome Italy Univ Salento Dept Math & Phys Ennio Giorgi I-73100 Lecce Italy

In recent years, ambient intelligence (AmI) has gained significant attention from both academia and industry. AmI seeks to create environments that automatically adapt to individuals' needs, improving comfort and efficiency. These systems typically rely on Internet of Things (IoT) frameworks, where sensors and actuators enable seamless interaction between people and their surroundings. To ensure the effective operation of AmI systems, robust wireless networks are essential, capable of integrating a wide range of devices across different environments. However, designing such networks presents challenges due to varying communication protocols, power limitations, and the computational capacities of connected devices. This paper introduces a novel approach that leverages multi-interface networks to design a heterogeneous wireless network supporting AmI systems within the IoT ecosystem. The approach centers on selecting the most appropriate communication protocols, such as Wi-Fi, Bluetooth, or 5G, to connect devices. Since many devices are battery-powered, choosing the right communication interface is critical for optimizing energy efficiency. Our primary objective is to improve network performance while extending its operational lifespan by identifying an optimal set of interfaces that balance power consumption and efficiency. We present a new model within the well-established field of multi-interface networks, designed to reduce battery consumption while maximizing network performance. Additionally, we examine the computational complexity of this model and propose two solution algorithms grounded in fixed-parameter tractability theory for specific network classes.

关键词： ambient intelligence multi-interfaces networks coverage parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Grundy Coloring and Friends, Half-Graphs, Bicliques

引用

ALGORITHMICA 2023年第1期85卷 1-28页

作者： Aboulker, Pierre Bonnet, Edouard Kim, Eun Jung Sikora, Florian PSL Univ DI ENS Paris France Univ Claude Bernard Lyon 1 Univ Lyon CNRS ENS LyonLIP UMR5668 Lyon France PSL Univ Univ Paris Dauphine LAMSADE CNRSUMR7243 Lyon France

The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order sigma, the smallest available color. The problem GRUNDY COLORING asks how many colors are needed for the most adversarial vertex ordering sigma, i.e., the maximum number of colors that the first-fit coloring requires over all possible vertex orderings. Since its inception by Grundy in 1939, GRUNDY COLORING has been examined for its structural and algorithmic aspects. A brute-force f (k)n(2k-1) -time algorithm for GRUNDY COLORING on general graphs is not difficult to obtain, where k is the number of colors required by the most adversarial vertex ordering. It was asked several times whether the dependency on k in the exponent of n can be avoided or reduced, and its answer seemed elusive until now. We prove that GRUNDY COLORING is W[1]-hard and the brute-force algorithm is essentially optimal under the Exponential Time Hypothesis, thus settling this question by the negative. The key ingredient in our W[1]-hardness proof is to use so-called half-graphs as a building block to transmit a color from one vertex to another. Leveraging the half-graphs, we also prove that b-CHROMATIC CORE is W[1]-hard, whose parameterized complexity was posed as an open question by Panolan et al. [JCSS '17]. A natural follow-up question is, how the parameterized complexity changes in the absence of (large) half-graphs. We establish fixed-parameter tractability on K-t,K-t-free graphs for b-CHROMATIC CORE and PARTIAL GRUNDY COLORING, making a step toward answering this question. The key combinatorial lemma underlying the tractability result might be of independent interest.

关键词： Grundy coloring parameterized complexity ETH lower bounds K-t,K-t-tree graphs Half-graphs

来源：评论

学校读者我要写书评

暂无评论

Above guarantee parameterization for vertex cover on graphs with maximum degree 4

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第1期45卷 1-15页

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

In the vertex cover problem the input is a graph G and an integer k, and the goal is to decide whether there is a set of vertices S of size at most k such that every edge of G is incident on at least one vertex in S. We study the vertex cover problem on graphs with maximum degree 4 and minimum degree at least 2, parameterized by r = k -n/3. We give an algorithm for this problem whose running time is O*(1.6253r). As a corollary, we obtain an O*(1.2403k)-time algorithm for vertex cover on graphs with maximum degree 4.

关键词： Vertex cover Graph algorithms parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：