In the CLUSTER EDITING problem, also known as CORRELATION CLUSTERING, we are given an undirected n-vertex graph G and a positive integer k. The task is to decide if G can be transformed into a cluster graph, i.e., a d...
详细信息
In the CLUSTER EDITING problem, also known as CORRELATION CLUSTERING, we are given an undirected n-vertex graph G and a positive integer k. The task is to decide if G can be transformed into a cluster graph, i.e., a disjoint union of cliques, by changing at most k adjacencies, i.e. by adding/deleting at most k edges. We give a subexponential-time parameterized algorithm that in time 2(O(root pk)) + n(O(1)) decides whether G can be transformed into a cluster graph with exactly p cliques by changing at most k adjacencies. Our algorithmic findings are complemented by the following tight lower bound on the asymptotic behavior of our algorithm. We show that unless ETH fails, for any constant 0 < sigma <= 1, there is p = Theta(k(sigma)) such that there is no algorithm deciding in time 2(o(root pk)) . n(O)(1) whether G can be transformed into a cluster graph with at most p cliques by changing at most k adjacencies. (C) 2014 Elsevier Inc. All rights reserved.
We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable (FPT) algorithms. The questions, whic...
详细信息
We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable (FPT) algorithms. The questions, which have been asked several times, are whether there is a nontrivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT)poly(N) time and outputs a solution of size f(OPT) for any computable functions t and f that are independent of N (for Clique, we want f (OPT) = omega(1))? In this paper, we show that both Clique and DomSet admit no nontrivial FPT-approximation algorithm, i.e., there is no o(OPT)-FPT-approximation algorithm for Clique and no f (OPT)-FPT-approximation algorithm for DomSet for any function f. In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential time Hypothesis [I. Dinur. ECCC, TR16-128, 2016;P. Manurangsi and P. Raghavendra, preprint, arXiv:1607.02986, 2016], which states that no 2(o(n))-time algorithm can distinguish between a satisfiable 3 SAT formula and one which is not even (1 - epsilon)-satisfiable for some constant epsilon > 0. Besides Clique and DomSet, we also rule out nontrivial FPT-approximation for the Maximum Biclique problem, the problem of finding maximum subgraphs with hereditary properties (e.g., Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs, and we rule out the k(o(1))-FPT-approximation algorithm for the Densest k-Subgraph problem.
We study the 3-COLORING problem in graphs with small diameter. In 2013, Mertzios and Spirakis showed that for n-vertex diameter-2 graphs this problem can be solved in subexponentialtime 2(O(root n log n)). Whether th...
详细信息
We study the 3-COLORING problem in graphs with small diameter. In 2013, Mertzios and Spirakis showed that for n-vertex diameter-2 graphs this problem can be solved in subexponentialtime 2(O(root n log n)). Whether the problem can be solved in polynomial time remains a well-known open question in the area of algorithmic graph theory. In this paper we present an algorithm that solves 3-COLORING in n-vertex diameter-2 graphs in time 2(O(n1/3 log2 n)). This is the first improvement upon the algorithm of Mertzios and Spirakis in the general case, i.e., without putting any further restrictions on the instance graph. In addition tOstandard branchings and reducing the problem tOan instance of 2-SAT, the crucial building block of our algorithm is a combinatorial observation about 3-colorable diameter-2 graphs, which is proven using a probabilistic argument. As a side result, we show that 3-COLORING can be solved in time 2(O((n log n)2/3)) in n-vertex diameter-3 graphs. This is the first algorithm for 3-COLORING which works in subexponentialtime for all diameter-3 graphs. We alsOdiscuss generalizations of our results tOthe weighted variant of 3-COLORING.
Given a tree T on n vertices, and k, b, s 1,., s b. N, the Tree Partitioning problem asks if at most k edges can be removed from T so that the resulting components can be grouped into b groups such that the number of ...
详细信息
Given a tree T on n vertices, and k, b, s 1,., s b. N, the Tree Partitioning problem asks if at most k edges can be removed from T so that the resulting components can be grouped into b groups such that the number of vertices in group i is s i, for i = 1,., b. The case where s 1 =. = s b = n/b, referred to as the Balanced Tree Partitioning problem, was shown to be NP-complete for trees of maximum degree at most 5, and the complexity of the problem for trees of maximum degree 4 and 3 was posed as an open question. The parameterized complexity of Balanced Tree Partitioning was also posed as an open question in another work. In this paper, we answer both open questions negatively. We show that Balanced Tree Partitioning (and hence, Tree Partitioning) is NP-complete for trees of maximum degree 3, thus closing the door on the complexity of Balanced Tree Partitioning, as the simple case when T is a path is in P. In terms of the parameterized complexity of the problems, we show that both Balanced Tree Partitioning and Tree Partitioning are W[1]-complete parameterized by k. Using a compact representation of the solution space for an instance of the problem, we present a dynamic programming algorithm for the weighted version of Tree Partitioning (and hence for that of Balanced Tree Partitioning) that runs in subexponential-time 2O(vn), adding a natural problem to the list of problems that can be solved in subexponentialtime. Finally, we extend this subexponential-time algorithm to the Weighted Graph Partitioning problem on graphs of treewidth o(n/ lg n), and we also show an application of this subexponential-time algorithm for approximating the Weighted Graph Partitioning problem.
A homomorphism from a graph G to a graph H is an edge-preserving mapping from V (G) to V (H). Let H be a fixed graph with possible loops. In the list homomorphism problem, denoted by LHom(H), the instance is a graph G...
详细信息
ISBN:
(纸本)9783031159145;9783031159138
A homomorphism from a graph G to a graph H is an edge-preserving mapping from V (G) to V (H). Let H be a fixed graph with possible loops. In the list homomorphism problem, denoted by LHom(H), the instance is a graph G, whose every vertex is equipped with a subset of V(H), called list. We ask if there exists a homomorphism from G to H, such that every vertex from G is mapped to a vertex from its list. We study the complexity of the LHOM(H) problem in intersection graphs of various geometric objects. In particular, we are interested in answering the question for what graphs H and for what types of geometric objects, the LHOM(H) problem can be solved in timesubexponential in the number of vertices of the instance. We fully resolve this question for string graphs, i.e., intersection graphs of continuous curves in the plane. Quite surprisingly, it turns out that the dichotomy coincides with the analogous dichotomy for graphs excluding a fixed path as an induced subgraph [Okrasa, Rzazewski, STACS 2021]. Then we turn our attention to intersections of fat objects. We observe that the (non) existence of subexponential-time algorithms in such classes is closely related to the size mrc (H) of a maximum reflexive clique in H, i.e., maximum number of pairwise adjacent vertices, each of which has a loop. We study the maximum value of mrc(H) that guarantees the existence of a subexponential-time algorithm for LHOM(H) in intersection graphs of (i) convex fat objects, (ii) fat similarly-sized objects, and (iii) disks. In the first two cases we obtain optimal results, by giving matching algorithms and lower bounds.
We present a series of almost settled inapproximability results for three fundamental problems. The first in our series is the subexponential-time inapproximability of the independent set problem, a question studied i...
详细信息
ISBN:
(纸本)9780769551357
We present a series of almost settled inapproximability results for three fundamental problems. The first in our series is the subexponential-time inapproximability of the independent set problem, a question studied in the area of parameterized complexity. The second is the hardness of approximating the bipartite induced matching problem on bounded-degree bipartite graphs. The last in our series is the tight hardness of approximating the k-hypergraph pricing problem, a fundamental problem arising from the area of algorithmic game theory. In particular, assuming the Exponential time Hypothesis, our two main results are: For any r larger than some constant, any r-approximation algorithm for the independent set problem must run in at least 2n(1-epsilon/r1+epsilon) time. This nearly matches the upper bound of 2(n/r) [23]. It also improves some hardness results in the domain of parameterized complexity (e.g., [26], [19]). For any k larger than some constant, there is no polynomial time min {k(1-epsilon), n(1/2-epsilon)}-approximation algorithm for the k-hypergraph pricing problem, where is the number of vertices in an input graph. This almost matches the upper bound of min {O(k), (O) over tilde(root n)} (by Balcan and Blum [3] and an algorithm in this paper). We note an interesting fact that, in contrast to n(1/2-epsilon) hardness for polynomial-timealgorithms, the k-hypergraph pricing problem admits n(delta) approximation for any delta > 0 in quasi-polynomial time. This puts this problem in a rare approximability class in which approximability thresholds can be improved significantly by allowing algorithms to run in quasi-polynomial time. The proofs of our hardness results rely on unexpectedly tight connections between the three problems. First, we establish a connection between the first and second problems by proving a new graph-theoretic property related to an induced matching number of dispersers. Then, we show that the n(1/2-epsilon) hardness of the last problem f
In this paper we obtain parameterized subexponential-time algorithms for p-KEMENY AGGREGATION (p-KAGG) - a problem in social choice theory - and for p-ONE-SIDED CROSSING MINIMIZATION (p-OSCM) - a problem in graph draw...
详细信息
ISBN:
(纸本)9783642192210
In this paper we obtain parameterized subexponential-time algorithms for p-KEMENY AGGREGATION (p-KAGG) - a problem in social choice theory - and for p-ONE-SIDED CROSSING MINIMIZATION (p-OSCM) - a problem in graph drawing (see the introduction for definitions). These algorithms run in time O*(2(O (root k log k))), where k is the parameter, and significantly improve the previous best algorithms with running times O*(1.403(k)) and O*(1.4656(k)), respectively(1). We also study natural "above-guarantee" versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p-DIRECTED FEEDBACK ARC SET. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of "votes" in the input to p-KAGG is odd the above guarantee version can still be solved in time O*(2(O(root k log k))), while if it is even then the problem cannot have a subexponentialtime algorithm unless the exponential time hypothesis fails (equivalently, unless FPT=M[1]).
暂无评论