Journal of Graph Algorithms and Applications
https://jgaa-v4.cs.brown.edu/index.php/jgaa
<p>The <span class="emph">Journal of Graph Algorithms and Applications</span> (<span class="emph">JGAA</span>) is a peer-reviewed scientific journal devoted to the publication of high-quality research papers on the analysis, design, implementation, and applications of graph algorithms. <span class="emph">JGAA</span> is supported by distinguished advisory and editorial boards, has high scientific standards and is distributed in electronic form. <span style="font-size: 0.875rem;"> </span><span class="emph">JGAA</span> is a diamond open access journal that charges no author fees. Also, <span style="font-size: 0.875rem;">JGAA is </span><a style="background-color: #ffffff; font-size: 0.875rem;" href="https://dblp.org/db/journals/jgaa/index.html" data-auth="NotApplicable" data-linkindex="5">indexed by DBLP</a><span style="font-size: 0.875rem;">.</span></p>en-USfabrizio.montecchiani@unipg.it (Publishing Editor) ( )Thu, 16 May 2024 16:44:54 +0000OJS 3.3.0.18http://blogs.law.harvard.edu/tech/rss60On Critical Node Problems with Vulnerable Vertices
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2922
<p>A vertex pair in an undirected graph is called \emph{connected} if<br>the two vertices are connected by a path. In the NP-hard<br>\textsc{Critical Node Problem}~(CNP), the input is an undirected<br>graph~$G$ with integers~$k$ and~$x$, and the question is whether one<br>can transform~$G$ by deleting at most~$k$ vertices into a graph whose total<br>number of connected vertex pairs is at most~$x$. In this work, we<br>introduce and study two NP-hard variants of CNP where a subset of<br>the vertices is marked as \emph{vulnerable}, and we aim to obtain a<br>graph with at most~$x$ connected vertex pairs containing at least one vulnerable vertex. In the first variant, which generalizes CNP,<br>we may delete vulnerable and non-vulnerable vertices. In<br>the second variant, we may only delete non-vulnerable vertices.</p> <p>We perform a parameterized complexity study of both problems. For example, we show that both problems are FPT with respect to~$k+x$. Furthermore, in the case of deletable vulnerable nodes, we provide a polynomial kernel for the parameter~$vc+k$, where~$vc$ is the vertex cover number. In the case of non-deletable vulnerable nodes, we prove NP-hardness even when there is only one vulnerable node.</p>Jannik Schestag, Niels Gruettemeier, Christian Komusiewicz, Frank Sommer
Copyright (c) 2024 Jannik Schestag, Niels Gruettemeier, Christian Komusiewicz, Frank Sommer
https://creativecommons.org/licenses/by/4.0
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2922Thu, 16 May 2024 00:00:00 +0000Linear-algebraic implementation of Fibonacci heap
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2926
<p>In the paper, we demonstrate that modern priority queues can be expressed in terms of linear algebraic operations. Specifically, we showcase one of the arguably most asymptotically faster known priority queues — the Fibonacci heap. By employing our approach, we prove that for the Dijkstra, Prim, Brandes, and greedy maximal independent set algorithms, their theoretical complexity remains the same for both combinatorial and linear-algebraic cases.</p>Danila Demin, Dmitry Sirotkin, Stanislav Moiseev
Copyright (c) 2024 Danila Demin, Dmitry Sirotkin, Stanislav Moiseev
https://creativecommons.org/licenses/by/4.0
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2926Thu, 16 May 2024 00:00:00 +0000The role of twins in computing planar supports of hypergraphs
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2927
<pre>A <em>support</em> or <em>realization </em>of a hypergraph $\mathcal{H}$ is a graph \(G\) on the same vertex set as \(\mathcal{H}\) such that </pre> <pre>for each hyperedge of $\mathcal{H}$ it holds that its vertices induce a </pre> <pre> connected subgraph of $G$.</pre> <pre> The NP-hard problem of finding a <em>planar</em> support</pre> <pre> has applications in hypergraph drawing</pre> <pre> and network design.</pre> <pre> Previous algorithms for the problem assume that</pre> <pre><em> twins</em>---pairs of vertices that are in precisely</pre> <pre> the same hyperedges---can safely be removed from the input hypergraph.</pre> <pre> We prove that this assumption is generally wrong,</pre> <pre> yet that the number of twins</pre> <pre> necessary for a hypergraph </pre> <pre> to have a planar support only depends on its number of hyperedges.</pre> <pre> We give an explicit upper bound on the number of twins</pre> <pre> necessary</pre> <pre> for a hypergraph with \(m\) hyperedges</pre> <pre> to have an \(r\)-outerplanar support,</pre> <pre> which depends only on \(r\) and \(m\).</pre> <pre> Since all additional twins can be safely removed,</pre> <pre> we obtain a linear-time</pre> <pre> algorithm for computing \(r\)-outerplanar supports</pre> <pre> for hypergraphs with \(m\) hyperedges</pre> <pre> </pre> <pre> if $m$ and $r$</pre> <pre> are constant; in other words, the problem is fixed-parameter linear-time</pre> <pre> solvable with respect to the parameters $m$ and $r$.</pre>René van Bevern, Iyad Kanj, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge
Copyright (c) 2024 René van Bevern, Iyad Kanj, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge
https://creativecommons.org/licenses/by/4.0
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2927Thu, 16 May 2024 00:00:00 +0000The Minimum Consistent Spanning Subset Problem on Trees
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2929
<pre>Given a vertex-colored edge-weighted graph, the <em>minimum consistent subset</em> (MCS) problem asks for a minimum subset $S$ of vertices such that every vertex $v\notin S$ has the same color as its nearest neighbor in $S$. <br>This problem is NP-complete. A recent result of Dey, Maheshwari, and Nandy (2021) gives a polynomial-time algorithm for the MCS problem on two-colored trees. A <em>block</em> is a maximal connected set of vertices of the same color. <br>We introduce a variant of the MCS problem, namely the <em>minimum consistent spanning subset</em> problem, for which we require the set $S$ to contain a vertex from every block of the graph such that every vertex $v\notin S$ has a nearest neighbor in $S$ that is in the same block as $v$. <br>We observe that this problem is NP-hard on general graphs. We present a polynomial-time algorithm for this problem on trees.</pre>Ahmad Biniaz, Parham Khamsepour
Copyright (c) 2024 Ahmad Biniaz, Parham Khamsepour
https://creativecommons.org/licenses/by/4.0
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2929Thu, 16 May 2024 00:00:00 +0000Thrackles, Superthrackles and the Hanani-Tutte Theorem
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2930
<pre>A thrackle is a drawing of a graph in which any two vertex-disjoint edges cross exactly once and incident edges do not cross. A graph that has a thrackle drawing is thracklable. <br>In the past three decades, mathematicians investigated a number of variations of thrackles by relaxing or changing the required number of crossings on edges or restricting the placement of vertices on the surface (e.g., restricting to outerdrawings, in which vertices are restricted to a boundary curve of the surface).</pre> <pre> </pre> <pre>A graph is superthracklable if it can be drawn so that any two edges cross exactly once. <br>We provide a simple proof for the following: a graph can be drawn on the plane so that every two edges cross an odd number of times if and only if it is superthracklable on the plane. </pre> <pre> </pre> <pre>A graph is outersuperthracklable if it has a drawing on a disc in which every vertex is on the boundary of the disc and every pair of edges cross exactly once. <br>We introduce some natural generalisations of outersuperthracklable graphs and we show that these classes of graphs are equivalent.</pre> <pre> </pre> <pre>Lastly, using the Hanani-Tutte characterisation of planar graphs we show that for any surface $\Sigma$, there is a relationship between the class of graphs that are not embeddable on $\Sigma$ and the class of graphs that are not superthracklable with respect to $\Sigma$. <br>More specifically, we show how to construct, from any forbidden minor $G$ for embeddability in $\Sigma$, two infinite families of graphs that are not superthracklable with respect to $\Sigma$. This sheds further light on</pre> <pre>the relationship between some of Archdeacon and Stor's forbidden configurations for superthrackles and Kuratowski's forbidden minors for planarity.</pre>Hooman Dehkordi, Graham Farr
Copyright (c) 2024 Hooman Dehkordi, Graham Farr
https://creativecommons.org/licenses/by/4.0
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2930Thu, 16 May 2024 00:00:00 +0000The maximum 2-edge-colorable subgraph problem and its fixed-parameter tractability
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2931
<pre>A $k$-edge-coloring of a graph is an assignment of colors $\{1,...,k\}$ to edges of the graph such that adjacent edges receive different colors. <br>In the maximum $k$-edge-colorable subgraph problem we are given a graph and an integer $k$, the goal is to find a $k$-edge-colorable subgraph with maximum number of edges together with its $k$-edge-coloring. <br>In this paper, we consider the maximum 2-edge-colorable subgraph problem and present some results that deal with the fixed-parameter tractability of this problem.</pre>Vahan Mkrtchyan
Copyright (c) 2024 Vahan Mkrtchyan
https://creativecommons.org/licenses/by/4.0
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2931Thu, 16 May 2024 00:00:00 +0000Faster maximal clique enumeration in large real-world link streams
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2932
<pre> </pre> <pre>Link streams offer a good model for representing interactions over time.</pre> <pre>They consist of links $(b,e,u,v)$, where $u$ and $v$ are vertices interacting during the whole time interval $[b,e]$.</pre> <pre>In this paper, we deal with the problem of enumerating maximal cliques in link streams.</pre> <pre>A clique is a pair $(C,[t_0,t_1])$, where $C$ is a set of vertices that all interact pairwise during the full interval $[t_0,t_1]$.</pre> <pre>It is maximal when neither its set of vertices nor its time interval can be increased.</pre> <pre> </pre> <pre>Some main works solving this problem are based on the famous Bron-Kerbosch algorithm for enumerating maximal cliques in graphs.</pre> <pre> </pre> <pre>We take this idea as a starting point to propose a new algorithm which matches the cliques of the instantaneous graphs formed by links existing at a given time $t$ to the maximal cliques of the link stream.</pre> <pre> </pre> <pre>We prove its correctness and compute its complexity, which is better than the state-of-the art ones in many cases of interest.</pre> <pre>We also study the output-sensitive complexity, which is close to the output size, thereby showing that our algorithm is efficient.</pre> <pre>To confirm this, we perform experiments on link streams used in the state of the art, and on massive link streams, up to 100 million links.</pre> <pre> </pre> <pre>In all cases our algorithm is faster, mostly by a factor of at least 10 and up to a factor of $10^4$.</pre> <pre>Moreover, it scales to massive link streams for which the existing algorithms are not able to provide the solution.</pre>Alexis Baudin, Clémence Magnien, Lionel Tabourier
Copyright (c) 2024 Alexis Baudin, Clémence Magnien, Lionel Tabourier
https://creativecommons.org/licenses/by/4.0
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2932Thu, 16 May 2024 00:00:00 +0000Distance-Preserving Graph Compression Techniques
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2933
<pre>We study the problem of distance-preserving graph compression for weighted paths and trees. <br>The problem entails a weighted graph $G = (V, E)$ with non-negative weights and a subset of edges $E^{\prime} \subset E$, which needs to be removed from G (with </pre> <pre>their endpoints merged as a supernode). The goal is to redistribute the weights of the deleted edges in a way that </pre> <pre>minimizes the error. The error is defined as the sum of the absolute differences of the shortest path lengths between different pairs of nodes before and after contracting $E^{\prime}$. </pre> <pre>Based on this error function, we propose optimal approaches for merging any subset of edges in a path and a single edge in a </pre> <pre>tree. Previous works on graph compression techniques aimed at preserving different graph properties (such as the chromatic </pre> <pre>number) or solely focused on identifying the optimal set of edges to contract. However, our focus in this paper is on </pre> <pre>achieving optimal edge contraction (when the contracted edges are provided as input), specifically for weighted trees and paths. </pre> <pre> </pre>Amirali Madani, Anil Maheshwari
Copyright (c) 2024 Amirali Madani, Anil Maheshwari
https://creativecommons.org/licenses/by/4.0
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2933Mon, 20 May 2024 00:00:00 +0000On Dispersability of Some Circulant Graphs
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2941
<pre>The matching book thickness of a graph is the least number of pages in a book embedding such that each page is a matching. <br>A graph is dispersable if its matching book thickness equals its maximum degree. </pre> <pre>Minimum page matching book embeddings are given for bipartite and for most non-bipartite circulants contained in the (Harary) cube of a cycle and for various higher-powers.</pre>Paul C. Kainen, Samuel Joslin, Shannon Overbay
Copyright (c) 2024 Paul C. Kainen, Samuel Joslin, Shannon Overbay
https://creativecommons.org/licenses/by/4.0
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2941Tue, 11 Jun 2024 00:00:00 +0000Computing Optimal Leaf Roots of Chordal Cographs in Linear Time
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2942
<pre>A graph $G$ is a <em>$k$-leaf power</em>, for an integer $k \geq 2$, if there is a tree $T$ with leaf set $V(G)$ such that, for all distinct vertices $x, y \in V(G)$, the edge $xy$ exists in $G$ if and only if the distance between $x$ and $y$ in $T$ is at most $k$.</pre> <pre>Such a tree $T$ is called a <em>$k$-leaf root</em> of $G$.</pre> <pre> </pre> <pre>The computational problem of constructing a $k$-leaf root for a given graph $G$ and an integer $k$, if any, is motivated by the challenge from computational biology to reconstruct phylogenetic trees.</pre> <pre>For fixed $k$, Lafond [SODA 2022] recently solved this problem in polynomial time.</pre> <pre> </pre> <pre>In this paper, we propose to study <em>optimal leaf roots</em> of graphs $G$, that is, the $k$-leaf roots of $G$ with <em>minimum</em> $k$ value.</pre> <pre>Thus, all $k'$-leaf roots of $G$ satisfy $k \leq k'$.</pre> <pre>In terms of computational biology, seeking optimal leaf roots is more justified as they yield more probable phylogenetic trees.</pre> <pre>Lafond’s result does not imply polynomial-time computability of optimal leaf roots, because, even for optimal $k$-leaf roots, $k$ may (exponentially) depend on the size of $G$.</pre> <pre> </pre> <pre>This paper presents a linear-time construction of optimal leaf roots for chordal cographs (also known as trivially perfect graphs).</pre> <pre>Additionally, it highlights the importance of the parity of the parameter $k$ and provides a deeper insight into the differences between optimal $k$-leaf roots of even versus odd $k$.</pre>Van Bang Le, Christian Rosenke
Copyright (c) 2024 Van Bang Le, Christian Rosenke
https://creativecommons.org/licenses/by/4.0
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2942Thu, 20 Jun 2024 00:00:00 +0000On Upward-Planar L-Drawings of Graphs
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2950
<p>In an <em>upward-planar L-drawing</em> of a directed acyclic graph (DAG) each edge $e=(v,w)$ is represented as a polyline composed of a vertical segment with its lowest endpoint at the <em>tail</em> $v$ of $e$ and of a horizontal segment ending at the <em>head</em> $w$ of $e$. Distinct edges may overlap, but must not cross.</p> <p>Recently, upward-planar L-drawings have been studied for $st$-graphs, i.e., planar DAGs with a single source $s$ and a single sink $t$ containing an edge directed from $s$ to $t$.</p> <p>It is known that a<em> plane $st$-graph</em>, i.e., an embedded $st$-graph in which the edge $(s,t)$ is incident to the outer face, admits an upward-planar L-drawing if and only if it admits a bitonic $st$-ordering, which can be tested in linear time. %</p> <p>We study upward-planar L-drawings of DAGs that are not necessarily $st$-graphs.</p> <p>As a combinatorial result, we show that a plane DAG admits an upward-planar L-drawing if and only if it is a subgraph of a plane $st$-graph admitting a bitonic $st$-ordering.</p> <p>This allows us to show that not every tree with a fixed bimodal embedding admits an upward-planar L-drawing. Moreover, we prove that any directed acyclic cactus with a single source (or a single sink) admits an upward-planar L-drawing, which respects a given outerplanar~embedding if there are no transitive edges.</p> <p>On the algorithmic side, we consider DAGs with a single source (or a single sink).</p> <p>We give linear-time testing algorithms for these DAGs in two cases: (a) when the drawing must respect a prescribed embedding and (b) when no restriction is given on the embedding, but the underlying undirected graph is series-parallel.</p> <p>For the single-sink case of (b) it even suffices that each biconnected component is series-parallel.</p>Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo
Copyright (c) 2024 Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo
https://creativecommons.org/licenses/by/4.0
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2950Tue, 09 Jul 2024 00:00:00 +0000Nash Equilibria in Reverse Temporal Voronoi Games
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2951
<p>We study Voronoi games on temporal graphs as introduced by Boehmer et al. (IJCAI '21) where two players each select a vertex in a temporal graph with the goal of reaching the other vertices earlier than the other player. In this work, we consider the <em>reverse</em> temporal Voronoi game, that is, a player wants to maximize the number of vertices reaching her earlier than the other player.</p> <p>Since temporal distances in temporal graphs are not symmetric in general, this yields a different game.</p> <p>We investigate the difference between the two games with respect to the existence of Nash equilibria in various temporal graph classes including temporal trees, cycles, grids, cliques and split graphs. Our extensive results show that the two games indeed behave quite differently depending on the considered temporal graph class.</p>Simeon Pawlowski, Vincent Froese
Copyright (c) 2024 Simeon Pawlowski, Vincent Froese
https://creativecommons.org/licenses/by/4.0
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2951Wed, 10 Jul 2024 00:00:00 +0000Experimental Analysis of Algorithms for the Dynamic Graph Coloring Problem
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2956
<p>This paper focuses on the dynamic graph coloring problem, a dynamic variant based on the well-researched graph coloring problem. This variant of the problem not only considers the number of colors used in the coloring for a graph, but also how many nodes in this graph need to change their color when the graph is changed. The balance between these two measures of quality, as well as running time, creates an inherent trade-off, in which algorithms solving this problem often only focus on one or the other. A variety of such algorithms already exist and are compared, as well as improved upon, in this paper. Each of these algorithms uses different variables to measure its effectiveness, making it difficult to compare their advantages and disadvantages. Finding the right option for a practical application is thus unnecessarily difficult. By implementing the different algorithms and comparing them experimentally, we get a better insight of the strong and weak points of these algorithms. Using this knowledge we propose two new improved variants of these algorithms, obtained by combining aspects of the existing ones. We find that this approach of combining existing algorithms with different strong points often yields superior results and allows for a more versatile trade-off within the algorithm, making it suitable for a broader range of practical applications.</p>Menno Theunis, Marcel Roeloffzen
Copyright (c) 2024 Menno Theunis, Marcel Roeloffzen
https://creativecommons.org/licenses/by/4.0
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2956Thu, 22 Aug 2024 00:00:00 +0000The Complexity of the Fixed Clique Property
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2957
<p>We prove that the following decision problems are co-NP-complete:<br>Determine<br>whether a finite reflexive graph has the fixed clique property.<br>Determine<br>whether a finite simplicial complex has the fixed simplex property.<br>Determine<br>whether a finite truncated lattice has the fixed point property.</p>Bernd Schröder
Copyright (c) 2024 Bernd Schröder
https://creativecommons.org/licenses/by/4.0
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2957Thu, 22 Aug 2024 00:00:00 +0000A Greedy Probabilistic Heuristic for Graph Black-and-White Anticoloring
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2964
<p>Given a graph $G$ and positive integers $b$ and $w$, the <em>Black-and-White Coloring problem</em> asks about the existence of a partial vertex-coloring of $G$, with $b$ vertices colored black and $w$ white, such that there is no edge between a black and a white vertex. The problem is known to be NP-complete.</p> <p>In this paper, we deal with the optimization version, mainly for random graphs. Using the method of conditional expectations, we develop a heuristic with a good performance. We also obtain theoretical results on some of the relevant quantities, and compare the performance of the heuristic with that of several others.</p>Daniel Berend, Shaked Mamana
Copyright (c) 2024 Daniel Berend, Shaked Mamana
https://creativecommons.org/licenses/by/4.0
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2964Sun, 08 Sep 2024 00:00:00 +0000A Linear-Time Optimal Broadcasting Algorithm in Stars of Cliques
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2981
<pre>For the telephone broadcast model, an $O(n\log n)$-time algorithm for </pre> <pre>constructing an optimal broadcasting scheme in a star of cliques with a total </pre> <pre>of $n$ vertices was recently presented by Ambashankar and Harutyunyan at IWOCA</pre> <pre>2024. In the present note we give a considerably shorter and purified </pre> <pre>algorithm description and correctness proof. Moreover, we improve the time </pre> <pre>complexity to $O(n)$.</pre>Peter Damaschke
Copyright (c) 2024 Peter Damaschke
https://creativecommons.org/licenses/by/4.0
https://jgaa-v4.cs.brown.edu/index.php/jgaa/article/view/2981Tue, 08 Oct 2024 00:00:00 +0000