Prafullkumar Tale

Florent Foucaud, Narges Ghareghani, Lucas Lorieau et al.

In the GEODETIC SET problem, an input is a (di)graph $G$ and integer $k$, and the objective is to decide whether there exists a vertex subset $S$ of size $k$ such that any vertex in $V(G)\setminus S$ lies on a shortest (directed) path between two vertices in $S$. The problem has been studied on undirected and directed graphs from both algorithmic and graph-theoretical perspectives. We focus on directed graphs and prove that GEODETIC SET admits a polynomial-time algorithm on ditrees, that is, digraphs with possible 2-cycles when the underlying undirected graph is a tree (after deleting possible parallel edges). This positive result naturally leads us to investigate cases where the underlying undirected graph is "close to a tree". Towards this, we show that GEODETIC SET on digraphs without 2-cycles and whose underlying undirected graph has feedback edge set number $\textsf{fen}$, can be solved in time $2^{\mathcal{O}(\textsf{fen})} \cdot n^{\mathcal{O}(1)}$, where $n$ is the number of vertices. To complement this, we prove that the problem remains NP-hard on DAGs (which do not contain 2-cycles) even when the underlying undirected graph has constant feedback vertex set number. Our last result significantly strengthens the result of Araújo and Arraes [Discrete Applied Mathematics, 2022] that the problem is NP-hard on DAGs when the underlying undirected graph is either bipartite, cobipartite or split.

Florent Foucaud, Harmender Gahlawat, Fionn Mc Inerney et al.

The VC-dimension is a well-studied and fundamental complexity measure of a set system (or hypergraph) that is central to many areas of machine learning. We establish several new results on the complexity of computing the VC-dimension. In particular, given a hypergraph $\mathcal{H}=(\mathcal{V},\mathcal{E})$, we prove that the naive $2^{\mathcal{O}(|\mathcal{V}|)}$-time algorithm is asymptotically tight under the Exponential Time Hypothesis (ETH). We then prove that the problem admits a $1$-additive fixed-parameter approximation algorithm when parameterized by the maximum degree of $\mathcal{H}$ and a fixed-parameter algorithm when parameterized by its dimension, and that these are essentially the only such exploitable structural parameters. Lastly, we consider a generalization of the problem, formulated using graphs, which captures the VC-dimension of both set systems and graphs. We design a $2^{\mathcal{O}(\rm{tw}\cdot \log \rm{tw})}\cdot |V|$-time algorithm for any graph $G=(V,E)$ of treewidth $\rm{tw}$ (which, for a set system, applies to the treewidth of its incidence graph). This is in contrast with closely related problems that require a double-exponential dependency on the treewidth (assuming the ETH).