DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.99

Upper Clique Transversal on Interval Graphs and Beyond

Authors: Lars Jaffke, Paloma de Lima, and Amir Nikabadi

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract

The Upper Clique Transversal (UCT) problem asks for the size of the largest minimal set of vertices intersecting all the maximal cliques of the input graph. This problem was recently introduced by Milanič and Uno [WG 2023], who studied its complexity on several graph classes. They showed that the problem is NP-hard on chordal graphs, and gave polynomial-time algorithms for UCT on split and on proper interval graphs. They left open the complexity of UCT on interval graphs. In this work we settle this question by giving a polynomial-time algorithm for UCT on interval graphs. We show that even on the more general class of rooted directed path graphs, which can be understood as a "tree-like version" of interval graphs, the problem remains polynomial-time solvable. On the negative side, we observe as consequences of the NP-hardness proof for chordal graphs due to Milanič and Uno that the problem is NP-hard on graphs of path-independence number two (interval graphs have path-independence number one) and on well-partitioned chordal graphs which lie between split and chordal graphs.

Cite as

Lars Jaffke, Paloma de Lima, and Amir Nikabadi. Upper Clique Transversal on Interval Graphs and Beyond. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 99:1-99:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.MFCS.2026.99,
  author =	{Jaffke, Lars and de Lima, Paloma and Nikabadi, Amir},
  title =	{{Upper Clique Transversal on Interval Graphs and Beyond}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{99:1--99:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.99},
  URN =		{urn:nbn:de:0030-drops-274818},
  doi =		{10.4230/LIPIcs.MFCS.2026.99},
  annote =	{Keywords: interval graphs, rooted directed path graphs, clique transversal}
}

Search Results

Documents authored by de Lima, Paloma

Upper Clique Transversal on Interval Graphs and Beyond

Abstract

Cite as

Thanks for your feedback!

Could not send message