In the k-cut problem, we are given an edge-weighted graph G and an integer k, and have to remove a set of edges with minimum total weight so that G has at least k connected components. The current best algorithms are ...
详细信息
ISBN:
(纸本)9781538642306
In the k-cut problem, we are given an edge-weighted graph G and an integer k, and have to remove a set of edges with minimum total weight so that G has at least k connected components. The current best algorithms are an O(n((2-o(1))k)) randomized algorithm due to Karger and Stein, and an (O) over tilde (n(2k)) deterministic algorithm due to Thorup. Moreover, several 2-approximation algorithms are known for the problem (due to Saran and Vazirani, Naor and Rabani, and Ravi and Sinha). It has remained an open problem to (a) improve the runtime of exact algorithms, and (b) to get better approximation algorithms. In this paper we show an O(k(O(k)) n((2 omega/3+o(1))k))-time algorithm for k-CUT. Moreover, we show an (1 + epsilon)-approximation algorithm that runs in time O((k/epsilon)(O(k)) n(k+O(1))), and a 1.81-approximation in fixed-parameter time O(2(O(k2)) poly(n)).
The additively separable hedonic game (ASHG) is a model of coalition formation games on graphs. In this paper, we intensively and extensively investigate the computational complexity of finding several desirable solut...
详细信息
ISBN:
(纸本)9783030337926;9783030337919
The additively separable hedonic game (ASHG) is a model of coalition formation games on graphs. In this paper, we intensively and extensively investigate the computational complexity of finding several desirable solutions, such as a Nash stable solution, a maximum utilitarian solution, and a maximum egalitarian solution in ASHGs on sparse graphs including bounded-degree graphs, bounded-treewidth graphs, and nearplanar graphs. For example, we show that finding a maximum egalitarian solution is weakly NP-hard even on graphs of treewidth 2, whereas it can be solvable in polynomial time on trees. Moreover, we give a pseudo fixed parameter algorithm when parameterized by treewidth.
Both the maximum agreement forest problem and the multicut on trees problem are NP-hard, thus cannot be solved efficiently if P ≠ NP. The maximum agreement forest problem was motivated in the study of evolution trees...
详细信息
Both the maximum agreement forest problem and the multicut on trees problem are NP-hard, thus cannot be solved efficiently if P ≠ NP. The maximum agreement forest problem was motivated in the study of evolution trees in bioinformatics, in which we are given two leaf-labeled trees and are asked to find a maximum forest that is a subgraph of both trees. The multicuton trees problem has applications in networks, in which we are given a forest and a set of pairs of termianls and are asked to find a cut that separates all pairs of terminals. We develop combinatorial and algorithmic techniques that lead to improved parameterized algorithms, approximation algorithms, and kernelization algorithms for these problems. For the maximum agreement forest problem, we proceed from the bottommost level of trees and extend solutions to whole trees. With this technique, we show that the maximum agreement forest problem is fixed-parameterized tractable in general trees, resolving an open problem in this area. We also provide the first constant ratio approximation algorithm for the problem in general trees. For the multicut on trees problem, we take a new look at the problem through the eyes of vertex cover problem. This connection allows us to develop an kernelization algorithm for the problem, which gives an upper bound of O(k3) on the kernel size, significantly improving the previous best upper bound O( k6). We further exploit this connection to give a parameterized algorithm for the problem that runs in time O* (1.62k), thus improving the previous best algorithm of running time O*(2k). In the protein complex prediction problem, which comes directly from the study of bioinformatics, we are given a protein-protein interaction network, and are asked to find dense regions in this graph. We formulate this problem as a graph clustering problem and develop an algorithm to refine the results for identifying protein complexes. We test our algorithm on yeast protein- protein interaction netwo
Kidney exchange programs have been established in several countries to organize kidney exchanges between incompatible patient-donor *** core of these programs are algorithms to solve kidney exchange problem, which can...
详细信息
Kidney exchange programs have been established in several countries to organize kidney exchanges between incompatible patient-donor *** core of these programs are algorithms to solve kidney exchange problem, which can be modeled as finding a maximum weight packing of vertex-disjoint cycles with length at most some small constant L (typically 2 ≤ L ≤ 5) in a directed *** generally, the objective function is maximizing the number of possible kidney *** this paper, we study the random methods for the kidney exchange problem involving only 2-cycle and 3-cycle ***, we formal the kidney exchange problem as a parameterized *** then we propose a randomized parameterized algorithm of running time O*(5.63k3 · 22k2) by randomly partitioning the ***, by using the random divide-and-conquer technique, another randomized algorithm of running time O* (k2[log k2/2.k3[logk3]/2.42k3.22k2) is given for the parameterized kidney ***,our randomized algorithms can be extended to solve the general kidney exchange problem.
We give a new general approach for designing exact exponential-time algorithms for subset problems. In a subset problem the input implicitly describes a family of sets over a universe of size n and the task is to dete...
详细信息
We give a new general approach for designing exact exponential-time algorithms for subset problems. In a subset problem the input implicitly describes a family of sets over a universe of size n and the task is to determine whether the family contains at least one set. A typical example of a subset problem is Weighted d-SAT. Here, the input is a CNF-formula with clauses of size at most d, and an integer W. The universe is the set of variables and the variables have integer weights. The family contains all the subsets S of variables such that the total weight of the variables in S does not exceed W and setting the variables in S to 1 and the remaining variables to 0 satisfies the formula. Our approach is based on "monotone local search," where the goal is to extend a partial solution to a solution by adding as few elements as possible. More formally, in the extension problem, we are also given as input a subset X of the universe and an integer k. The task is to determine whether one can add at most k elements to X to obtain a set in the (implicitly defined) family. Our main result is that a c(k)n(O(1)) time algorithm for the extension problem immediately yields a randomized algorithm for finding a solution of any size with running time O((2 - 1/c)(n)). In many cases, the extension problem can be reduced to simply finding a solution of size at most k. Furthermore, efficient algorithms for finding small solutions have been extensively studied in the field of parameterized algorithms. Directly applying these algorithms, our theorem yields in one stroke significant improvements over the best known exponential-time algorithms for several well-studied problems, including d-HITTING SET, FEEDBACK VERTEX SET, NODE UNIQE LABEL COVER, and WEIGHTED d-SAT. Our results demonstrate an interesting and very concrete connection between parameterized algorithms and exact exponential-time algorithms. We also show how to derandomize our algorithms at the cost of a subexponential multiplic
The Square Colouring of a graph G refers to colouring of vertices of a graph such that any two distinct vertices which are at distance at most two receive different colours. In this paper, we initiate the study of a r...
详细信息
The Square Colouring of a graph G refers to colouring of vertices of a graph such that any two distinct vertices which are at distance at most two receive different colours. In this paper, we initiate the study of a related colouring problem called the subset square colouring of graphs. Broadly, the subset square colouring of a graph studies the square colouring of a dominating set of a graph using q colours. Here, the aim is to optimize the number of colours used. This also generalizes the well-studied Efficient Dominating Set problem. We show that the q-Subset Square Colouring problem with q = 2 is NP-hard even on planar bipartite graphs and the q-Subset Square Colouring problem is NP-hard even on bipartite graphs and chordal graphs. We further study the parameterized complexity of this problem when parameterized by a number of structural parameters. We further show bounds on the number of colours needed to subset square colour some graph classes.(c) 2023 Elsevier B.V. All rights reserved.
We study the Partial Information Network Query (PINQ) problem, which generalizes two problems that often arise in bioinformatics: the Alignment Network Query (ANQ) problem and the Topology-Free Network Query (TFNQ) pr...
详细信息
We study the Partial Information Network Query (PINQ) problem, which generalizes two problems that often arise in bioinformatics: the Alignment Network Query (ANQ) problem and the Topology-Free Network Query (TFNQ) problem. In both ANQ and TFNQ we have a pattern P and a graph H, and we seek a subgraph of H that resembles P. ANQ requires knowing the topology of P, while TFNQ ignores it. PINQ fits the scenario where partial information is available on the topology of P. Our main result is a parameterized algorithm that handles inputs for PINQ in which Pis a set of trees. This algorithm significantly improves the best known O* running time in solving TFNQ. We also improve the best known O* running times in solving two special cases of ANQ. (c) 2014 Elsevier B.V. All rights reserved.
暂无评论