DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.19

Clustering Permutations Under the Ulam Metric: A Parameterized Complexity Study

Authors: Tian Bai, Fedor V. Fomin, Petr A. Golovach, Yash Hiren More, and Simon Wietheger

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

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.

Cite as

Tian Bai, Fedor V. Fomin, Petr A. Golovach, Yash Hiren More, and Simon Wietheger. Clustering Permutations Under the Ulam Metric: A Parameterized Complexity Study. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 19:1-19:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bai_et_al:LIPIcs.ICALP.2026.19,
  author =	{Bai, Tian and Fomin, Fedor V. and Golovach, Petr A. and More, Yash Hiren and Wietheger, Simon},
  title =	{{Clustering Permutations Under the Ulam Metric: A Parameterized Complexity Study}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{19:1--19:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.19},
  URN =		{urn:nbn:de:0030-drops-264080},
  doi =		{10.4230/LIPIcs.ICALP.2026.19},
  annote =	{Keywords: parameterized complexity, Ulam distance, rank aggregation, clustering}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2024.15

Breaking the Barrier 2^k for Subset Feedback Vertex Set in Chordal Graphs

Authors: Tian Bai and Mingyu Xiao

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract

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.

Cite as

Tian Bai and Mingyu Xiao. Breaking the Barrier 2^k for Subset Feedback Vertex Set in Chordal Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bai_et_al:LIPIcs.MFCS.2024.15,
  author =	{Bai, Tian and Xiao, Mingyu},
  title =	{{Breaking the Barrier 2^k for Subset Feedback Vertex Set in Chordal Graphs}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.15},
  URN =		{urn:nbn:de:0030-drops-205711},
  doi =		{10.4230/LIPIcs.MFCS.2024.15},
  annote =	{Keywords: Subset Feedback Vertex Set, Prize-Collecting Maximum Independent Set, Parameterized Algorithms, Split Graphs, Chordal Graphs, Dulmage-Mendelsohn Decomposition}
}

Search Results

Documents authored by Bai, Tian

Clustering Permutations Under the Ulam Metric: A Parameterized Complexity Study

Abstract

Cite as

Breaking the Barrier 2^k for Subset Feedback Vertex Set in Chordal Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message