[Back]

R. Ganian, T. Hamm, S. Ordyniak:
"The Complexity of Object Association in Multiple Object Tracking";
Talk: 35th AAAI Conference on Artificial Intelligence (AAAI-21), virtual event; 2021-02-02 - 2021-02-09; in: "The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)", AAAI Press, 35/2 (2021), ISBN: 978-1-57735-866-4; 1388 - 1396.

Object association, i.e., the identification of which observations
correspond to the same object, is a central task for
the area of multiple object tracking. Two prominent models
capturing this task have been introduced in the literature:
the Lifted Multicut model and the more recent Lifted Paths
model. Here, we carry out a detailed complexity-theoretic
study of the problems arising from these two models that is
aimed at complementing previous empirical work on object
association. We obtain a comprehensive complexity map for
both models that takes into account natural restrictions to instances
such as possible bounds on the number of frames,
number of tracked objects and branching degree, as well as
less explicit structural restrictions such as having bounded
treewidth. Our results include new fixed-parameter and XP
algorithms for the problems as well as hardness proofs which
altogether indicate that the Lifted Paths problem exhibits a
more favorable complexity behavior than Lifted Multicut.

https://publik.tuwien.ac.at/files/publik_300286.pdf