{'fraction_non_alphanumeric': 0.027564102564102563, 'fraction_numerical': 0.0, 'mean_word_length': 5.219123505976095, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On path cover problems with positive and negative constraints for graph-based multitarget tracking

One way to formulate a graph-based target tracking problem is to have vertices representing measurements and/or tracklets and arcs representing allowable associations. Then a solution as a set of tracks is simply a vertex-disjoint path cover of the graph. Under certain (path independence) conditions, the tracking problem can be transformed into one of finding the maximum-weight vertex-disjoint path cover of a directed acyclic graph, which can be efficiently solved using maximum-weight bipartite matching or minimum cost network flow algorithms. However, attribute information often leads to path dependence; in such a case we are interested in an associated graph theoretic problem: Find the maximum-weight vertex-disjoint path cover under “positive” and/or “negative” constraints, where a positive constraint requires, and a negative constraint prohibits, a given pair of vertices to be on the same path. In our previous paper, the case of a single positive constraint (formerly called “same-track constraint”) was considered, and an efficient algorithm to obtain the optimal solution was presented for the special case of a trellis graph. In this paper, we first present a greedy algorithm for multiple positive constraints for a general graph, based on a known algorithm for finding vertex-disjoint paths. We then consider a single negative constraint, and present a search algorithm for a general graph, and an efficient algorithm for a trellis graph.