O(n^8) time algorithm for even-hole-free graph recognition!!!

我想出來了！
先把 cap-free 跟 triangle-free 的 structure 弄好，
重要的觀察：wheels in triangle-free cleaned graphs are cutsets!
透過 tracking 穿過 decompositions，
然後再對 extended line tree 作量身打造的 O(n+m) algorithm，
就完成了！

hope that everything is correct:]

--

Woops, 時間計算有點錯誤，
decomposition 也要乘上 O(mn)!!
這樣最多可能要到O(n^8)...
除非 2-join 可以處理？

Subgrpah of a hypercube II

直接轉貼自己 Math 板上的文章~

目前找到最好的 citation:

Embedding trees in a hypercube is NP-complete,
A Wagner, DG Corneil - SIAM Journal on Computing, 1990

換句話說，對於一棵樹 T 要判斷是不是 n-cube 的子圖是一件很難的事...
更不用說對於一般圖 A 了。

不過，對於可以放進一個 n-cube 的圖，已經有人證明了 iff conditions:

B-valuations of graphs,
I Havel, J Moravek - Czech. Math. J, 1972

例如 trees 都可以放進 n-cube 中。

最後是一篇 survey:

Embeddings in Hypercubes,
M Livingston - 1988

不過，考慮 dilation 跟 expension 好像就有一些好的演算法？
但這波研究已經過去了，我想是大家已經覺得 well-known 了吧:]

那個 iff condition 可以研究看看...
看起來不乾淨:S

Subgraph of a hypercube

PTT Math 板上出現了有趣的問題~~

"Given an n-node graph G with |V(G)| \leq 2^n, with deg(x) \leq n for all node x,
for what condition we can say that G is a subgraph of a hypercube Q_n?"

Pretty interesting question...
We know that labeling may help,
and G must be bipartite and K_{2,3}-free,
maybe I'll think about it tomorrow :S

And an algorithm for subgraph isomorphism problem in bipartite graphs?

Playground Opening!!

遊樂場開門啦，先來個開山宗旨吧XD

「本遊樂場提供各類離散數學及資訊理論相關學術研究的資訊，
歡迎各界人士遊玩以及發表意見！」

為了符合宗旨，
首先就來個連結吧(笑)

The Status of the P Versus NP Problem

簡單來說，這可是所有在讀資訊理論的人的終極目標啊！
即使遙不可及，也應該約略了解一下:]