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

ON WEIGHTED GRAPH SEPARATION PROBLEMS AND FLOW AUGMENTATION

SIAM JOURNAL ON DISCRETE MATHEMATICS 2024年第1期38卷 170-189页

作者： Kim, Eun jung Masarik, Tomas Pilipczuk, Marcin Sharma, Roohani Wahlstrom, Magnus Univ Paris 09 PSL Res Univ CNRS UMR 7243 LAMSADE F-75016 Paris France Univ Warsaw P-02097 Warsaw Poland Max Planck Inst Informat Saarland Informat Campus D-66123 Saarbrucken Germany Univ London Royal Holloway Egham TW20 0EX England

One of the first applications of the recently introduced technique of flow augmentation [Kim et al., STOC 2022] is a fixed -parameter algorithm for the weighted version of DIRECTED FEEDBACK VERTEX SET, a landmark problem in parameterized complexity. In this article, we explore the applicability of flow augmentation to other weighted graph separation problems parameterized by the size of the cutset. We show the following: \bullet In weighted undirected graphs, MULTICUT is fixed -parameter tractable (FPT) in both the edge- and the vertex -deletion version. \bullet The weighted version of GROUP FEEDBACK VERTEX SET is FPT, even with oracle access to group operations. \bullet The weighted version of DIRECTED SUBSET FEEDBACK VERTEX SET is FPT. Our study reveals DIRECTED SYMMETRIC MULTICUT as the next important graph separation problem whose parameterized complexity remains unknown, even in the unweighted setting.

关键词： weighted multicut weighted group feedback vertex set weighted directed subset feedback vertex set parameterized complexity directed flow augmentation

来源：评论

学校读者我要写书评

暂无评论

On Structural Parameterizations of the Harmless Set Problem

引用

ALGORITHMICA 2024年第5期86卷 1475-1511页

作者： Gaikwad, Ajinkya Maity, Soumen Indian Inst Sci Educ & Res Dept Math Dr Homi Bhabha Rd Pune 411008 Maharashtra India

In this paper, we study the HARMLESS SET problem from a parameterized complexity perspective. Given a graph G=(V,E), a threshold function t : V -> N and an integer k, we study HARMLESS SET, where the goal is to find a subset of vertices S subset of V of size at least k such that every vertex v is an element of V has fewer than t(v) neighbours in S. On the positive side, we obtain fixed-parameter algorithms for the problem when parameterized by the neighbourhood diversity, the twin-cover number and the vertex integrity of the input graph. We complement two of these results from the negative side. On dense graphs, we show that the problem is W[1]-hard parameterized by cluster vertex deletion number-a natural generalization of the twin-cover number. We show that the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, and treedepth-a natural generalization of the vertex integrity. We thereby resolve one open question stated by Bazgan and Chopin (Discrete Optim 14(C):170-182, 2014) concerning the complexity of HARMLESS SET parameterized by the treewidth of the input graph. We also show that HARMLESS SET for a special case where each vertex has the threshold set to half of its degree (the so-called MAJORITY HARMLESS SET problem) is W[1]-hard when parameterized by the treewidth of the input graph. Given a graph G and an irredundant c-expression of G, we prove that HARMLESS SET can be solved in XP-time when parameterized by clique-width.

关键词： parameterized complexity FPT W[1]-hard Treewidth Feedback vertex set number Clique-width

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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 the parameterized Intractability of Determinant Maximization

引用

ALGORITHMICA 2024年第6期86卷 1731-1763页

作者： Ohsaka, Naoto CyberAgent Inc Tokyo Japan

In the Determinant Maximization problem, given an n x n positive semi-definite matrix A in Q (nxn) and an integer k, we are required to find a k x k principal submatrix of A having the maximum determinant. This problem is known to be NP-hard and further proven to be W[1]-hard with respect to k by Koutis (Inf Process Lett 100:8-13, 2006);i.e., af (k)n (O(1))-time algorithm is unlikely to exist for any computable function f. However, there is still room to explore its parameterized complexity in there stricted case, in the hope of overcoming the general-case parameterized intractability. In this study, we rule out the fixed-parameter tractability of Determinant Maximization even if an input matrix is extremely sparse or low rank, or an approximate solution is acceptable. We first prove that Determinant Maximization is NP-hard and W[1]-hard even if an input matrix is an arrowhead matrix;i.e., the underlying graph formed by nonzero entries is a star, implying that the structural sparsity is not helpful. By contrast, Determinant Maximization is known to be solvable in polynomial time on tridiagonal matrices(Al-Thani and Lee, in: LAGOS, 2021). Thereafter, we demonstrate the W[1]-hardness with respect to the rank r of an input matrix. Our result is stronger than Koutis' result in the sense that any k x k principal submatrix is sin-gular whenever k> r. We finally give evidence that it is W[1]-hard to approximate Determinant Maximization parameterized by k within a factor of 2(-c root k)for some universal constant c>0. Our hardness result is conditional on the parameterized In approximability Hypothesisposed by Lokshtanov et al. (in: SODA, 2020), which asserts that a gap version of Binary Constraint Satisfaction Problem is W[1]-hard. To complement this result, we develop an epsilon-additive approximation algorithm that runs in epsilon(-r2)r(O(r3))n(O(1))time for the rank r of an input matrix, provided that the diagonal entries are bounded.

关键词： Determinant maximization parameterized complexity Approximability

来源：评论

学校读者我要写书评

暂无评论

On kernels for d-path vertex cover

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2024年 144卷

作者： Cerveny, Radovan Choudhary, Pratibha Suchy, Ondrej Czech Tech Univ Fac Informat Technol Dept Theoret Comp Sci Thakurova 9 Prague 16000 Czech Republic

In this paper we study the kernelization of the d-Path Vertex Cover (d-PVC) problem. Given a graph G, the problem requires finding whether there exists a set of at most k vertices whose removal from G results in a graph that does not contain a path (not necessarily induced) with d vertices. It is known that d-PVC is NP-complete for d >= 2. Since the problem generalizes to d-Hitting Set, it is known to admit a kernel with O(dk(d)) edges. We improve on this by giving better kernels. Specifically, we give kernels with O(k(2)) vertices and edges for the cases when d = 4 and d = 5. Further, we give a kernel with O(k(4)d(2d+9)) vertices and edges for general d. (c) 2024 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Kernelization d -Hitting set d -Path vertex cover Expansion lemma

来源：评论

学校读者我要写书评

暂无评论

A near-linear kernel for bounded-state parsimony distance

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2024年 140卷

作者： Deen, Elise van Iersel, Leo Janssen, Remie Jones, Mark Murakami, Yukihiro Zeh, Norbert Delft Univ Technol Delft Inst Appl Math Delft Netherlands Natl Inst Publ Hlth & Environm RIVM Bilthoven Netherlands Dalhousie Univ Fac Comp Sci Halifax NS Canada

The maximum parsimony distance dMP(T1, T2) and the bounded-state maximum parsimony distance dtMP(T1, T2) measure the difference between two phylogenetic trees T1, T2 in terms of the maximum difference between their parsimony scores for any character (with t a bound on the number of states in the character, in the case of dtMP(T1, T2)). While computing dMP(T1, T2) was previously shown to be fixed-parameter tractable with a linear kernel, no such result was known for dtMP(T1, T2). In this paper, we prove that computing dtMP(T1, T2) is fixed-parameter tractable for all t. Specifically, we prove that this problem has a kernel of size O (k lgk), where k = dtMP(T1, T2). As the primary analysis tool, we introduce the concept of leg-disjoint incompatible quartets, which may be of independent interest.(c) 2023 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： parameterized complexity Kernelization Phylogenetics Phylogenetic tree Distance measure Parsimony Maximum parsimony distance

来源：评论

学校读者我要写书评

暂无评论

Getting linear time in graphs of bounded neighborhood diversity

引用

NETWORKS 2024年第3期84卷 255-277页

作者： Cordasco, Gennaro Gargano, Luisa Rescigno, Adele A. Univ Campania L Vanvitelli Dipartimento Psicol Caserta Italy Univ Salerno Dipartimento Informat Fisciano Italy Univ Campania L Vanvitelli Dipartimento Psicol Viale Ellitt I-81100 Caserta Italy

parameterized complexity, introduced to efficiently solve NP-hard problems for small values of a fixed parameter, has been recently used as a tool to speed up algorithms for tractable problems. Following this line of research, we design algorithms parameterized by neighborhood diversity (nd$$ \mathsf{nd} $$) for several graph theoretic problems in P$$ P $$: Maximum b$$ b $$-Matching, Triangle Counting and Listing, Girth, Global Minimum Vertex Cut, and Perfect Graphs Recognition. Such problems are known to admit algorithms parameterized by modular-width (mw$$ \mathsf{mw} $$) and consequently-as nd$$ \mathsf{nd} $$ is a special case of mw$$ \mathsf{mw} $$-by nd$$ \mathsf{nd} $$. However, the proposed novel algorithms allow for improving the computational complexity from time O(f(mw)n+m)$$ O\left(f\left(\mathsf{mw}\right)\cdotp n+m\right) $$-where n$$ n $$ and m$$ m $$ denote, respectively, the number of vertices and edges in the input graph-to time O(g(nd)+n+m)$$ O\left(g\left(\mathsf{nd}\right)+n+m\right) $$ which is only additive in the size of the input. Then we consider some classical NP-hard problems (Maximum independent set, Maximum clique, and Minimum dominating set) and show that for several classes of hereditary graphs, they admit linear time algorithms for sufficiently small-nonnecessarily constant-values of the neighborhood diversity parameter.

关键词： hereditary graph classes neighborhood diversity parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On structural parameterizations of load coloring

引用

DISCRETE APPLIED MATHEMATICS 2024年 342卷 181-189页

作者： Reddy, I. Vinod Indian Inst Technol Bhilai Dept Comp Sci & Engn Chhattisgarh India

Given a graph G and a positive integer k, the 2-LOAD COLORING problem is to check whether there is a 2-coloring f : V (G) -> {r, b} of G such that for every i is an element of {r, b}, there are at least k edges with both end vertices colored i. It is known that the problem is NP-complete even on special classes of graphs like regular graphs. Gutin and Jones (2014) showed that the problem is fixed-parameter tractable by giving a kernel with at most 7k vertices. Barbero et al. (2017) obtained a kernel with less than 4k vertices and O(k) edges, improving the earlier result. In this paper, we study the parameterized complexity of the problem with respect to structural graph parameters. We show that 2-LOAD COLORING cannot be solved in time f (w)no(w), unless ETH fails and it can be solved in time nO(w), where n is the size of the input graph, w is the clique-width of the graph and f is an arbitrary function of w. Next, we consider the parameters distance to cluster graphs, distance to co-cluster graphs and distance to threshold graphs, which are weaker than the parameter clique-width and show that the problem is fixed-parameter tractable (FPT) with respect to these parameters. Finally, we show that 2-LOAD COLORING is NP-complete even on bipartite graphs and split graphs. (c) 2023 Elsevier B.V. All rights reserved.

关键词： Load coloring parameterized complexity NP-complete

来源：评论

学校读者我要写书评

暂无评论

A quasi-quadratic vertex-kernel for Cograph Edge Editing

引用

DISCRETE APPLIED MATHEMATICS 2024年 357卷 282-296页

作者： Crespelle, Christophe Pellerin, Remi Thomasse, Stephan Univ Cote Azur Lab Informat Signaux & Syst Sophia Antipolis I3S 2000 Route Lucioles Les AlgorithmesBat Euclide B F-06900 Sophia Antipolis France Univ Lyon LIP Inria CNRSEnsLUCBL 46 Allee Italie F-69342 Lyon 07 France

We provide a O(k2 log k) vertex kernel for cograph edge editing. This improves a cubic kernel found by Guillemot, Havet, Paul and Perez (Guillemot et al., 2010) which involved four reduction rules. We generalize one of their rules, based on packing of induced paths of length four, by introducing t-modules, which are modules up to t edge modifications. The key fact is that large t-modules cannot be edited more than t times, and this allows to obtain a near quadratic kernel. The extra log k factor seems tricky to remove as it is necessary in the combinatorial lemma on trees which is central in our proof. Nevertheless, we think that a quadratic bound should be reachable. (c) 2024 Published by Elsevier B.V.

关键词： Cographs Kernelization algorithms parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：