{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreicztndryftur5kw36emfr6uqb632x7sgvwaff6blwv2v5l4in2tbe",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mhu7rilfolt2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.23193v1",
  "publishedAt": "2026-03-25T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Florent Foucaud",
    "Narges Ghareghani",
    "Lucas Lorieau",
    "Morteza Mohammad-Noori",
    "Rasa Parvini Oskuei",
    "Prafullkumar Tale"
  ],
  "textContent": "**Authors:** Florent Foucaud, Narges Ghareghani, Lucas Lorieau, Morteza Mohammad-Noori, Rasa Parvini Oskuei, Prafullkumar Tale\n\nIn 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.",
  "title": "Algorithms and Hardness for Geodetic Set on Tree-like Digraphs"
}