2026-08-21T18:34:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27481 2026-08-21T14:42:41Z ddc:004 open_access

Upper Clique Transversal on Interval Graphs and Beyond Jaffke, Lars de Lima, Paloma Nikabadi, Amir interval graphs rooted directed path graphs clique transversal 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lars Jaffke and Paloma de Lima and Amir Nikabadi 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.99 urn:nbn:de:0030-drops-274818 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.99 eng https://creativecommons.org/licenses/by/4.0/legalcode