Based on well-known complexity theory conjectures, any polynomial-time kernelization algorithm for the NP-hard Line-Cover problem produces a kernel of size Omega(k2)\documentclass[12pt]{minimal} \usepackage{amsmath} \...
详细信息
Based on well-known complexity theory conjectures, any polynomial-time kernelization algorithm for the NP-hard Line-Cover problem produces a kernel of size Omega(k2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega (k<^>2)$$\end{document}, where k is the size of the sought line cover. Motivated by the current research in massive data processing, we study the existence of kernelization algorithms with limited space and time complexity for Line-Cover. We prove that every kernelization algorithm for Line-Cover takes time Omega(nlogk+k2logk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega (n \log k + k<^>2 \log k)$$\end{document}, and present a randomized kernelization algorithm for Line-Cover that produces a kernel of size bounded by k2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k<^>2$$\end{document}, and runs in time O(nlogk+k2(logkloglogk)2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}}(n \log k + k<^>2 (\log k \log \log k)<^>2)$$\end{document} and space O(k2log2k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}}(k<^>2\log <^>kernelization algorithm k
The P-2-packing problem asks whether a graph contains k vertex-disjoint (not necessarily induced) paths each of length two. We continue the study of its kernelization algorithms, and develop a 5k-vertex kernel. (C) 20...
详细信息
The P-2-packing problem asks whether a graph contains k vertex-disjoint (not necessarily induced) paths each of length two. We continue the study of its kernelization algorithms, and develop a 5k-vertex kernel. (C) 2022 Elsevier B.V. All rights reserved.
We study algorithms for graph problems in which the graphs are of extremely large size N so that super -linear time w ( N ) or linear space Theta( N ) would become impractical. We use a parameter k to characterize the...
详细信息
We study algorithms for graph problems in which the graphs are of extremely large size N so that super -linear time w ( N ) or linear space Theta( N ) would become impractical. We use a parameter k to characterize the computational power of a normal computer that can provide additional time and space bounded by polynomials of k in dealing with the large graphs. In particular, we are interested in strict linear -time algorithms using space O ( k O (1) ). In our case studies, as examples, we present (1) a randomized greedy algorithm of time O ( N ) and space O ( k 2 ) for a parameterized version of the M AXIMAL M ATCHING problem;and (2) randomized kernelization algorithms of time O ( N ) and space O ( k O (1) ) for a number of well-known NP -hard problems. Our kernelization algorithms have their kernel sizes match the best kernel sizes by known polynomialtime kernelization algorithms with no space constraints for the problems. We also study the relationship between our proposed model and the streaming model. This study motivates a new streaming kernelization algorithm for the famous V ERTEX C OVER problem that has an optimal update time complexity while matches the best known space complexity of streaming algorithms for the problem.
The Chordal Vertex Deletion (ChVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for ChVD under the parameterization by...
详细信息
The Chordal Vertex Deletion (ChVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for ChVD under the parameterization by the solution size. Using a new Erdos-Posa-type packing/covering duality for holes in nearly chordal graphs, we present a polynomial-time algorithm that reduces any instance (G, k) of ChVD to an equivalent instance with poly(k) vertices. The existence of a polynomial kernel answers an open problem posed by Marx in 2006 [ D. Marx, "Chordal Deletion Is Fixed-Parameter Tractable," in Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 4271, Springer, 2006, pp. 37-48]. To obtain the kernelization, we develop the first poly(opt)-approximation algorithm for ChVD, which is of independent interest. In polynomial time, it either decides that G has no chordal deletion set of size k, or outputs a solution of size O(k(4) log(2) k).
In the Block Graph Deletion problem, we are given a graph G on n vertices and a positive integer k, and the objective is to check whether it is possible to delete at most k vertices from G to make it a block graph, i....
详细信息
In the Block Graph Deletion problem, we are given a graph G on n vertices and a positive integer k, and the objective is to check whether it is possible to delete at most k vertices from G to make it a block graph, i.e., a graph in which each block is a clique. In this paper, we obtain a kernel with vertices for the Block Graph Deletion problem. This is a first step to investigate polynomial kernels for deletion problems into non-trivial classes of graphs of bounded rank-width, but unbounded tree-width. Our result also implies that Chordal Vertex Deletion admits a polynomial-size kernel on diamond-free graphs. For the kernelization and its analysis, we introduce the notion of 'complete degree' of a vertex. We believe that the underlying idea can be potentially applied to other problems. We also prove that the Block Graph Deletion problem can be solved in time .
In a recent paper Soleimanfallah and Yeo proposed a kernelization algorithm for vertex cover which, for any fixed constant c, produces a kernel of order 2k - c in polynomial time. In this paper we show how their techn...
详细信息
In a recent paper Soleimanfallah and Yeo proposed a kernelization algorithm for vertex cover which, for any fixed constant c, produces a kernel of order 2k - c in polynomial time. In this paper we show how their techniques can be extended to improve the produced kernel to order 2k - c log k, for any fixed constant c. (C) 2011 Elsevier B.V. All rights reserved.
暂无评论