<p>Facility location problems on networks deal with locating facilities (e.g., parks, schools, or health facilities) to serve a set of clients (e.g., citizens). Many existing facility location studies assume that it is possible to (re-)locate predetermined or build new facilities. However, this assumption is not realistic for situations when relocating or building facilities would be too expensive or impossible. Recognizing this challenge, Berman et al. (Ann Oper Res 40:1–16, 1992) first propose the facility network addition modification problems (FNAMPs) on networks that aim to add a given number of new edges (e.g., constructing new roadways or bridges) to improve the client accessibility to the facilities by minimizing the total accessibility or maximum accessibility cost objectives based on clients’ distances to the facility. Yet, all existing approaches for FNAMPs are only heuristics, provide no solution quality guarantees, and fail to scale to even moderate-sized network instances. In this paper, we revisit a special case of FNAMPs with binary demands. We develop approximation algorithms and efficient heuristics for this special case under the two cost objectives. We then consider the strategic aspects of the special case of FNAMPs in which clients’ locations are private information. We design scalable strategyproof mechanisms to address FNAMPs under the two cost objectives while incentivizing clients to report their locations truthfully. We conduct extensive experiments on synthetic and real-world networks to demonstrate the effectiveness and efficiency of all proposed methods against various baselines as well as the strategyproofness of the proposed methods.</p>