Publications
Under Review

Injective Hulls of Various Graph Classes
H. Guarnera, F. Dragan, A. Leitert
Submitted to journal.
[abstract]
[arXiv]
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, squarechordal graphs, and distancehereditary graphs are.
Graphs that have an efficiently computable injective hull are of particular interest.
A lineartime algorithm to construct the injective hull of any distancehereditary graph is provided and we show that the injective hull of several graphs from some other wellknown 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 = \biglV(G)\bigr$ and $a > 1$.
Journal Papers

Equivalence Between Pathbreadth and Strong Pathbreadth
G. Ducoffe, A. Leitert
Discrete Applied Mathematics 262, 185188, 2019.
[abstract]
[doi]
[arXiv]
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, 4864, 2019.
[abstract]
[doi]
[arXiv]
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 treebreadth 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 realworld 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 the Minimum Eccentricity Shortest Path Problem
F. Dragan, A. Leitert
Theoretical Computer Science 694, 6678, 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 NPhard 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 2approximation, a 3approximation, and an 8approximation 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.
 3Colouring for Dually Chordal Graphs and Generalisations
A. Leitert
Information Processing Letters 128, 2126, 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 NPcomplete 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 treebreadth 1.
Additionally, we show that a dually chordal graph is 3colourable if and only if it is perfect and has no clique of size four.
 LineDistortion, Bandwidth and PathLength of a Graph
F. Dragan, E. Köhler, A. Leitert
Algorithmica 77 (3), 686713, 2017.
[abstract]
[doi]
[arXiv]
We investigate the minimum linedistortion and the minimum bandwidth problems on unweighted graphs and their relations with the minimum length of a RobertsonSeymour's pathdecomposition.
The length of a pathdecomposition of a graph is the largest diameter of a bag in the decomposition.
The pathlength of a graph is the minimum length over all its pathdecompositions.
In particular, we show:
(i) if a graph $G$ can be embedded into the line with distortion $k$, then $G$ admits a RobertsonSeymour's pathdecomposition with bags of diameter at most $k$ in $G$;
(ii) for every class of graphs with pathlength bounded by a constant, there exist an efficient constantfactor approximation algorithm for the minimum linedistortion problem and an efficient constantfactor approximation algorithm for the minimum bandwidth problem;
(iii) there is an efficient 2approximation algorithm for computing the path length of an arbitrary graph;
(iv) ATfree graphs and some intersection families of graphs have pathlength at most 2;
(v) for ATfree graphs, there exist a linear time 8approximation algorithm for the minimum linedistortion problem and a linear time 4approximation 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), 299322, 2016.
[abstract]
[doi]
[arXiv]
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 NPhard in general graphs, we demonstrate that a minimum eccentricity shortest path can be found in linear time for distancehereditary graphs (generalizing the previous result for trees) and in $\mathcal{O}(n^3m)$ time for chordal graphs and for dually chordal graphs.
 Polynomialtime Algorithms for Weighted Efficient Domination
Problems in ATfree Graphs and Dually Chordal Graphs
A. Brandstädt, P. Fičur, A. Leitert, M. Milanič
Information Processing Letters 115 (2), 256262, 2015.
[abstract]
[doi]
[arXiv]
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 vertexweighted 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 polynomialtime
algorithms for the weighted efficient domination problems in the classes of dually
chordal and ATfree 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
Accepted for WADS 2021.
[abstract]
[arXiv]
Presentation: [pdf]
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, 348361, 2017.
[abstract]
[doi]
[arXiv]
Presentation: [pdf]
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 treebreadth 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 realworld 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 TreeBreadth
A. Leitert, F. Dragan
COCOA 2016, Lecture Notes in Computer Science 10043, 6276, 2016.
[abstract]
[doi]
Presentation: [pdf]
In this paper, we introduce and investigate strong treebreadth. We say
that a graph $G$ has strong treebreadth $\rho$ if there is a
treedecomposition $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 NPcomplete to determine if a given
graph has strong treebreadth $\rho$, even for $\rho = 1$; if a graph $G$
has strong treebreadth $\rho$, then we can find a treedecomposition for $G$
with treebreadth $\rho$ in $\mathcal{O}(n^2m)$ time; with some additional
restrictions, a treedecomposition with strong breadth $\rho$ can be found
in polynomial time; some graph classes including distancehereditary graphs have
strong treebreadth 1.
 Minimum Eccentricity Shortest Paths in some Structured Graph
Classes
F. Dragan, A. Leitert
WG 2015, Lecture Notes in Computer Science 9224, 189202, 2016.
[abstract]
[doi]
[arXiv]
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 NPhard in general graphs, we demonstrate that a minimum eccentricity
shortest path can be found in linear time for distancehereditary 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, 276288, 2015.
[abstract]
[doi]
Presentation: [pdf]
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 MESPproblem is NPhard on general graphs;
 a 2approximation, a 3approximation, and an 8approximation for the MESPproblem
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 MESPproblem can be solved in linear time for trees.
 LineDistortion, Bandwidth and PathLength of a Graph
F. Dragan, E. Köhler, A. Leitert
SWAT 2014, Lecture Notes in Computer Science 8503, 146157, 2014.
[abstract]
[doi]
[arXiv]
Presentation: [pdf]
We investigate the minimum linedistortion and the minimum bandwidth
problems on unweighted graphs and their relations with the minimum length
of a RobertsonSeymour's pathdecomposition. The length of a pathdecomposition
of a graph is the largest diameter of a bag in the decomposition. The pathlength
of a graph is the minimum length over all its pathdecompositions. In particular,
we show: (i) if a graph $G$ can be embedded into the line with distortion $k$,
then $G$ admits a RobertsonSeymour's pathdecomposition with bags of diameter at
most $k$ in $G$; (ii) for every class of graphs with pathlength bounded by
a constant, there exist an efficient constantfactor approximation algorithm for
the minimum linedistortion problem and an efficient constantfactor approximation
algorithm for the minimum bandwidth problem; (iii) there is an efficient 2approximation
algorithm for computing the path length of an arbitrary graph; (iv) ATfree graphs
and some intersection families of graphs have pathlength at most 2; (v) for ATfree
graphs, there exist a linear time 8approximation algorithm for the minimum linedistortion
problem and a linear time 4approximation 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, 267277, 2012.
[abstract]
[doi]
[arXiv]
Presentation: [pdf]
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 NPcomplete on alphaacyclic
hypergraphs, and is solvable in polynomial time on hypertrees, while EED is polynomial
on alphaacyclic hypergraphs and NPcomplete on hypertrees.
Thesis
 TreeBreadth of Graphs with Variants and Applications
Dissertation, Kent State University, August 2017.
[abstract]
[pdf]
[git]
The treebreadth 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 treedecompositions limiting the radius of each bag.
In this dissertation, we further investigate the treebreadth of graphs.
We present approaches to compute a treedecomposition 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 treebreadth called strong treebreadth.
Next, we present various algorithms to approach the (Connected) $r$Domination problem for graphs with bounded treebreadth.
One variant, called pathbreadth, requires the decomposition to be a path instead of a tree.
We use graphs with bounded pathbreadth to construct efficient constantfactor approximation algorithms for the bandwidth and linedistortion 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]
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]
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 branchandboundprocedure and an evolutionary
algorithm yielded the best results. Also this thesis introduces a concept that allows
analysing the input of the student.