Summary: The paper presents a new efficient solver for the min-cost flow framework that solves the MOT problem. The efficiency was achieved by exploiting special graph structures in the MOT problem and saving unnecessary computations that a more general solver would perform. The authors showed the efficiency of the new solver by comparing the running time of the new method to that of the existing solvers on multiple tracking sequences. Strengths: -- made good observations regarding where computations can be saved by carefully analyzing the flow formulation. -- provided an analytical insight regarding how the solution optimality is still maintained by the proposed method. Also, time and space complexity analyses were provided in the supplementary document. Weaknesses: -- Only running time comparisons were provided in the experiment section. Thus, it is hard to know how well the method performs in terms of outputting accurate object trajectories. It would be worth reporting numbers on other tracking metrics such as MOTA, IDF1, and IDS as well. Also, are the solutions found by SSP, FollowMe, cs2, and the propose method (muSSP) always the same? If so, please highlight the fact that the final solutions obtained by the proposed method and the baselines were all the same in Table 1. For the results in Table 2, I believe that the solutions are not the same anymore because the formulation used in Table 2 does not allow us to find the global optimal solution. In this case, the comparison for tracking accuracy is required. -- The worst time complexity of the new solver is the same as that of SSP. However, the new solver does not seem to reach the worst case in the experiments that the authors reported. What would be the case that the new solver will struggle to find the optimal solution and thus become slow? -- The paper presentation could be improved such that it would be easier for the readers to follow. Overall comment: The paper did not provide any analysis regarding the tracking accuracy of the proposed approach and the baseline approaches. The authors may have not included this in the paper because there is no difference in terms of tracking accuracy between the proposed method and the baselines. However, the authors could still compare it against other recent state-of-the-art approaches in order to show that the min-cost flow solvers achieve strong tracking performance and that it is thus worth investing on designing more efficient flow solvers for the MOT problem. Without seeing the tracking accuracy results, it is very hard for me to judge if the proposed method is an effective solution for MOT. Final comment: Some of my concerns were addressed by the authors' rebuttal. However, my biggest concern still remains. The authors did not provide any results of the proposed approach in terms of the tracking accuracy in the paper and in the supplemental document. Thus, I cannot know whether or not the tracking results that the authors generated for Table 1 and 2 are reasonably good. Because of this reason, I will keep my original score (4) for this paper. I would like to encourage the authors to provide more detailed analysis including the tracking accuracy in the paper in order to make the paper stronger.

This paper tackles a fairly difficult problem, namely data association for multi-object tracking and provides a novel algorithm based on a min-cut, max-flow formulation. Given the complexity of data association for MOT, I found the technical presentation to be especially clear (and insightful). I also give high marks for the scholarship and demonstrated familiary with both the problem and the literature. Rather than blindly applying standard algorithms to the problem, they provide a thorough analysis of the complexity of the graph and how it may be pruned in way that achieves significant computational savings. While one might view this as a very specialized result, I think the detailed analysis would be of interest outisde multi-object tracking for other problems that might benefit from graph simpification. They provide analysis and guarantees related to the various algorithmic changes. They provide convincing empirical comparisons to existing algorithms. It was the case that I had to reread various sections due to the density of the material, but I think that is the nature of this particular problem. Minor questions/comments: 1) if an object is detected in frames i-1 and i+1, but missed in i, can the algortihm recover the trajectory. It seems like the answer would be no since a flow cannot be established. 2) line 261 "We designed the graphs using three different methods" - What does this mean? I assumed the graph was based on a set of detections. Is this just saying that depending on the detection method, you would get a different graph (seems obvious) or something else? Please clarify. Post Rebuttal: The authors addressed the minor questions that I raised. I still feel strongly that this paper merits inclusion. It contributes to both multi-object tracking in a practical and important way *AND* the analysis provides insight into other network flow problems.

The paper is clearly written, and the theoretic part is solid. The experiments also show the efficiency of the proposed algorithm. Minor concerns: The running time of different algorithm can be influenced by the CPU brand, compiler options, memory speed, \etc. The authors can give a detailed spec of the platform in the appendix. ==== After rebuttal ==== I think the author resolves the reviewers' concern successfully. I tend to vote accept for the paper.