Rank aggregation seeks a representative permutation for a collection of rankings and plays a central role in areas such as social choice, information retrieval, and computational biology. Two fundamental aggregation tasks are the center and median problems, which minimize the maximum and the total distance to the input permutations, respectively. While these problems are well understood under Kendall’s tau and related distances, their parameterized complexity under the Ulam metric, an edit-distance-based metric on permutations, has remained largely unexplored. In this work, we initiate a systematic study of the parameterized complexity of rank aggregation under the Ulam metric. We consider both the center and median problems, as well as their generalizations to the k-center and k-median clustering settings, parameterized by the number of centers k and the distance budget d (corresponding to the maximum distance for center variants and the total distance for median variants). Both problems are known to be NP-hard already for k = 1. We show that the Ulam k-center problem remains NP-hard when d = 1, but is fixed-parameter tractable when parameterized by k + d. Our algorithm is based on a novel local-search framework tailored to the non-local nature of Ulam distances. We complement this by proving that no polynomial kernel exists for the k+d parameterization unless NP ⊆ coNP/poly. For the Ulam k-median problem parameterized by the total distance d, we establish W[1]-hardness and provide an XP algorithm. We also provide a polynomial kernel for the parameter k + d, which in turn yields a fixed-parameter tractable algorithm.

We consider a novel vertex cover problem on temporal graphs, where the edges in the graph may change over time, and a vertex selected into the solution has a lifespan d. Specifically, a vertex selected at time t can cover all incident edges in graphs from time slot t to t+d-1. This model effectively captures the scenario of monitoring communication links via secure nodes (monitors) with limited lifespan in a dynamic network. We provide a systematic study of this problem from both theoretical and practical perspectives. We analyze its computational complexity, develop approximation and online algorithms with tight ratios, and present a parameterized algorithm and a tight quadratic kernel under fixed d. Experimental results on random and real-world temporal networks demonstrate the effectiveness of our algorithms. We believe that our systematic study not only reveals the nature of the problem itself, but also paves the way for investigating the ''sustained'' version of other problems on temporal graphs.

Distinguishing abnormal nodes from those with normal packet loss in clusters helps reduce the loss of clustered network resources. The detection performance of existing detection schemes is limited by the techniques to quantify node behaviors, and most schemes cannot avoid being misled by the falsified information. This paper presents a novel probabilistic abnormal node detection scheme CSD – Cooperative Statistical Detection – for accurate and efficient detection in the presence of falsified detection data in clustered networks. Specifically, employing the likelihood ratio test (LRT) based detection method to measure node forwarding behaviors, we propose a modified Z-score based falsification-resistant mechanism to filter out falsifications. We show that both the false alarm and missed detection probabilities can decrease exponentially if and only if the transmissions from the nodes falsifying the data are less than half of the total. Furthermore, the optimal threshold of the modified Z-score method is derived, which guarantees perfect detection of our CSD under any falsification strategy in the proposed detection model. Evaluation results validate the effectiveness, robustness, and superiority of our scheme compared to the state-of-the-art.

The Subset Feedback Vertex Set problem (SFVS) is to delete k vertices from a given graph such that in the remaining graph, any vertex in a subset T of vertices (called a terminal set) is not in a cycle. The famous Feedback Vertex Set problem is the special case of SFVS with T being the whole set of vertices. In this paper, we study exact algorithms for SFVS in Split Graphs (SFVS-S) and SFVS in Chordal Graphs (SFVS-C). SFVS-S generalizes the minimum vertex cover problem and the prize-collecting version of the maximum independent set problem in hypergraphs (PCMIS), and SFVS-C further generalizes SFVS-S. Both SFVS-S and SFVS-C are implicit 3-Hitting Set problems. However, it is not easy to solve them faster than 3-Hitting Set. In 2019, Philip, Rajan, Saurabh, and Tale (Algorithmica 2019) proved that SFVS-C can be solved in 𝒪^*(2^k) time, slightly improving the best result 𝒪^*(2.0755^k) for 3-Hitting Set. In this paper, we break the "2^k-barrier" for SFVS-S and SFVS-C by introducing an 𝒪^*(1.8192^k)-time algorithm. This achievement also indicates that PCMIS can be solved in 𝒪^*(1.8192ⁿ) time, marking the first exact algorithm for PCMIS that outperforms the trivial 𝒪^*(2ⁿ) threshold. Our algorithm uses reduction and branching rules based on the Dulmage-Mendelsohn decomposition and a divide-and-conquer method.

The facility location game is an extensively studied problem in mechanism design. In the classical model, the cost of each agent is her distance to the nearest facility. In this paper, we consider a novel model where each facility charges an entrance fee, which is a function of the facility's location. Thus, in our model, the cost of each agent is the sum of the distance to the facility and the entrance fee of the facility. The generalized model captures more real-life scenarios. In our model, the entrance fee function can be an arbitrary function, and the corresponding preferences of agents may not be single-peaked anymore: this makes the problem complex and requires new techniques in the analysis. We systematically study the model and design strategyproof mechanisms with nice approximation ratios and also complement these with nearly-tight impossibility results. Specifically, for one-facility and two-facility games, we provide upper and lower bounds for the approximation ratios given by deterministic and randomized mechanisms, with respect to the utilitarian and egalitarian objectives. Most of our bounds are tight, and these bounds are independent of the entrance fee functions. Our results also match the results of the classical model.