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

parameterized approximation algorithms for weighted vertex cover

THEORETICAL COMPUTER SCIENCE 2024年 1021卷

作者： Mandal, Soumen Misra, Pranabendu Rai, Ashutosh Saurabh, Saket IIT Delhi Dept Math New Delhi India Chennai Math Inst Chennai India Inst Math Sci Chennai India Univ Bergen Bergen Norway

A vertex cover of a graph is a set of vertices of the graph such that every edge has at least one endpoint in it. In this work, we study Weighted Vertex Cover with solution size as a parameter. Formally, in the (k, W)-Vertex Cover problem, given a graph G, an integer k, a positive rational W, and a weight function w:V(G)-> Q+, the question is whether G has a vertex cover of size at most k of weight at most W, with k being the parameter. An (a,b)-bi-criteria approximation algorithm for (k,W)-Vertex Cover either produces a vertex cover S such that |S|<= ak and w(S)<= bW, or decides that there is no vertex cover of size at most k of weight at most W. We obtain the following results. center dot A simple (2,2)-bi-criteria approximation algorithm for (k,W)-Vertex Cover in polynomial time by modifying the standard LP-rounding algorithm. center dot A simple exact parameterized algorithm for (k,W)-Vertex Cover running in O*(1.4656(k)) time(1). center dot A (1+epsilon,2)-approximation algorithm for (k,W)-Vertex Cover running in O*(1.4656((1-epsilon)k)) time. center dot A (1.5,1.5)-approximation algorithm for (k,W)-Vertex Cover running in O*(1.414(k)) time. center dot A (2-delta,2-delta)-approximation algorithm for (k,W)-Vertex Cover running in O*(Sigma(delta k(1-2 delta)/2 delta)(i=delta k(1-2 delta)/1+2 delta) (delta k+i delta k-2i delta 1-2 delta)) time for any delta<0.5. For example, for (1.75,1.75) and (1.9,1.9)-approximation algorithms, we get running times of O*(1.272(k)) and O*(1.151(k)) respectively. Our algorithms (expectedly) do not improve upon the running times of the existing algorithms for the unweighted version of Vertex Cover. When compared to algorithms for the weighted version, our algorithms are the first ones to the best of our knowledge which work with arbitrary weights, and they perform well when the solution size is much smaller than the total weight of the desired solution.

关键词： Weighted vertex cover parameterized algorithms Approximation algorithms parameterized approximation

来源：评论

学校读者我要写书评

暂无评论

An improved kernel and parameterized algorithm for deletion to induced matching

引用

THEORETICAL COMPUTER SCIENCE 2025年 1041卷

作者： Liu, Yuxi Xiao, Mingyu Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China

A graph is called an induced matching if each vertex in the graph is a degree-1 vertex. The DELETION TO INDUCED MATCHING problem asks whether we can delete at most kvertices from the input graph such that the remaining graph is an induced matching. This paper studies parameterized algorithms for this problem by taking the size kof the deletion set as the parameter. First, we prove a 6k-vertex kernel for this problem, improving the previous result of 7k. Second, we give an k*(1.6477k)-time and polynomial-space algorithm, improving the previous running-time bound of k*(1.7485k).

关键词： Graph algorithms Maximum induced matching parameterized algorithms Linear kernel

来源：评论

学校读者我要写书评

暂无评论

parameterized results on acyclic matchings with implications for related problems

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2025年 148卷

作者： Chaudhary, Juhi Zehavi, Meirav Tata Inst Fundamental Res Sch Technol & Comp Sci Mumbai India Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

A matching Min a graph G is an acyclic matching if the subgraph of G induced by the endpoints of the edges of M is a forest. Given a graph G and l is an element of N, ACYCLIC MATCHING asks whether G has an acyclic matching of size at least P. In this paper, we prove that assuming W[1] not subset of FPT, there does not exist any FPT-approximation algorithm for ACYCLIC MATCHING that approximates it within a constant factor when parameterized by P. Our reduction also asserts FPT-inapproximability for INDUCED MATCHING and UNIQUELY RESTRICTED MATCHING. We also consider three below-guarantee parameters for ACYCLIC MATCHING, viz. n/2 - P, MM(G) - P, and IS(G) - P, where n = V (G), MM(G) is the matching number, and IS(G) is the independence number of G. Also, we show that ACYCLIC MATCHING does not exhibit a polynomial kernel with respect to vertex cover number (or vertex deletion distance to clique) plus the size of the matching unless NP subset of coNP/poly. (c) 2024 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Acyclic matching parameterized algorithms Kernelization lower bounds Induced matching Uniquely restricted matching Below-guarantee parameterization

来源：评论

学校读者我要写书评

暂无评论

The complexity of cluster vertex splitting and company

引用

DISCRETE APPLIED MATHEMATICS 2025年 365卷 190-207页

作者： Firbas, Alexander Dobler, Alexander Holzer, Fabian Schafellner, Jakob Sorge, Manuel Villedieu, Anais Wissmann, Monika TU Wien Vienna Austria

Clustering a graph when the clusters can overlap can be seen from three different angles: We may look for cliques that cover the edges of the graph with bounded overlap, we may look to add or delete few edges to uncover the cluster structure, or we may split vertices to separate the clusters from each other. Splitting a vertex v means to remove it and to add two new copies of v and to make each previous neighbor of v adjacent with at least one of the copies. In this work, we study underlying computational problems regarding the three angles to overlapping clusterings, in particular when the overlap is small. We show that the above-mentioned covering problem is NP-complete. We then make structural observations that show that the covering viewpoint and the vertex- splitting viewpoint are equivalent, yielding NP-hardness for the vertex-splitting problem. On the positive side, we show that splitting at most k vertices to obtain a cluster graph has a problem kernel with O ( k ) vertices. Finally, we observe that combining our hardness results with structural observations and a so-called critical-clique lemma yields a simple alternative NP-hardness proof for the CLUSTER EDITING WITH VERTEX SPLITTING problem, where we add or delete edges and split vertices to obtain a cluster graph. (c) 2025 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： parameterized algorithms Data reduction Compact letter display Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Budget-feasible egalitarian allocation of conflicting jobs

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2025年第1期39卷 1-29页

作者： Gupta, Sushmita Jain, Pallavi Mohanapriya, A. Tripathi, Vikash Inst Math Sci Theoret Comp Sci Chennai Tamil Nadu India Indian Inst Technol Dept Comp Sci & Engn Jodhpur Rajasthan India

Allocating conflicting jobs among individuals while respecting a budget constraint for each individual is an optimization problem that arises in various real-world scenarios. In this paper, we consider the situation where each individual derives some satisfaction from each job. We focus on finding a feasible allocation of conflicting jobs that maximize egalitarian cost, i.e., the satisfaction of the individual who is worst-off. To the best of our knowledge, this is the first paper to combine egalitarianism, budget-feasibility, and conflict-freeness in allocations. We provide a systematic study of the computational complexity of finding budget-feasible conflict-free egalitarian allocation and show that our problem generalizes a large number of classical optimization problems. Therefore, unsurprisingly, our problem is NP-hard even for two individuals and when there is no conflict between any jobs. We show that the problem admits algorithms when studied in the realm of approximation algorithms and parameterized algorithms with a host of natural parameters that match and in some cases improve upon the running time of known algorithms.

关键词： Fair allocation Maximize egalitarian cost parameterized algorithms Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Cluster Editing with Vertex Splitting

引用

DISCRETE APPLIED MATHEMATICS 2025年 371卷 185-195页

作者： Abu-Khzam, Faisal N. Arrighi, Emmanuel Bentert, Matthias Drange, Pal Gronas Egan, Judith Gaspers, Serge Shaw, Alexis Shaw, Peter Sullivan, Blair D. Wolf, Petra Lebanese Amer Univ Beirut Lebanon CNRS UCBL EnsL LIP Villeurbanne France Univ Bergen Bergen Norway Charles Darwin Univ Casuarina NT Australia Univ New South Wales Sydney Australia Oujiang Lab Wenzhou Zhejiang Peoples R China Univ Utah Wellsville UT 84112 USA Univ Bordeaux LaBRI CNRS Bordeaux INP Bordeaux France

CLUSTER EDITING, also known as CORRELATION CLUSTERING, is a well-studied graph modification problem. In this problem, one is given a graph and the task is to perform up to k edge additions or deletions to transform it into a cluster graph, i.e., a graph consisting of a disjoint union of cliques. In this paper, we introduce a variation of CLUSTER EDITING we call CLUSTER EDITING WITH VERTEX SPLITTING that extends this model to settings where clusters may be overlapping. Specifically, we allow a new edit operation that divides a vertex into two new vertices, each with a subset of the original neighbors. This approach addresses the limitations of assuming disjoint clusters, while still inherently limiting the amount of overlap when the number of edits is small. We show that CLUSTER EDITING WITH VERTEX SPLITTING is NP-complete and fixed-parameter tractable when parameterized by the number of editing operations k. In particular, we obtain O(29k log k + n + m)-time algorithm and a 6k-vertex kernel. (c) 2025 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Graph modification Cluster Editing Vertex Splitting NP-hardness parameterized algorithms Kernelization

来源：评论

学校读者我要写书评

暂无评论

parameterized top-K algorithms

引用

THEORETICAL COMPUTER SCIENCE 2013年 470卷 105-119页

作者： Chen, Jianer Kanj, Iyad A. Meng, Jie Xia, Ge Zhang, Fenghui Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA Depaul Univ Sch Comp Chicago IL 60604 USA Samsung R&D Ctr San Jose CA 95134 USA Lafayette Coll Dept Comp Sci Easton PA 18042 USA Google Kirkland Kirkland WA 98033 USA

We study algorithmic techniques that produce the best K solutions to an instance of a parameterized NP-hard problem whose solutions are associated with a scoring function. Our parameterized top-K algorithms proceed in two stages. The first stage is a structure algorithm that on a problem instance constructs a structure of feasible size, and the second stage is an enumerating algorithm that produces the K best solutions to the instance based on the structure. We show that many algorithm-design techniques for parameterized algorithms, such as branch-and-search, color coding, and bounded treewidth, can be adopted for designing efficient structure algorithms. We then develop new techniques that support efficient enumerating algorithms. In particular, we show that for a large class of well-known NP optimization problems, there are parameterized top-K algorithms that produce the best K solutions for the problems in feasible amount of average time per solution when the parameter value is small. Finally, we investigate the relation between fixed-parameter tractability and parameterized top-K algorithms. (C) 2012 Elsevier B.V. All rights reserved.

关键词： parameterized algorithms Enumeration algorithms

来源：评论

学校读者我要写书评

暂无评论

On MAX-SAT with cardinality constraint

引用

THEORETICAL COMPUTER SCIENCE 2025年 1025卷

作者： Panolan, Fahad Yaghoubizade, Hannane Univ Leeds Sch Comp Leeds England Sharif Univ Technol Dept Math Sci Tehran Iran

We consider the weighted MAX-SAT problem with an additional constraint that at most k variables can be set to true. We call this problem k-WMAX-SAT. This problem admits a (1-1/e)-factor approximation algorithm in polynomial time [Sviridenko, Algorithmica (2001)] and it is proved that there is no (1-1/e+& varepsilon;)-factor approximation algorithm in f(k)& sdot;n(o(k)) time for Maximum Coverage, the unweighted monotone version of k-WMAX-SAT [Manurangsi, SODA 2020]. Therefore, we study two restricted versions of the problem in the realm of parameterized complexity. 1. When the input is an unweighted 2-CNF formula (the problem is called k-MAX-2SAT), we design an efficient polynomial-size approximate kernelization scheme. That is, we design a polynomial-time algorithm that given a 2-CNF formula psi and & varepsilon;>0, compresses the input instance to a 2-CNF formula psi(star) such that any c-approximate solution of psi(star) can be converted to a c(1-& varepsilon;)-approximate solution of psi in polynomial *** the input is a planar CNF formula, i.e., the variable-clause incidence graph is a planar graph, we show the following results: center dot There is an FPT algorithm for k-WMAX-SAT on planar CNF formulas that runs in 2O(k)& sdot;(C+V) time. center dot There is a polynomial-time approximation scheme for k-WMAX-SAT on planar CNF formulas that runs in time 2(O(1/& varepsilon;))& sdot;k & sdot;(C+V). The above-mentioned C and V are the number of clauses and variables of the input formul a respectively.

关键词： parameterized algorithms Approximation algorithms MAX-SAT MAX-2SAT

来源：评论

学校读者我要写书评

暂无评论

Facility location problems: A parameterized view

引用

DISCRETE APPLIED MATHEMATICS 2011年第11期159卷 1118-1130页

作者： Fellows, Michael R. Fernau, Henning Univ Trier FB Abt Informat 4 D-54286 Trier Germany Charles Darwin Univ Darwin NT 0909 Australia

Facility location problems have been investigated in the Operations Research literature from a variety of algorithmic perspectives, including those of approximation algorithms, heuristics, and linear programming. We introduce the study of these problems from the point of view of parameterized algorithms and complexity. Some applications of algorithms for these problems in the processing of semistructured documents and in computational biology are also described. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Exact algorithms parameterized algorithms NP-completeness Facility location problems Semistructured documents

来源：评论

学校读者我要写书评

暂无评论

Revisiting the parameterized complexity of Maximum-Duo Preservation String Mapping

引用

THEORETICAL COMPUTER SCIENCE 2020年 847卷 27-38页

作者： Komusiewicz, Christian Oliveira, Mateus de Oliveira Zehavi, Meirav Philipps Univ Marburg Fachbereich Math & Informat Marburg Germany Univ Bergen Bergen Norway Ben Gurion Univ Negev Beer Sheva Israel

In the MAXIMUM-DUO PRESERVATION STRING MAPPING (MAX-DUO PSM) problem, the input consists of two related strings A and B of length n and a nonnegative integer k. The objective is to determine whether there exists a mapping m from the set of positions of A to the set of positions of B that maps only to positions with the same character and preserves at least k duos, which are pairs of adjacent positions. We develop a randomized algorithm that solves MAx-Duo PSM in 4(k) . n(O(1)) time, and a deterministic algorithm that solves this problem in 6.855(k) . n (O(1)) time. The previous best known (deterministic) algorithm for this problem has (8e)(2+o(k)) . n(O(1)) running time [Beretta et al. (2016) [1,2]]. We also show that Max-Duo PSM admits a problem kernel of size O(k(3)), improving upon the previous best known problem kernel of size O (k(6)). (C) 2020 Elsevier B.V. All rights reserved.

关键词： Maximum-Duo Preservation String Mapping parameterized algorithms Kernelization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：