固定參數演算法與性質測試之研究

機構典藏 > College of Engineering > Graduate Institute & Department of Computer Science and Information Engineering > Monograph > Item 987654321/120448

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/120448

Title:	固定參數演算法與性質測試之研究
Other Titles:	A Study on FixedParameter Algorithms and Property Testing
Authors:	林莊傑
Keywords:	Fixed-parameter algorithm;Property testing;Parameterized property testing;Randomized algorithms;Graph algorithm;Evolutionary tree;Quartet topology
Date:	2011-07
Issue Date:	2021-03-25 12:13:27 (UTC+8)
Abstract:	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$.
Appears in Collections:	[Graduate Institute & Department of Computer Science and Information Engineering] Monograph

Files in This Item:

File	Size	Format
index.html	0Kb	HTML	97	View/Open

Loading...