Sunday, August 03, 2008

Testing colorability & hereditary graph properties

關於我論文計畫裡另一個(可能的)主題,是關於 colorability 的 testing。

雖說 monotone graph properties 與 hereditary graph properties 已經被證明為 testable,但是該結果應用了 Regularity Lemma,使得 query complexity 為深度 O(1/ε) 的 tower of 2's,遠比 exp(1/ε) 還恐怖。但是,這就像是當初演算法研究證明了某些問題為 polynomial time solvable 或 NP-hard 一樣,還是會有其它的方向可以走,譬如針對前者設計更有效率的 polynomial time (甚至 linear time) algorithms,針對後者則試圖找出 approximation algorithms 一樣。因此,就算前人已經利用了 Regularity Lemma 證明一個 property 為 testable,嘗試其他的分析或演算法來找出 poly(1/ε) 的 query complexity testers,都是可以走的方向。

現在手頭有些 papers 要先快速 view 過一遍,知道他們的精髓在哪裡,一面看一面再想關於我的問題還有什麼出路。

  • J. Komlós: Covering odd cycles. Combinatorica 17 (1997) 393-400.
  • N. Alon and M. Krevelevich: Testing k-colorability. SIAM J. Comput. 15 (2002) 211-227.
  • E. Fischer: Testing graphs for colorability properties. Random Struct. Alg. 25 (2005) 289-309.
  • N. Alon and A. Shapira: A characterization of the (natural) graph properties testable with one-sided error. SIAM J. Comput. 37 (2008) 1703-1727.
  • N. Alon and A. Shapira: A characterization of easily testable induced subgraphs. Comb., Probab. Comput. 15 (2006) 791-805.

property testing 的結果已經多到嚇死人了!如果寫篇 survey paper 應該是不錯的貢獻,可是作者的功力可得要有相當的程度才行。

除了硬著頭皮做 property testing 以外,當然也可以想一些相關的題目,譬如能不能應用到 approximation algorithms 或是 fixed-parameter algorithms 的設計之類的,都還可以再想想看。另外呢,Testing ρN-vertex coverability 在 dense graphs 上仍然是 open problem (testable or not) ? I think no.

Let us say P is the set of n-vertex graphs that have vertex cover less than k. Then P is a hereditary property.

最後,提醒自己一下,

A monotone graph property is also a hereditary graph property.
(舊文)

別老是搞不清楚了。

1 comment:

Joseph, Chuang-Chieh Lin said...

關於 k-coloring,AK 2002 這篇基本上跟 GGR1998 的方法差不多。

而 AS2006 和 AS2008 這兩篇 SICOMP 的文章的主要結果都應用了 Regularity Lemma。