Network　Functions　Virtualization　(NFV)　and　Software-Defined　Networks　(SDN)　empower　IT　professionals　and　service　providers　to　strategically　deploy　Virtual　Network　Functions　(VNFs),　resulting　in　enhanced　services　and　security　while　minimizing　costs.　Network　services　are　dynamically　provided　through　the　deployment　of　Service　Function　Chains　(SFCs),　which　involve　selecting　and　interconnecting　physical　or　virtual　servers　hosting　VNFs.　In　this　paper,　we　address　the　online　VNF　placement　and　chaining　(VNF-PC)　problem,　aiming　to　optimize　the　overall　cost　while　satisfying　the　resource　constraints.　We　begin　by　proving　the　NP-completeness　of　finding　feasible　solutions　for　both　fixed-size　NFV　infrastructures　and　constant-size　SFCs.　Subsequently,　we　formulate　the　VNF-PC　problem　using　Integer　Linear　Programming　(ILP),　which　is　adept　at　handling　and　solving　small-scale　instances　of　the　problem.　However,　the　efficiency　of　ILP　hinges　on　the　quality　and　quantity　of　precomputed　paths,　a　factor　that　escalates　rapidly　with　the　expansion　of　NFV　infrastructure　size.　To　tackle　scalability,　we　initially　suggest　resource　homogenization　using　a　novel　multi-partite　graph,　followed　by　the　introduction　of　the　Constrained　Shortest　Path-based　Heuristic　in　multi-Partite　Graph　(CSPH-PG)　to　solve　the　VNF-PC　problem　in　polynomial　time.　Our　heuristic　focuses　on　promising　solution　areas　by　restricting　the　exploration　to　the　K　shortest　paths　that　meet　the　constraints　at　each　node,　with　K　acting　as　a　fixed　parameter　of　our　heuristic.　Extensive　simulations　demonstrate　that　our　heuristic　rapidly　converges　towards　optimal　solutions,　even　with　small　values　of　the　parameter　K　.