Motivated by practical applications, the Labeled Correlation Clustering problem, a variant of Correlation Clustering problem, is formally defined and studied in this paper. Since the problem is NP-complete, we conside...
详细信息
Motivated by practical applications, the Labeled Correlation Clustering problem, a variant of Correlation Clustering problem, is formally defined and studied in this paper. Since the problem is NP-complete, we consider the parameterized complexities. Three different parameterizations are considered, and the corresponding parameterized complexities are studied. For the two parameterized problems which are fixed-parameter-tractable, the lower bounds of them are analyzed under SETH (Strong Exponential Time Hypothesis). (C) 2015 Elsevier B.V. All rights reserved.
We study the Hospitals/Residents with Couples problem, a variant of the classical Stable Marriage problem. This is the extension of the Hospitals/Residents problem where residents are allowed to form pairs and submit ...
详细信息
We study the Hospitals/Residents with Couples problem, a variant of the classical Stable Marriage problem. This is the extension of the Hospitals/Residents problem where residents are allowed to form pairs and submit joint rankings over hospitals. We use the framework of parameterized complexity, considering the number of couples as a parameter. We also apply a local search approach, and examine the possibilities for giving FPT algorithms applicable in this context. Furthermore, we also investigate the matching problem containing couples that is the simplified version of the Hospitals/Residents with Couples problem modeling the case when no preferences are given. (C) 2010 Elsevier B.V. All rights reserved.
We propose a general proof technique based on the Turing machine halting problem that allows us to establish membership results for the classes W[1], W[2], and W[P]. Using this technique, we prove that Perfect Code be...
详细信息
We propose a general proof technique based on the Turing machine halting problem that allows us to establish membership results for the classes W[1], W[2], and W[P]. Using this technique, we prove that Perfect Code belongs to W[l], Steiner Tree belongs to W[2], and alpha-Balanced Separator, Maximal Irredundant Set, and Bounded DFA Intersection belong to W[P]. (C) 2003 Elsevier Science (USA). All rights reserved.
We investigate the parameterized complexity of several problems formalizing cluster identification in graphs. In other words, we ask whether a graph contains a large enough and sufficiently connected subgraph. We stud...
详细信息
We investigate the parameterized complexity of several problems formalizing cluster identification in graphs. In other words, we ask whether a graph contains a large enough and sufficiently connected subgraph. We study here three relaxations of C LIQUE : s -C LUB and s -C LIQUE , in which the relaxation is focused on the distances in respectively the cluster and the original graph, and y -C OMPLETE S UBGRAPH in which the relaxation is made on the minimal degree in the cluster. As these three problems are known to be NP -hard, we study here their parameterized complexities. We prove that s -C LUB and s -C LIQUE are NP -hard even restricted to graphs of degeneracy <= 3 whenever s >= 3 , and to graphs of degeneracy <= 2 whenever s >= 5 , which is a strictly stronger result than its W[1] -hardness parameterized by the degeneracy. Concerning y -C OMPLETE S UBGRAPH , we prove that it is W[1] -hard parameterized both by the degeneracy, implying the W[1] -hardness parameterized by the number of vertices in the y-complete-subgraph, and by the number of elements outside the y -complete subgraph.
The comparison of tree structured data is widespread since trees can be used to represent wide varieties of data, such as XML data, evolutionary histories, or carbohydrate structures. Two graph-theoretical problems us...
详细信息
The comparison of tree structured data is widespread since trees can be used to represent wide varieties of data, such as XML data, evolutionary histories, or carbohydrate structures. Two graph-theoretical problems used in the comparison of such data are the problems of finding the maximum common subtree (MCT) and the minimum common supertree (MCST) of two trees. These problems generalize to the problem of finding the MCT and MCST of multiple trees (Multi-MCT and Multi-MCST, respectively). In this paper, we prove parameterized complexity hardness results for the different parameterized versions of the Multi-MCT and Multi-MCST problem under isomorphic embeddings.
In the MAXIMUM DEGREE CONTRACTION problem, the input is a graph G on n vertices, and integers k, d, and the objective is to check whether G can be transformed into a graph of maximum degree at most d, using at most k ...
详细信息
In the MAXIMUM DEGREE CONTRACTION problem, the input is a graph G on n vertices, and integers k, d, and the objective is to check whether G can be transformed into a graph of maximum degree at most d, using at most k edge contractions. A simple brute-force algorithm that checks all possible sets of edges for a solution runs in time n(O(k)). As our first result, we prove that this algorithm is asymptotically optimal, upto constants in the exponents, under Exponential Time Hypothesis (ETH). Belmonte, Golovach, van't Hof, and Paulusma studied the problem in the realm of parameterized complexity and proved, among other things, that it admits an FPT algorithm running in time (d + k)(2k) . n(O(1)) = 2(O(k log(k+d))) . n(O(1)), and remains NP-hard for every constant d >= 2 (Acta Informatica (2014)). We present a different FPT algorithm that runs in time 2(O(dk)) . n(O(1)). In particular, our algorithm runs in time 2(O(k)) . n(O(1)), for every fixed d. In the same article, the authors asked whether the problem admits a polynomial kernel, when parameterized by k + d. We answer this question in the negative and prove that it does not admit a polynomial compression unless NP subset of coNP/poly.
Given a graph G and an integer k >= 0, the NP-complete INDUCED MATCHING problem asks whether there exists ail edge subset M of size at least k such that M is a matching and no two edges of M are joined by an edge o...
详细信息
Given a graph G and an integer k >= 0, the NP-complete INDUCED MATCHING problem asks whether there exists ail edge subset M of size at least k such that M is a matching and no two edges of M are joined by an edge of G. The complexity of this problem on general graphs, as well as oil many restricted graph classes has been studied intensively. However, other than the fact that the problem is W[l]-hard on general graphs, little is known about the parameterized complexity of the problem in restricted graph classes. In this work, we provide first-time fixed-parameter tractability results for planar graphs, bounded-degree graphs, graphs with girth at least six, bipartite graphs, line graphs, and graphs of bounded treewidth. In particular, we give a linear-size problem kernel for planar graphs. (C) 2008 Elsevier B.V. All rights reserved.
We consider the problem of keeping under control the spread of harmful items in networks, such as the contagion proliferation of diseases or the diffusion of fake news. We assume the linear threshold model of diffusio...
详细信息
We consider the problem of keeping under control the spread of harmful items in networks, such as the contagion proliferation of diseases or the diffusion of fake news. We assume the linear threshold model of diffusion where each node has a threshold that measures the node's resistance to the contagion. We study the parameterized complexity of the problem: Given a network, a set of initially contaminated nodes, and two integers k and l, is it possible to limit the diffusion to at most k other nodes of the network by immunizing at most l nodes? We consider several parameters associated with the input, including the bounds k and l, the maximum node degree Delta, the number zeta of initially contaminated nodes, the treewidth, and the neighborhood diversity of the network. We first give W[1] or W[2]-hardness results for each of the considered parameters. Then we give fixed-parameter algorithms for some parameter combinations.
The NP-complete geometric covering problem Rectangle Stabbing is defined as follows: Given a set R of axis-parallel rectangles in the plane, a set L of horizontal and vertical lines in the plane, and a positive intege...
详细信息
The NP-complete geometric covering problem Rectangle Stabbing is defined as follows: Given a set R of axis-parallel rectangles in the plane, a set L of horizontal and vertical lines in the plane, and a positive integer k, select at most k of the lines such that every rectangle is intersected by at least one of the selected lines. While it is known that the problem can be approximated in polynomial time within a factor of two, its parameterized complexity with respect to the parameter k was open so far. Giving two fixed-parameter reductions, one from the W[1]-complete problem Multicolored Clique and one to the W[1]-complete problem Short Turing Machine Acceptance, we prove that Rectangle Stabbing is W[1]-complete with respect to the parameter k, which in particular means that there is no hope for an algorithm running in f(k)a <...|(RaL)-L-a| (O(1)) time. Our reductions also show the W[1]-completeness of the more general problem Set Cover on instances that "almost have the consecutive-ones property", that is, on instances whose matrix representation has at most two blocks of 1s per row. We also show that the special case of Rectangle Stabbing where all rectangles are squares of the same size is W[1]-hard. The case where the input consists of non-overlapping rectangles was open for some time and has recently been shown to be fixed-parameter tractable (Heggernes et al., Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing, 2009). By giving an algorithm running in (2k) (k) a <...|(RaL)-L-a| (O(1)) time, we show that Rectangle Stabbing is fixed-parameter tractable in the still NP-hard case where both these restrictions apply, that is, in the case of disjoint squares of the same size. This algorithm is faster than the one in Heggernes et al. (Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing, 2009) for the disjoint rectangles case. Moreover, we show fixed-parameter tractability for the restrictions where the rect
Longest common subsequence is a widely used measure to compare strings, in particular in computational biology. Recently, several variants of the longest common subsequence have been introduced to tackle the compariso...
详细信息
Longest common subsequence is a widely used measure to compare strings, in particular in computational biology. Recently, several variants of the longest common subsequence have been introduced to tackle the comparison of genomes. In particular, the Repetition Free Longest Common Subsequence (RFLCS) problem is a variant of the LCS problem that asks for a longest common subsequence of two input strings with no repetition of symbols. In this paper, we investigate the parameterized complexity of RFLCS. First, we show that the problem does not admit a polynomial kernel. Then, we present a randomized FPT algorithm for the RFLCS problem, improving the time complexity of the existent FPT algorithm. (C) 2011 Elsevier B.V. All rights reserved.
暂无评论