年度99
等級
書名固定參數演算法與性質測試之研究
部分章節For a long time, as long as a problem is proved to be {\bf NP}-hard, people usually avoid solving it exactly due to its computational hardness. In fact, there are strategies of designing {\em fixed-parameter algorithms}, which can be used to solve these problems exactly. A parameterized problem is a language $L\subset \Sigma^*\times \mathbb{Z}^+$, where $\Sigma$ is a finite alphabet. The first component is called the problem instance of~$L$ which has size of~$n$, and the second component, which is simply a nonnegative integer~$k$ for most cases, is called the parameter of~$L$. A {\em fixed-parameter algorithm} is an algorithm that solves a parameterized problem in $f(k)\cdot n^{O(1)}$ time for some computable function~$f$ depending solely on~$k$. When $k$ is small, a fixed-parameter algorithms runs in~$\mbox{poly}(n)$ time. In the past two decades, a variety of useful methods and techniques for demonstrating fixed-parameter tractability or designing fixed-parameter algorithms have emerged.
Besides, with recent advances in technology, we are faced with imperious need to process increasing larger amounts of data quickly. It is sometimes necessary to come out an answer without examining the whole input, yet the answer must have guaranteed accuracy. {\em Property testing} delves into the possibilities of getting answers by observing only a small fraction of the input. An input, given as a function $f:D \mapsto F$, is said to be {\em $\epsilon$-close} to
satisfying a property $\mathcal{P}$, if there exists a function $f':D\mapsto F$ that satisfies $\mathcal{P}$ and differs from $f$ in less than $\epsilon |D|$ places. Otherwise, it is said to be {\em $\epsilon$-far} from~$\mathcal{P}$. Given a specified property $\mathcal{P}$, property testing is the study of the following task: {\it Given queries or accesses to an unknown function $f$, determine in~$o(|D|)$ time whether $f$ satisfies $\mathcal{P}$ or is $\epsilon$-far from~$\mathcal{P}$}. In the past decade, property testing has become one of the most active fields in theoretical computer science.
In this dissertation, we study fixed-parameter algorithms and property testing, and introduce a new concept: {\em parameterized property testing}, which combines the characteristics of these two fields. Given a function $f:D \mapsto F$, $\epsilon\in (0,1)$, and an integer $k\in \mathbb{Z}^+$ as the parameter, a {\em parameterized property tester} for a property $\mathcal{P}$ is a property tester for~$\mathcal{P}$ which has time complexity $ hi(k,1/\epsilon)\cdot
o(|D|)$, where $ hi$ is a function that solely depends on~$k$ and~$\epsilon$. In the first half of the dissertation, we focus on a problem of determining consistency of a set of quartet topologies, which is related to evolutionary tree reconstruction. We tackle this problem and its variants through the aspects of fixed-parameter algorithms, property testing and parameterized property testing. Let $Q$ be a set of quartet topologies over an $n$-taxon set~$S$. We say
that $Q$ is {\em complete} if every quartet over~$S$ has exactly one topology in~$Q$. Given a complete $Q$, the {\em Minimum Quartet Inconsistency} (MQI) problem asks if there exists an unrooted evolutionary tree~$T$ such that at most $k$ quartet topologies in~$Q$ are not satisfied by~$T$. For the MQI problem, we present three fixed-parameter algorithms with time complexity $O(3.0446^kn + n^4)$, $O(2.0162^kn^3 + n^5)$, and $O^*((1+\varepsilon)^k)$, respectively, where $\varepsilon >0$ is an arbitrarily small constant. Next, we consider {\em tree-consistency} of quartet topologies, which is the property that all the quartet topologies in~$Q$ are satisfied by an unrooted evolutionary tree. To test if a complete $Q$ is tree-consistent, we give a non-adaptive $O(n^3/\epsilon)$ property tester with one-sided error. When $Q$ is not necessarily complete, we give a non-adaptive $O(1.7321^k k n^3/\epsilon)$ parameterized property tester with one-sided error to test if $Q$ is tree-consistent, where $k\in \mathbb{Z}^+$ is an upper bound on the number of quartets which do not have topologies in~$Q$. This parameterized property tester is uniform on~$k$.
In the second half of the dissertation, we study parameterized property testing for graph properties and focus on two {\bf NP}-hard graph theoretical problems: the {\em Vertex Cover} problem and the problem of computing {\em treewidth} of a graph. We consider the sparse model, where graphs are stored in adjacency lists and have maximum vertex degree bounded by~$d$. To test if an $n$-vertex graph has a vertex cover of size at most~$k$, we present an adaptive parameterized property tester with two-sided error, which runs in~$O(d/\epsilon)$ time for $k < n/(6d)$, and another adaptive parameterized property tester with one-sided error, which runs in~$O(kd/\epsilon)$ time for~$k < \epsilon n/4$. For testing if an $n$-vertex graph has treewidth at most~$k$, we give two adaptive parameterized property testers with two-sided error, which run in~$2^{d^{O(kd^3/\epsilon^2)}}$ time and $d^{(k/\epsilon)^{O(k^2)}} + 2^{\mbox{\scriptsize\rm poly}(k,d, 1/\epsilon)}$ time respectively. Both of them are uniform on~$k$.
全部作者林莊傑
出版日期2011-07-01
所屬計畫案固定參數演算法與性質測試之研究
備註專書