革新自治体ブームを背景に、旧上福岡市では、1972年から東武鉄道労働組合を基盤とした、日本社会党所属の田中喜三市長が長期執権を続けていた。しかし、特養老人ホーム建設をめぐる贈収賄の疑惑が浮上し、日本共産党が与党を離脱。自由民主党推薦の武藤が当選した。
武藤は、2市2町合併実現を最優先政策とした。旧上福岡市は、市域が狭い割には、商店街がしっかりしており、合併しない限り、これ以上の発展が見込めなかったからである。三芳町では合併反対が強いと見越した武藤は、所沢市に程近い三芳町役場を新市役所として認めるなど、最大限の譲歩をしたが、合併を巡る住民投票で三芳町民の反対は突き崩せなかった。
新市名ふじみ野は、隣の富士見市内にあるふじみ野駅に由来する。富士見市・旧大井町・旧上福岡市の2市1町の入り組んだ地域に広がるふじみ野エリアは、東入間地域のシンボル的な存在であり、先の2市2町での合併協議の中で既に新市名として決定していたものである。公募の結果とはいえその市名を踏襲した背景には、将来的に富士見市・三芳町との新たな合併を目指す戦略も見え隠れする。
ふじみ野市成立に伴い、2005年9月30日付けで失職。市長職務代理者を務めていたが、11月実施の市長選で前大井町長、島田行雄に敗れた。