Search

We design succinct encodings of series-parallel, block-cactus and 3-leaf power graphs while supporting the basic navigational queries such as degree, adjacency and neighborhood optimally in the RAM model with logarithmic word size. One salient feature of our representation is that it can achieve optimal space even though the exact space lower bound for these graph classes is not known. For these graph classes, we provide succinct data structures with optimal query support for the first time in the literature. For series-parallel multigraphs, our work also extends the works of Uno et al. (Disc. Math. Alg. and Appl., 2013) and Blelloch and Farzan (CPM, 2010) to produce optimal bounds. [ABSTRACT FROM AUTHOR]

Let G be a simple graph of order n whose adjacency eigenvalues are λ 1 ≥ ⋯ ≥ λ n . The HL-index of G is defined to be R (G) = max { | λ h | , | λ l | } with h = n + 1 2 and l = n + 1 2 . Mohar conjectured that R (G) ≤ 1 for every planar subcubic graph G. In this note, we prove that Mohar's Conjecture holds for every K 4 -minor-free subcubic graph. In addition, R (G) ≤ 1 for every subcubic graph G which contains a subgraph K 2 , 3. [ABSTRACT FROM AUTHOR]

The length of a tree-decomposition of a graph is the maximum distance (in the graph) between two vertices of a same bag of the decomposition. The treelength of a graph is the minimum length among its tree-decompositions. Treelength of graphs has been studied for its algorithmic applications in classical metric problems such as Traveling Salesman Problem or metric dimension of graphs and also, in compact routing in the context of distributed computing. Deciding whether the treelength of a general graph is at most 2 is NP-complete (graphs of treelength one are precisely the chordal graphs), and it is known that the treelength of a graph cannot be approximated up to a factor less than 3 2 (the best known approximation algorithm for treelength has an approximation ratio of 3). However, nothing is known on the computational complexity of treelength in planar graphs, except that the treelength of any outerplanar graph is equal to the third of the size of a largest isometric cycle. This work initiates the study of treelength in planar graphs by considering the next natural subclass of planar graphs, namely the one of series–parallel graphs. We first fully describe the treelength of melon graphs (set of pairwise internally disjoint paths linking two vertices), showing that, even in such a restricted graph class, the expression of the treelength is not trivial. Then, we show that treelength can be approximated up to a factor 3 2 in series–parallel graphs. Our main result is a quadratic-time algorithm for deciding whether a series–parallel graph has treelength at most 2. Our latter result relies on a characterization of series–parallel graphs with treelength 2 in terms of an infinite family of forbidden isometric subgraphs. [ABSTRACT FROM AUTHOR]

A signed graph is a graph G together with a signature σ : E (G) → { 1 , − 1 }. For a real number r ≥ 1 , C r is a circle of circumference r. For two points a , b ∈ C r , the distance d (mod r) (a , b) between a and b is the length of the shorter arc of C r connecting a and b. For x ∈ C r , the antipodal x ̄ of x is the unique point in C r of distance r / 2 from x. A circular r -colouring of (G , σ) is a mapping f : V (G) → C r such that for each positive edge e = u v , d (mod r) (f (u) , f (v)) ≥ 1 , and for each negative edge e = u v , d (mod r) (f (u) , f (v) ¯) ≥ 1. The circular chromatic number of a signed graph (G , σ) is the minimum r such that (G , σ) is circular r –colourable. Let g ∗ (G , σ) be the length of the shortest cycle in (G , σ) with an odd number of positive edges. For a positive integer g , let SP g be the family of signed series–parallel graphs with g ∗ (G , σ) ≥ g. This paper determines, for any positive integer g , the supremum value of χ c (G , σ) of signed graphs in SP g. [ABSTRACT FROM AUTHOR]

A planar orthogonal drawing of a planar 4-graph G (i.e., a planar graph with vertex-degree at most four) is a crossing-free drawing that maps each vertex of G to a distinct point of the plane and each edge of G to a polygonal chain consisting of horizontal and vertical segments. A longstanding open question in Graph Drawing, dating back over 30 years, is whether there exists a linear-time algorithm to compute an orthogonal drawing of a plane 4-graph with the minimum number of bends. The term "plane" indicates that the input graph comes together with a planar embedding, which must be preserved by the drawing (i.e., the drawing must have the same set of faces as the input graph). In this paper we positively answer the question above for the widely-studied class of series–parallel graphs. Our linear-time algorithm is based on a characterization of the planar series–parallel graphs that admit an orthogonal drawing without bends. This characterization is given in terms of the orthogonal spirality that each type of triconnected component of the graph can take; the orthogonal spirality of a component measures how much that component is "rolled-up" in an orthogonal drawing of the graph. [ABSTRACT FROM AUTHOR]

A mixed s -stack q -queue layout of a graph consists of a linear order of its vertices and a partition of its edges into s stacks and q queues, such that no two edges in the same stack cross and no two edges in the same queue nest. In 1992, Heath and Rosenberg conjectured that every planar graph admits a mixed 1-stack 1-queue layout. In 2017, Pupyrev disproved this conjecture by demonstrating a planar partial 3-tree that does not admit a mixed 1-stack 1-queue layout. In this work, we strengthen Pupyrev's result by showing that the conjecture does not hold even for 2-trees, also known as series-parallel graphs. We conclude this by means of a stronger result, stating that the conjecture does not hold, even in the more general union and local settings. In the former, crossings (nestings) are allowed in the stack (queue) as long as the involved edges belong to different connected components of the subgraph induced by its edges, while in the latter several stacks and queues may form the layout, but locally every vertex is incident to edges from only one stack and one queue. [ABSTRACT FROM AUTHOR]

Given its wide spectrum of applications, the classical problem of all‐terminal network reliability evaluation remains a highly relevant problem in network design. The associated optimization problem—to find a network with the best possible reliability under multiple constraints—presents an even more complex challenge, which has been addressed in the scientific literature but usually under strong assumptions over failures probabilities and/or the network topology. In this work, we propose a novel reliability optimization framework for network design with failures probabilities that are independent but not necessarily identical. We leverage the linear‐time evaluation procedure for network reliability in the series‐parallel graphs of Satyanarayana and Wood (1985) to formulate the reliability optimization problem as a mixed‐integer nonlinear optimization problem. To solve this nonconvex problem, we use classical convex envelopes of bilinear functions, introduce custom cutting planes, and propose a new family of convex envelopes for expressions that appear in the evaluation of network reliability. Furthermore, we exploit the refinements produced by spatial branch‐and‐bound to locally strengthen our convex relaxations. Our experiments show that, using our framework, one can efficiently obtain optimal solutions in challenging instances of this problem. [ABSTRACT FROM AUTHOR]

The Critical Node Problem is a well-known optimisation problem that aims to find the subset of nodes in a graph whose removal impacts the graph connectivity as much as possible according to a specific connectivity measure. In this work, we study a new version of the Critical Node Problem, which we call the Connected Critical Node Problem , where the set of the removed nodes has to form a connected subgraph. We consider three connectivity measures and provide complexity results and solution approaches for general graphs and specific classes of graphs such as graphs with bounded treewidth, trees and series-parallel graphs. We consider the Connected Critical Node Problem where the pairwise connectivity (related to the number of pairs of vertices still connected in the graph) is minimised. We prove that this problem is strongly NP-hard and inapproximable on general graphs and is polynomial-time solvable on graphs with bounded treewidth and with unit connection costs. Further, we prove the NP-hardness of the problem with arbitrary connection costs over trees and series-parallel graphs and derive dynamic programming algorithms. We extend our results to the problem variants that consider the minimisation of the largest connected component and the maximisation of the number of connected components (also called K-way Vertex Cut Problem). As side results, we provide new complexity results for the classic Critical Node Problem on series-parallel graphs. [ABSTRACT FROM AUTHOR]

It is well known that the treewidth of a graph G corresponds to the node search number where a team of searchers is pursuing a fugitive that is lazy and invisible (or alternatively is agile and visible) and has the ability to move with infinite speed via unguarded paths. Recently, monotone and connected node search strategies have been considered. A search strategy is monotone if it prevents the fugitive from pervading again areas from where he had been expelled and is connected if, at each step, the set of vertices that is or has been occupied by the searchers induces a connected subgraph of G. It has been shown that the corresponding connected and monotone search number of a graph G can be expressed as the connected treewidth , denoted by ctw (G) , that is defined as the minimum width of a rooted tree-decomposition (X , T , r) , where the union of the bags corresponding to the nodes of a path of T containing the root r is connected in G. In this paper, we initiate the algorithmic study of connected treewidth. We design a O (n 2 ⋅ log n) -time dynamic programming algorithm to compute the connected treewidth of biconnected series–parallel graphs. At the price of an extra n factor in the running time, our algorithm generalizes to graphs of treewidth at most two. [ABSTRACT FROM AUTHOR]

We represent a flow of a graph G = (V , E) as a couple (C , e) with C a circuit of G and e an edge of C , and its incidence vector is the 0 / ± 1 vector χ C ∖ e − χ e . The flow cone of G is the cone generated by the flows of G and the unit vectors. When G has no K 5 -minor, this cone can be described by the system x (M) ≥ 0 for all multicuts M of G. We prove that this system is box-totally dual integral if and only if G is series–parallel. Then, we refine this result to provide the Schrijver system describing the flow cone in series–parallel graphs. This answers a question raised by Chervet et al., (2018). [ABSTRACT FROM AUTHOR]

For a graph $G=(V,E)$, a set $S \subseteq V$ is a $[1,2]$-set if it is a dominating set for $G$ and each vertex $v \in V \setminus S$ is dominated by at most two vertices of $S$, i.e. $1 \leq \vert N(v) \cap S \vert \leq 2$. Moreover a set $S \subseteq V$ is a total $[1,2]$-set if for each vertex of $V$, it is the case that $1 \leq \vert N(v) \cap S \vert \leq 2$. The $[1,2]$-domination number of $G$, denoted $\gamma_{[1,2]}(G)$, is the minimum number of vertices in a $[1,2]$-set. Every $[1,2]$-set with cardinality of $\gamma_{[1,2]}(G)$ is called a $\gamma_{[1,2]}$-set. Total $[1,2]$-domination number and $\gamma_{t[1,2]}$-sets of $G$ are defined in a similar way. This paper presents a linear time algorithm to find a $\gamma_{[1,2]}$-set and a $\gamma_{t[1,2]}$-set in generalized series-parallel graphs.

The length of a tree-decomposition of a graph is the maximum distance between two vertices of a same bag of the decomposition. The treelength of a graph is the minimum length among its tree-decompositions. Treelength of graphs has been studied for its algorithmic applications in classical metric problems such as Traveling Salesman Problem or metric dimension of graphs and also, in compact routing in the context of distributed computing. Deciding whether the treelength of a general graph is at most 2 is NP-complete (graphs of treelength one are precisely the chordal graphs), and it is known that the treelength of a graph cannot be approximated up to a factor less than 3/2 (the best known approximation algorithm for treelength has an approximation ratio of 3). However, nothing is known on the computational complexity of treelength in planar graphs, except that the treelength of any outerplanar graph is equal to the third of the maximum size of its isometric cycles. This work initiates the study of treelength in planar graphs by considering the next natural superclass of outerplanar graphs, namely the one of series-parallel graphs. We first fully describe the treelength of melon graphs (set of pairwise internally disjoint paths linking two vertices), showing that, even in such a restricted graph class, the expression of the treelength is not trivial. Then, we show that treelength can be approximated up to a factor 3/2 in series-parallel graphs. Our main result is a polynomial-time algorithm for deciding whether a series-parallel graph has treelength at most 2. Our latter result relies on a characterization of series-parallel graphs with treelength 2 in terms of infinite families of forbidden isometric subgraphs. [ABSTRACT FROM AUTHOR]

We study the problem DFA-SW of determining if a given deterministic finite automaton A possesses a synchronizing word of length at most k for automata whose (multi-)graphs are TTSPL, i.e., series-parallel, plus allowing some self-loops. While DFA-SW remains NP-complete on TTSPL automata, we also find (further) restrictions with efficient (parameterized) algorithms. We also study the (parameterized) complexity of related problems, for instance, extension variants of the synchronizing word problem, or the problem of finding smallest alphabet-induced synchronizable sub-automata. [ABSTRACT FROM AUTHOR]

Recently, so-called tree-based phylogenetic networks have attracted considerable attention. These networks can be constructed from a phylogenetic tree, called the base tree, by adding additional edges. The primary aim of this study is to provide sufficient criteria for tree-basedness by reducing phylogenetic networks to related graph structures. Even though it is generally known that determining whether a network is tree-based is an NP-complete problem, one of these criteria, namely edge-basedness, can be verified in linear time. Surprisingly, the class of edge-based networks is closely related to a well-known family of graphs, namely, the class of generalized series-parallel graphs, and we explore this relationship in full detail. Additionally, we introduce further classes of tree-based networks and analyze their relationships. [ABSTRACT FROM AUTHOR]

For a graph G=(V,E), a set S⊆V is a [1,2]-set if it is a dominating set for G and each vertex v∈V∖S is dominated by at most two vertices of S, i.e. 1≤|N(v)∩S|≤2. Moreover a set S⊆V is a total [1,2]-set if for each vertex of V, it is the case that 1≤|N(v)∩S|≤2. The [1,2]-domination number of G, denoted γ[1,2](G),is the minimum number of vertices in a [1,2]-set. Every [1,2]-set with cardinality of γ[1,2](G) is called a γ[1,2]-set. Total [1,2]-domination number and γt[1,2]-sets of G are defined in a similar way. This paper presents a linear time algorithm to find a γ[1,2]-set and a γt[1,2]-set in generalized series-parallel graphs. [ABSTRACT FROM AUTHOR]

Potential‐based flows are an extension of classical network flows in which the flow on an arc is determined by the difference of the potentials of its incident nodes. Such flows are unique and arise, for example, in energy networks. Two important algorithmic problems are to determine whether there exists a feasible flow and to maximize the flow between two designated nodes. We show that these problems can be solved for the single source and sink case by reducing the network to a single arc. However, if we additionally consider switches that allow to force the flow to 0 and decouple the potentials, these problems are NP‐hard. Nevertheless, for particular series‐parallel networks, one can use algorithms for the subset sum problem. Moreover, applying network presolving based on generalized series‐parallel structures allows to significantly reduce the size of realistic energy networks. [ABSTRACT FROM AUTHOR]

We study the class L of link types that admit a K 4 -minor-free diagram, i.e., they can be projected on the plane so that the resulting graph does not contain any subdivision of K 4 . We prove that L is the closure of a subclass of torus links under the operation of connected sum. Using this structural result, we enumerate L and subclasses of it, with respect to the minimal number of crossings or edges in a projection of L ∈ L . Further, we enumerate (both exactly and asymptotically) all connected K 4 -minor-free link diagrams, all minimal connected K 4 -minor-free link diagrams, and all K 4 -minor-free diagrams of the unknot. [ABSTRACT FROM AUTHOR]

The multi‐budgeted matching problem (mBM) is a weighted matching problem with k independent edge cost functions. For each cost function, a budget constraint requires the accumulated cost not to exceed a corresponding budget. We show that the mBM is strongly NP‐hard on paths with uniform edge weights and budgets by a reduction from 3‐SAT. Subsequently, we propose a dynamic program for series‐parallel graphs with pseudo‐polynomial run time for a fixed number of budget constraints. As an extension we show how this algorithm can be used to solve the mBM on trees using a graph transformation. Realizing that both these graph classes have a bounded treewidth in common, we introduce a dynamic program based on tree decompositions. This approach leads to a pseudo‐polynomial algorithm for the mBM with fixed k on graphs of bounded treewidth. [ABSTRACT FROM AUTHOR]

We consider a variant of the well-known, NP-complete problem of minimum cut linear arrangement for directed acyclic graphs. In this variant, we are given a directed acyclic graph and we are asked to find a topological ordering such that the maximum number of cut edges at any point in this ordering is minimum. In our variant, the vertices and edges have weights, and the aim is to minimize the maximum weight of cut edges in addition to the weight of the last vertex before the cut. There is a known, polynomial time algorithm (Liu, 1987 [17] ) for the cases where the input graph is a rooted tree. We focus on the instances where the input graph is a directed series-parallel graph, and propose a polynomial time algorithm, thus expanding the class of graphs for which a polynomial time algorithm is known. Directed acyclic graphs are used to model scientific applications where the vertices correspond to the tasks of a given application and the edges represent the dependencies between the tasks. In such models, the problem we address reads as minimizing the peak memory requirement in an execution of the application. Our work, combined with Liu's work on rooted trees addresses this practical problem in two important classes of applications. [ABSTRACT FROM AUTHOR]

In classical network reliability, the system under study is a network with perfect nodes and imperfect links that fail randomly and independently. The probability that a given subset [ABSTRACT FROM AUTHOR]

Let H be a fixed graph and [ABSTRACT FROM AUTHOR]

The budgeted minimum cost flow problem (BMCF( K)) with unit upgrading costs extends the classical minimum cost flow problem by allowing one to reduce the cost of at most K arcs. In this article, we consider complexity and algorithms for the special case of an uncapacitated network with just one source. By a reduction from 3-SAT we prove strong [ABSTRACT FROM AUTHOR]

We consider network design games with weighted players and uniform edge capacities and study their Nash equilibria. In these games, each player has to choose a path from her source to her sink through a network subject to the constraint that the total weight of all players using an edge within their chosen path does not exceed the capacity of the edge. The fixed cost of each edge that is used by some player is shared among the players using the edge by charging each player a fraction of the edge's cost equal to the ratio of her weight to the total weight of all players using the edge. We show that there exist instances of capacitated network design games with weighted players and uniform capacities that do not admit a Nash equilibrium even in the case that all players share the same source and sink. Moreover, we show that it is strongly [ABSTRACT FROM AUTHOR]

Graph Theory