Journal Papers

• Injective Hulls of Various Graph Classes
  H. Guarnera, F. Dragan, A. Leitert
  Graphs and Combinatorics 38, 2017.
  [abstract] [arXiv] [doi]

  A graph is Helly if its disks satisfy the Helly property, i.e., every family of pairwise intersecting disks in $G$ has a common intersection. It is known that for every graph $G$, there exists a unique smallest Helly graph $\mathcal{H}(G)$ into which $G$ isometrically embeds; $\mathcal{H}(G)$ is called the injective hull of $G$. Motivated by this, we investigate the structural properties of the injective hulls of various graph classes. We say that a class of graphs $\mathcal{C}$ is closed under Hellification if $G \in \mathcal{C}$ implies $\mathcal{H}(G) \in C$. We identify several graph classes that are closed under Hellification. We show that permutation graphs are not closed under Hellification, but chordal graphs, square-chordal graphs, and distance-hereditary graphs are. Graphs that have an efficiently computable injective hull are of particular interest. A linear-time algorithm to construct the injective hull of any distance-hereditary graph is provided and we show that the injective hull of several graphs from some other well-known classes of graphs are impossible to compute in subexponential time. In particular, there are split graphs, cocomparability graphs, bipartite graphs $G$ such that $\mathcal{H}(G)$ contains $\Omega(a^n)$ vertices, where $n = \bigl|V(G)\bigr|$ and $a > 1$.

• Equivalence Between Pathbreadth and Strong Pathbreadth
  G. Ducoffe, A. Leitert
  Discrete Applied Mathematics 262, 185-188, 2019.
  [abstract] [arXiv] [doi]

  We say that a given graph $G = (V, E)$ has pathbreadth at most $\rho$, denoted $\mathrm{pb}(G) \leq \rho$, if there exists a Roberston and Seymour's path decomposition where every bag is contained in the $\rho$-neighbourhood of some vertex. Similarly, we say that $G$ has strong pathbreadth at most $\rho$, denoted $\mathrm{spb}(G) \leq \rho$, if there exists a Roberston and Seymour's path decomposition where every bag is the complete ρ-neighbourhood of some vertex. It is straightforward that $\mathrm{pb}(G) \leq \mathrm{spb}(G)$ for any graph $G$. Inspired from a close conjecture in [Leitert and Dragan, COCOA'16], we prove in this note that $\mathrm{spb}(G) \leq 4 \cdot \mathrm{pb}(G)$.

• Parameterized Approximation Algorithms for some Location Problems in Graphs
  A. Leitert, F. Dragan
  Theoretical Computer Science 755, 48-64, 2019.
  [abstract] [arXiv] [doi] [gif]

  We develop efficient parameterized, with additive error, approximation algorithms for the (Connected) $r$-Domination problem and the (Connected) $p$-Center problem for unweighted and undirected graphs. Given a graph $G$, we show how to construct a (connected) $\big(r + \mathcal{O}(\mu) \big)$-dominating set $D$ with $|D| \leq |D^*|$ efficiently. Here, $D^*$ is a minimum (connected) $r$-dominating set of $G$ and $\mu$ is our graph parameter, which is the tree-breadth or the cluster diameter in a layering partition of $G$. Additionally, we show that a $+ \mathcal{O}(\mu)$-approximation for the (Connected) $p$-Center problem on $G$ can be computed in polynomial time. Our interest in these parameters stems from the fact that in many real-world networks, including Internet application networks, web networks, collaboration networks, social networks, biological networks, and others, and in many structured classes of graphs these parameters are small constants.

• 3-Colouring for Dually Chordal Graphs and Generalisations
  A. Leitert
  Information Processing Letters 128, 21-26, 2017.
  [abstract] [doi]

  In this paper, we investigate the Colourability problem for dually chordal graphs and some of its generalisations. We show that the problem remains NP-complete if limited to four colours. For the case of three colours, we present a simple linear time algorithm for dismantlable graphs (which include dually chordal graphs) and present an $\mathcal{O}(n^3m)$ time algorithm for graphs with tree-breadth 1. Additionally, we show that a dually chordal graph is 3-colourable if and only if it is perfect and has no clique of size four.

• On the Minimum Eccentricity Shortest Path Problem
  F. Dragan, A. Leitert
  Theoretical Computer Science 694, 66-78, 2017.
  [abstract] [doi]

  In this paper, we introduce and investigate the Minimum Eccentricity Shortest Path (MESP) problem in unweighted graphs. It asks for a given graph to find a shortest path with minimum eccentricity. Let $n$ and $m$ respectively denote the number of vertices and edges of a given graph. We demonstrate that:

  • a minimum eccentricity shortest path plays a crucial role in obtaining the best to date approximation algorithm for a minimum distortion embedding of a graph into the line;
  • the MESP problem is NP-hard for planar bipartite graphs with maximum degree 3 and W[2]-hard for general graphs;
  • a shortest path of minimum eccentricity $k$ can be computed in $\mathcal{O}\big(n^{2k+2}m\big)$ time;
  • a 2-approximation, a 3-approximation, and an 8-approximation for the MESP problem can be computed in $\mathcal{O}(n^3)$ time, in $\mathcal{O}(nm)$ time, and in $\mathcal{O}(m)$ time, respectively;
  • in a graph with a shortest path of eccentricity $k$, a $k$-dominating set can be found in $n^{\mathcal{O}(k)}$ time.

• Line-Distortion, Bandwidth and Path-Length of a Graph
  F. Dragan, E. Köhler, A. Leitert
  Algorithmica 77 (3), 686-713, 2017.
  [abstract] [arXiv] [doi]

  We investigate the minimum line-distortion and the minimum bandwidth problems on unweighted graphs and their relations with the minimum length of a Robertson-Seymour's path-decomposition. The length of a path-decomposition of a graph is the largest diameter of a bag in the decomposition. The path-length of a graph is the minimum length over all its path-decompositions. In particular, we show: (i) if a graph $G$ can be embedded into the line with distortion $k$, then $G$ admits a Robertson-Seymour's path-decomposition with bags of diameter at most $k$ in $G$; (ii) for every class of graphs with path-length bounded by a constant, there exist an efficient constant-factor approximation algorithm for the minimum line-distortion problem and an efficient constant-factor approximation algorithm for the minimum bandwidth problem; (iii) there is an efficient 2-approximation algorithm for computing the path- length of an arbitrary graph; (iv) AT-free graphs and some intersection families of graphs have path-length at most 2; (v) for AT-free graphs, there exist a linear time 8-approximation algorithm for the minimum line-distortion problem and a linear time 4-approximation algorithm for the minimum bandwidth problem.

• Minimum Eccentricity Shortest Paths in some Structured Graph Classes
  F. Dragan, A. Leitert
  Journal of Graph Algorithms and Applications 20 (2), 299-322, 2016.
  [abstract] [arXiv] [doi]

  We investigate the Minimum Eccentricity Shortest Path problem in some structured graph classes. It asks for a given graph to find a shortest path with minimum eccentricity. Although it is NP-hard in general graphs, we demonstrate that a minimum eccentricity shortest path can be found in linear time for distance-hereditary graphs (generalizing the previous result for trees) and in $\mathcal{O}(n^3m)$ time for chordal graphs and for dually chordal graphs.

• Polynomial-time Algorithms for Weighted Efficient Domination Problems in AT-free Graphs and Dually Chordal Graphs
  A. Brandstädt, P. Fičur, A. Leitert, M. Milanič
  Information Processing Letters 115 (2), 256-262, 2015.
  [abstract] [arXiv] [doi]

  An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the vertex set of the graph. The minimum weight efficient domination problem is the problem of finding an efficient dominating set of minimum weight in a given vertex-weighted graph; the maximum weight efficient domination problem is defined similarly. We develop a framework for solving the weighted efficient domination problems based on a reduction to the maximum weight independent set problem in the square of the input graph. Using this approach, we improve on several previous results from the literature by deriving polynomial-time algorithms for the weighted efficient domination problems in the classes of dually chordal and AT-free graphs. In particular, this answers a question by Lu and Tang regarding the complexity of the minimum weight efficient domination problem in strongly chordal graphs.

Conference Papers

• Computing the Union Join and Subset Graph of Acyclic Hypergraphs in Subquadratic Time
  A. Leitert
  WADS 2021, Lecture Notes in Computer Science 12808, 571-584, 2021.
  [abstract] [arXiv] [doi] [slides] [gif]

  We investigate the two problems of computing the union join graph as well as computing the subset graph for acyclic hypergraphs and their subclasses. In the union join graph $G$ of an acyclic hypergraph $H$, each vertex of $G$ represents a hyperedge of $H$ and two vertices of $G$ are adjacent if there exits a join tree $T$ for $H$ such that the corresponding hyperedges are adjacent in $T$. The subset graph of a hypergraph $H$ is a directed graph where each vertex represents a hyperedge of $H$ and there is a directed edge from a vertex $u$ to a vertex $v$ if the hyperedge corresponding to $u$ is a subset of the hyperedge corresponding to $v$. For a given hypergraph $H = (V, \mathcal{E})$, let $n = |V|$, $m = |\mathcal{E}|$, and $N = \sum_{E \in \mathcal{E}} |E|$. We show that, if the Strong Exponential Time Hypothesis is true, both problems cannot be solved in $\mathcal{O} \bigl( N^{2 - \varepsilon} \bigr)$ time for $\alpha$-acyclic hypergraphs and any constant $\varepsilon > 0$, even if the created graph is sparse. Additionally, we present algorithms that solve both problems in $\mathcal{O} \bigl( N^2 / \log N + |G| \bigr)$ time for $\alpha$-acyclic hypergraphs, in $\mathcal{O} \bigl( N \log (n + m) + |G| \bigr)$ time for $\beta$-acyclic hypergaphs, and in $\mathcal{O} \bigl( N + |G| \bigr)$ time for $\gamma$-acyclic hypergraphs as well as for interval hypergraphs, where $|G|$ is the size of the computed graph.

• Parameterized Approximation Algorithms for some Location Problems in Graphs
  A. Leitert, F. Dragan
  COCOA 2017, Lecture Notes in Computer Science 10628, 348-361, 2017.
  [abstract] [arXiv] [doi] [slides] [gif]

  We develop efficient parameterized, with additive error, approximation algorithms for the (Connected) $r$-Domination problem and the (Connected) $p$-Center problem for unweighted and undirected graphs. Given a graph $G$, we show how to construct a (connected) $\big(r + \mathcal{O}(\mu) \big)$-dominating set $D$ with $|D| \leq |D^*|$ efficiently. Here, $D^*$ is a minimum (connected) $r$-dominating set of $G$ and $\mu$ is our graph parameter, which is the tree-breadth or the cluster diameter in a layering partition of $G$. Additionally, we show that a $+ \mathcal{O}(\mu)$-approximation for the (Connected) $p$-Center problem on $G$ can be computed in polynomial time. Our interest in these parameters stems from the fact that in many real-world networks, including Internet application networks, web networks, collaboration networks, social networks, biological networks, and others, and in many structured classes of graphs these parameters are small constants.

• On Strong Tree-Breadth
  A. Leitert, F. Dragan
  COCOA 2016, Lecture Notes in Computer Science 10043, 62-76, 2016.
  [abstract] [doi] [slides] [gif]

  In this paper, we introduce and investigate strong tree-breadth. We say that a graph $G$ has strong tree-breadth $\rho$ if there is a tree-decomposition $T$ for $G$ such that each bag $B$ of $T$ is equal to the complete $\rho$-neighbourhood of some vertex $v$ in $G$, i.e., $B = N_G^\rho[v]$. We will show that it is NP-complete to determine if a given graph has strong tree-breadth $\rho$, even for $\rho = 1$; if a graph $G$ has strong tree-breadth $\rho$, then we can find a tree-decomposition for $G$ with tree-breadth $\rho$ in $\mathcal{O}(n^2m)$ time; with some additional restrictions, a tree-decomposition with strong breadth $\rho$ can be found in polynomial time; some graph classes including distance-hereditary graphs have strong tree-breadth 1.

• Minimum Eccentricity Shortest Paths in some Structured Graph Classes
  F. Dragan, A. Leitert
  WG 20015, Lecture Notes in Computer Science 9224, 189-202, 2016.
  [abstract] [arXiv] [doi]

  We investigate the Minimum Eccentricity Shortest Path problem in some structured graph classes. It asks for a given graph to find a shortest path with minimum eccentricity. Although it is NP-hard in general graphs, we demonstrate that a minimum eccentricity shortest path can be found in linear time for distance-hereditary graphs (generalizing the previous result for trees) and in $\mathcal{O}(n^3m)$ time for chordal graphs and for dually chordal graphs.

• On the Minimum Eccentricity Shortest Path Problem
  F. Dragan, A. Leitert
  WADS 2015, Lecture Notes in Computer Science 9214, 276-288, 2015.
  [abstract] [doi] [slides]

  In this paper, we introduce and investigate the Minimum Eccentricity Shortest Path (MESP) problem in unweighted graphs. It asks for a given graph to find a shortest path with minimum eccentricity. We demonstrate that:

  • a minimum eccentricity shortest path plays a crucial role in obtaining the best to date approximation algorithm for a minimum distortion embedding of a graph into the line;
  • the MESP-problem is NP-hard on general graphs;
  • a 2-approximation, a 3-approximation, and an 8-approximation for the MESP-problem can be computed in $\mathcal{O}(n^3)$ time, in $\mathcal{O}(nm)$ time, and in linear time, respectively;
  • a shortest path of minimum eccentricity $k$ in general graphs can be computed in $\mathcal{O}(n^{2k+2}m)$ time;
  • the MESP-problem can be solved in linear time for trees.

• Line-Distortion, Bandwidth and Path-Length of a Graph
  F. Dragan, E. Köhler, A. Leitert
  SWAT 2014, Lecture Notes in Computer Science 8503, 146-157, 2014.
  [abstract] [arXiv] [doi] [slides]

  We investigate the minimum line-distortion and the minimum bandwidth problems on unweighted graphs and their relations with the minimum length of a Robertson-Seymour's path-decomposition. The length of a path-decomposition of a graph is the largest diameter of a bag in the decomposition. The path-length of a graph is the minimum length over all its path-decompositions. In particular, we show: (i) if a graph $G$ can be embedded into the line with distortion $k$, then $G$ admits a Robertson-Seymour's path-decomposition with bags of diameter at most $k$ in $G$; (ii) for every class of graphs with path-length bounded by a constant, there exist an efficient constant-factor approximation algorithm for the minimum line-distortion problem and an efficient constant-factor approximation algorithm for the minimum bandwidth problem; (iii) there is an efficient 2-approximation algorithm for computing the path- length of an arbitrary graph; (iv) AT-free graphs and some intersection families of graphs have path-length at most 2; (v) for AT-free graphs, there exist a linear time 8-approximation algorithm for the minimum line-distortion problem and a linear time 4-approximation algorithm for the minimum bandwidth problem.

• Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs
  A. Brandstädt, A. Leitert, D. Rautenbach
  ISAAC 2012, Lecture Notes in Computer Science 7676, 267-277, 2012.
  [abstract] [arXiv] [doi] [slides]

  Let $G = (V, E)$ be a graph. A vertex dominates itself and all its neighbors, i.e., every vertex $v$ in $V$ dominates its closed neighborhood $ N[v] $. A vertex set $D$ in $G$ is an efficient dominating (e.d.) set for G if for every vertex $v$ in $V$, there is exactly one $d$ in $D$ dominating $v$. An edge set $M$ is an efficient edge dominating (e.e.d.) set for $G$ if it is an efficient dominating set in the line graph $L(G)$ of $G$. The ED problem (EED problem, respectively) asks for the existence of an e.d. set (e.e.d. set, respectively) in the given graph. We give a unified framework for investigating the complexity of these problems on various classes of graphs. In particular, we solve some open problems and give linear time algorithms for ED and EED on dually chordal graphs. We extend the two problems to hypergraphs and show that ED remains NP-complete on alpha-acyclic hypergraphs, and is solvable in polynomial time on hypertrees, while EED is polynomial on alpha-acyclic hypergraphs and NP-complete on hypertrees.

Thesis

• Tree-Breadth of Graphs with Variants and Applications
  Dissertation, Kent State University, August 2017.
  [abstract] [pdf] [git]

  The tree-breadth of a graph is a recently introduced variant of the well known idea of decomposing a graph into a tree of bags. It is a parameter which adds a metric constraint to tree-decompositions limiting the radius of each bag. In this dissertation, we further investigate the tree-breadth of graphs. We present approaches to compute a tree-decomposition with small breadth for a given graph including approximation algorithms for general graphs as well as optimal solutions for special graph classes. Additionally, we introduce a variant of tree-breadth called strong tree-breadth. Next, we present various algorithms to approach the (Connected) $r$-Domination problem for graphs with bounded tree-breadth. One variant, called path-breadth, requires the decomposition to be a path instead of a tree. We use graphs with bounded path-breadth to construct efficient constant-factor approximation algorithms for the bandwidth and line-distortion problems. Motivated by these results, we introduce and investigate the new Minimum Eccentricity Shortest Path problem. We analyse the hardness of the problem, show algorithms to compute an optimal solution, and present approximation algorithms differing in quality and runtime.

• Das Dominating Induced Matching Problem für azyklische Hypergraphen
  Diploma thesis, University of Rostock, April 2012, in German.
  [abstract] [pdf] [git]

  This thesis deals with the Dominating Induced Matching problem for acyclic hypergraphs. This problem asks for a set of edges so that every edge shares a vertex with exactly one edge of this set. After dealing with the theoretical background this thesis will show that the problem can be reduced to the Weighted Independent Set problem on the square of the linegraph. At the end of the thesis some algorithms will be presentetd to solve the problem for several kinds of acyclic hypergraphs in polynomial time.

• Graphenbasierte Überprüfung unvollständiger Lösungen in Modellierungsaufgaben
  Study thesis, University of Rostock, July 2011, in German.
  [abstract] [pdf] [git]

  This thesis deals with the checking of graphs with the goal of comparing the input of a student with a reference solution for a computerbased modelling task. Therefore the principle of graph edit distance is threated theoretically and algorithms are be introduced to compute graph edit distance. Next the algorithms will be tested with the focus on runtime. In the tests a branch-and-bound-procedure and an evolutionary algorithm yielded the best results. Also this thesis introduces a concept that allows analysing the input of the student.