13 papers · 1 filter
Structural parameterizations of Geodetic Set on directed (acyclic) graphs
Laurent Beaudou, Florent Foucaud, Lucas Lorieau +1
In DIRECTED GEODETIC SET, we are given a (directed) graph and seek a small solution set such that every vertex lies on a shortest directed path between two verti…
Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
Florent Foucaud, Narges Ghareghani, Lucas Lorieau +3
In the GEODETIC SET problem, an input is a (di)graph and integer , and the objective is to decide whether there exists a vertex subset of size such that any vertex i…
A Finer View of the Parameterized Landscape of Labeled Graph Contractions
Yashaswini Mathur, Prafullkumar Tale
We study the \textsc{Labeled Contractibility} problem, where the input consists of two vertex-labeled graphs and , and the goal is to determine whether can be obtained f…
Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
R. Krithika, V. K. Kutty Malu, Roohani Sharma +1
In this work, we initiate the complexity study of Biclique Contraction and Balanced Biclique Contraction. In these problems, given as input a graph G and an integer k, the objectiv…
Parameterized complexity of isometric path partition: treewidth and diameter
Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud +2
We investigate the parameterized complexity of the Isometric Path Partition problem when parameterized by the treewidth () of the input graph, arguably one of the most…
Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar +1
We investigate fine-grained algorithmic aspects of identification problems in graphs and set systems, with a focus on Locating-Dominating Set and Test Cover. We prove the (tight) c…