Sparsest　cut　problems　are　very　important　graph　partitions,　which　have　been　widely　applied　in　expander　graphs,　Markov　chains,　and　image　segmentation.　In　this　paper,　we　study　the　edge-weighted　version　of　the　Sparse　Cut　Problem,　which　minimizes　the　ratio　of　the　total　weight　of　edges　between　blocks　and　the　total　weight　of　edges　incident　to　vertices　in　one　block.　We　first　prove　that　the　problem　is　even　NP-hard　for　an　edge-weighted　graph　with　bridges.　Then,　we　combine　and　generalize　submodular　functions　and　principal　partition　to　design　a　graph　algorithm　to　improve　the　initial　bipartition,　which　runs　in　polynomial　time　by　using　network　flow　as　its　subroutines.　©　2022　World　Scientific　Publishing　Company.