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)...
详细信息
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.
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 remainin...
详细信息
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).
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 mat...
详细信息
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.
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 poly...
详细信息
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.
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 uncov...
详细信息
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/).
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...
详细信息
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/).
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 w...
详细信息
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.
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...
详细信息
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.
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 i...
详细信息
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.
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 map...
详细信息
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.
暂无评论