Inserting　redundant　vias　is　necessary　for　improving　via　yield　in　circuit　designs.　Block　copolymer　directed　self-assembly　(DSA)　is　an　emerging　and　promising　lithography　technology　for　the　manufacture　of　vias　and　redundant　vias,　in　which　guiding　templates　are　used　to　enhance　the　resolution.　Considering　manufacturability　of　via　layer,　multiple　patterning　(MP)　lithography　is　also　needed　in　advanced　designs.　In　this　paper,　we　study　the　redundant　via　insertion　and　guiding　template　assignment　for　DSA　with　MP　problem　at　the　postrouting　stage.　We　propose　a　graph-methodology-based　solution　framework.　First,　by　analyzing　the　structure　of　guiding　templates,　we　propose　a　new　solution　expression　by　introducing　the　concept　of　multiplet　to　discard　redundant　solutions,　and　then,　honoring　the　compact　solution　expression,　we　construct　a　conflict　graph　on　the　grid　model.　Second,　we　formulate　the　problem　with　single　patterning　(SP)　as　a　constrained　maximum　weight-independent　set　problem,　for　which　a　fast　linear　interpolation　algorithm　is　introduced　to　obtain　a　local　optimal　solution.　To　avoid　undesirable　local　optima,　we　propose　an　effective　initial　solution　generation　method.　Our　framework　is　general　and　is　further　extended　to　solve　the　problem　with　double　patterning　(DP)　or　triple　patterning　(TP)　in　a　two-stage　manner.　Experimental　results　validate　the　efficiency　and　effectiveness　of　our　method.　Specifically,　compared　with　the　state-of-the-art　work　for　the　problem　with　SP,　DP,　and　TP,　our　method　can　save　58%,　82%,　and　96%　runtime,　respectively.　©　1993-2012　IEEE.