The　k-ary　n-cube　Qnk　is　one　of　the　most　important　interconnection　networks　for　building　network-on-chips,　data　center　networks,　and　parallel　computing　systems　owing　to　its　desirable　properties.　Since　edge　faults　grow　rapidly　and　the　path　structure　plays　a　vital　role　in　large-scale　networks　for　parallel　computing,　fault-tolerant　path　embedding　and　its　related　problems　have　attracted　extensive　attention　in　the　literature.　However,　the　existing　path　embedding　approaches　usually　only　focus　on　the　theoretical　proofs　and　produce　an　n-related　linear　fault　tolerance　since　they　are　based　on　the　traditional　fault　model,　which　allows　all　faults　to　be　adjacent　to　the　same　node.　In　this　paper,　we　design　an　efficient　fault-tolerant　Hamiltonian　path　embedding　algorithm　for　enhancing　the　fault-tolerant　capacity　of　k-ary　n-cubes.　To　facilitate　the　algorithm,　we　first　introduce　a　new　conditional　fault　model,　named　Partitioned　Edge　Fault　model　(PEF　model).　Based　on　this　model,　for　the　k-ary　n-cube　Qnk　with　n　≥　2　and　odd　k　≥　3,　we　explore　the　existence　of　a　Hamiltonian　path　in　Qnk　with　large-scale　edge　faults.　Then　we　give　an　O(N)　algorithm,　named　HP-PEF,　to　embed　the　Hamiltonian　path　into　Qnk　under　the　PEF　model,　where　N　is　the　number　of　nodes　in　Qnk.　The　performance　analysis　of　HP-PEF　shows　the　average　path　length　of　adjacent　node　pairs　in　the　Hamiltonian　path　constructed　by　HP-PEF.　We　also　make　comparisons　to　show　that　our　result　of　edge　fault　tolerance　has　exponentially　improved　other　known　results.　We　further　experimentally　show　that　HP-PEF　can　support　the　dynamic　degradation　of　average　success　rate　of　constructing　Hamiltonian　paths　when　increasing　faulty　edges　exceed　the　fault　tolerance.　©　1990-2012　IEEE.