Search

In this paper, we investigate the computational complexity of subgraph reconfiguration problems in directed graphs. More specifically, we focus on the problem of reconfiguring arborescences in a digraph, where an arborescence is a directed graph such that its underlying undirected graph forms a tree and all vertices have in-degree at most 1. Given two arborescences in a digraph, the goal of the problem is to determine whether there is a (reconfiguration) sequence of arborescences between the given arborescences such that each arborescence in the sequence can be obtained from the previous one by removing an arc and then adding another arc. We show that this problem can be solved in polynomial time, whereas the problem is PSPACE-complete when we restrict arborescences in a reconfiguration sequence to directed paths or relax to directed acyclic graphs. We also show that there is a polynomial-time algorithm for finding a shortest reconfiguration sequence between two spanning arborescences. [ABSTRACT FROM AUTHOR]

Stackelberg pricing games are pricing problems over a set of items. One player, the leader , sets prices for the items and the second player, the follower , buys a subset of items at minimal total cost subject to feasibility constraints. The constraints are determined by an optimization problem. For example, the Stackelberg shortest path game is used to optimize the income from road tolls (cf. [21]). The items are edges in a network graph and the follower buys a subset of edges forming a path. The Stackelberg pricing games studied in the literature are formulated on top of covering problems. In this paper, we introduce pricing games based on packing problems. We are interested in the complexity of computing leader-optimal prices depending on different types of follower-constraints. We show that optimal prices can be computed in polynomial time if the follower-constraints are determined by the well-known interval scheduling problem. This problem is equivalent to the independent set problem on interval graphs. In case the follower-constraints are based on the independent set problem on perfect graphs or on the bipartite matching problem, we prove APX-hardness for the pricing problem. On a more general note, we prove Σ 2 p -completeness if the follower-constraints are given by a packing problem that is NP-complete, i.e., the leader's pricing problem is hard even if she has an NP-oracle at hand. [ABSTRACT FROM AUTHOR]

A subset M ⊆ E of edges of a graph G = (V , E) is called a m a t c h i n g if no two edges of M share a common vertex. Given a matching M in G , a vertex v ∈ V is called M -saturated if there exists an edge e ∈ M incident with v. A matching M of a graph G is called an acyclic matching if, G [ V (M) ] , the subgraph of G induced by the M -saturated vertices of G is an acyclic graph. Given a graph G , the Acyclic Matching problem asks to find an acyclic matching of maximum cardinality in G. The Decide-Acyclic Matching problem takes a graph G and an integer k and asks whether G has an acyclic matching of cardinality at least k. The Decide-Acyclic Matching problem is known to be NP -complete for general graphs as well as for bipartite graphs. In this paper, we strengthen this result by showing that the Decide-Acyclic Matching problem remains NP -complete for comb-convex bipartite graphs, star-convex bipartite graphs, and dually chordal graphs. On the positive side, we show that the Acyclic Matching problem is linear time solvable for split graphs, block graphs, and proper interval graphs. We show that the Acyclic Matching problem is hard to approximate within a factor of n 1 − ϵ for any ϵ > 0 unless P = NP. Also, we show that the Acyclic Matching problem is APX -complete for (2 k + 1) -regular graphs for every fixed integer k ≥ 3. [ABSTRACT FROM AUTHOR]

Thorup and Zwick [1] introduced the notion of approximate distance oracles, a data structure that produces for an n -vertex, m -edge weighted undirected graph G = (V , E) , distance estimations in constant query time. They presented a distance oracle of size O (k n 1 + 1 / k) that given a pair of vertices u , v ∈ V at distance d (u , v) produces in O (k) time an estimation that is bounded by (2 k − 1) d (u , v) , i.e., a (2 k − 1) -multiplicative approximation (stretch). Thorup and Zwick [1] presented also a lower bound based on the girth conjecture of Erdős. For sparse unweighted graphs (i.e., m = O ˜ (n)) the lower bound does not apply. Pǎtraşcu and Roditty [2] used the sparsity of the graph and obtained a distance oracle that uses O ˜ (n 5 / 3) space, has O (1) query time and a stretch of 2. Pǎtraşcu et al. [3] presented infinitely many distance oracles with fractional stretch factors that for graphs with m = O ˜ (n) converge exactly to the integral stretch factors and the corresponding space bound of Thorup and Zwick. It is not known, however, whether graph sparsity can help to get a stretch which is better than (2 k − 1) using only O ˜ (k n 1 + 1 / k) space. In this paper we answer this open question and prove a separation between sparse and dense graphs by showing that using sparsity it is possible to obtain better stretch/space tradeoffs than those of Thorup and Zwick. We show that for every k ≥ 2 there is a distance oracle of size O ˜ (k m 1 + 1 / k) that produces in O (k) time an estimation d ⁎ (u , v) that satisfies d (u , v) ≤ d ⁎ (u , v) ≤ (2 k − 1) d (u , v) − 4 , for k > 2 , and d (u , v) ≤ d ⁎ (u , v) ≤ 3 d (u , v) − 2 , for k = 2. Another contribution of this paper is a refined stretch analysis of Thorup and Zwick distance oracles that allows us to obtain a better understanding of this important data structure. We present simple conditions for every w ∈ V that characterize the exact scenarios in which every query that involves w produces an estimation of stretch strictly better than 2 k − 1 , even in the case of dense graphs. We complement this contribution with an experiment on real world graphs. The main finding in the experiment is that different real world graphs are likely to satisfy the required conditions and hence the stretch of Thorup and Zwick distance oracles is much better than its worst case bound in these real world graphs. • Graph sparsity can help to get space-stretch tradeoffs for Distance Oracle which are strictly better than Thorup and Zwick space-stretch tradeoffs for general undirected graphs. • A refined stretch analysis of Thorup and Zwick Distance Oracle that characterizes several cases in which the stretch is strictly better than 2 k − 1. • An experiment on real world graphs shows that the cases characterized in the refined stretch analysis are quite frequent, and thus, in many real world graphs, the actual stretch is much better than the worst case stretch bound. [ABSTRACT FROM AUTHOR]

We study the problem of deciding reconfigurability of target sets of a graph. Given a graph G with vertex thresholds τ , consider a dynamic process in which vertex v becomes activated once at least τ (v) of its neighbors are activated. A vertex set S is called a target set if all vertices of G would be activated when initially activating vertices of S. In the Target Set Reconfiguration problem, given two target sets X and Y of the same size, we are required to determine whether X can be transformed into Y by repeatedly swapping one vertex in the current set with another vertex not in the current set preserving every intermediate set as a target set. In this paper, we investigate the complexity of Target Set Reconfiguration in restricted cases. On the hardness side, we prove that Target Set Reconfiguration is PSPACE -complete on bipartite planar graphs of degree 3 and 4 and of threshold 2, bipartite 3-regular graphs and planar 3-regular graphs of threshold 1 and 2, and split graphs, which is in contrast to the fact that a special case called Vertex Cover Reconfiguration is in P for the last graph class. On the positive side, we present a polynomial-time algorithm for Target Set Reconfiguration on graphs of maximum degree 2 and trees. The latter result can be thought of as a generalization of that for Vertex Cover Reconfiguration. [ABSTRACT FROM AUTHOR]

We study the k -Canadian Traveller Problem, where the objective is to lead a traveller in an undirected weighted graph G from a source s to a target t , knowing that at most k edges of the graph are blocked and cannot be traversed. The locations of blockages are unknown at the beginning of the walk but a blocked edge is revealed when the traveller visits one of its endpoints. There exist graphs for which the competitive ratio of any deterministic strategies cannot be smaller than 2 k + 1. Conversely, there exists a very simple strategy, reposition , which achieves this ratio 2 k + 1. It consists in successively traversing shortest (s , t) -paths and coming back to s when the traveller is blocked. We refine this analysis by detecting families of graphs for which a smaller competitive ratio can be obtained. This paper produces a global analysis to understand the impact of the size of the maximum (s , t) -cuts of G on the competitiveness of deterministic strategies. We design deterministic strategies achieving a ratio ρ k + O (λ) , with ρ < 2 , for two different cut parameters λ. In particular, we propose a strategy called detour with a competitive ratio 2 k + O (μ max E) , where μ max E is the size of the maximum edge (s , t) -cut. Another contribution is a strategy called bypass with a competitive ratio 2 3 4 k + O (λ max V) , where λ max V is the size of the maximum vertex (s , t) -cut of all subgraphs of G. This produces an efficient algorithm for outerplanar graphs, which verify λ max V ≤ 2. • Competitive analysis of deterministic strategies for the Canadian Traveller Problem. • Study of families of graphs with small maximum (s,t)-cuts. • Design of two strategies outperforming the current ratios over these families. • Improvement of the original lower bound of competitiveness for outerplanar graphs. [ABSTRACT FROM AUTHOR]

For an integer r ≥ 0 the r-th iterated line graph L r (G) of a graph G is defined by: (i) L 0 (G) = G and (ii) L r (G) = L (L (r − 1) (G)) for r > 0 , where L (G) denotes the line graph of G. The Hamiltonian Index h (G) of G is the smallest r such that L r (G) has a Hamiltonian cycle [Chartrand, 1968]. Checking if h (G) = k is NP -hard for any fixed integer k ≥ 0 even for subcubic graphs G [Ryjáček et al., 2011]. We study the parameterized complexity of this problem with the parameter treewidth, t w (G) , and show that we can find h (G) in time1 O ⋆ ((1 + 2 (ω + 3)) t w (G)) where ω is the matrix multiplication exponent. Prior work on computing h (G) includes various O ⋆ (2 O (t w (G))) -time algorithms for checking if h (G) = 0 holds; i.e., whether G has a Hamiltonian Cycle [Cygan et al., FOCS 2011; Bodlaender et al., Inform. Comput., 2015; Fomin et al., JACM 2016]; an O ⋆ (t w (G) O (t w (G))) -time algorithm for checking if h (G) = 1 holds; i.e., whether L (G) has a Hamiltonian Cycle [Lampis et al., Discrete Appl. Math., 2017]; and, most recently, an O ⋆ ((1 + 2 (ω + 3)) t w (G)) -time algorithm for checking if h (G) = 1 holds [Misra et al., CSR 2019]. Our algorithm for computing h (G) generalizes these results. The NP -hard Eulerian Steiner Subgraph problem takes as input a graph G and a specified subset K of terminal vertices of G and asks if G has an Eulerian2 subgraph H containing all the terminals. A key ingredient of our algorithm for finding h (G) is an algorithm which solves Eulerian Steiner Subgraph in O ⋆ ((1 + 2 (ω + 3)) t w (G)) time. To the best of our knowledge this is the first FPT algorithm for Eulerian Steiner Subgraph. Prior work on the special case of finding a spanning Eulerian subgraph (i.e., with K = V (G)) includes a polynomial-time algorithm for series-parallel graphs [Richey et al., 1985] and an O ⋆ (2 O (n)) -time algorithm for planar graphs on n vertices [Sau and Thilikos, 2010]. Our algorithm for Eulerian Steiner Subgraph generalizes both these results. [ABSTRACT FROM AUTHOR]

In the l -Path Vertex Cover problem (resp., the l -Component Order Connectivity problem) the input is an undirected graph G and an integer k. The goal is to decide whether there is a set of vertices of size at most k whose deletion from G results in a graph that does not contain a path with l vertices (resp., does not contain a connected component with at least l vertices). In this paper we give a parameterized algorithm for l -Path Vertex Cover when l = 5 , 6 , 7 , whose running times are O ⁎ (3.945 k) , O ⁎ (4.947 k) , and O ⁎ (5.951 k) , respectively. We also give an algorithm for l -Component Order Connectivity whose running time is O ⁎ ((l − 1 − ϵ l) k) for every l ≥ 4 , where ϵ l > 0 for every l. [ABSTRACT FROM AUTHOR]

In a graph G = (V , E) with an edge coloring ℓ : E → C and two distinguished vertices s and t , a colored (s , t) -cut is a set C ˜ ⊆ C such that deleting all edges with some color c ∈ C ˜ from G disconnects s and t. Motivated by applications in the design of robust networks, we introduce colored cut games. In these games, an attacker and a defender choose colors to delete and to protect, respectively, in an alternating fashion. The attacker wants to achieve a colored (s , t) -cut and the defender wants to prevent this. First, we show that for an unbounded number of alternations, colored cut games are PSPACE-complete even on subcubic graphs. We then show that, even on subcubic graphs, colored cut games with i alternations are complete for classes in the polynomial hierarchy whose level depends on i. To complete the dichotomy, we show that all colored cut games are polynomial-time solvable on graphs with maximum degree at most 2. Next, we show that all colored cut games admit a polynomial kernel for the parameter k + κ r where k denotes the total attacker budget and, for any constant r , κ r is the number of vertex deletions that are necessary to transform G into a graph where the longest path has length at most r. For κ 1 , which is the vertex cover number vc of the input graph, the kernel has size O (vc 2 k 2). Moreover, we introduce an algorithm solving the most basic colored cut game, Colored (s , t) - Cut , in 2 vc + k n O (1) time. [ABSTRACT FROM AUTHOR]

A vertex coloring of a graph G = (V , E) is called an exact square coloring of G if any two vertices at distance exactly 2 receive different colors. The minimum number of colors required by an exact square coloring is called the exact square chromatic number of G and is denoted by χ [ # 2 ] (G). Given a graph G and a positive integer k , the Exact Square Coloring Problem is to decide whether G admits an exact square coloring using k colors. It is known that Exact Square Coloring Problem is NP-complete for chordal graphs. In this paper, we strengthen this result by proving that this problem remains NP-complete for undirected path graphs, which is a proper subclass of chordal graphs. However, we give linear time algorithms for computing the exact square chromatic number of proper interval graphs and threshold graphs, which are proper subclasses of chordal graphs. Moreover, for a proper interval graph G , we show that χ [ # 2 ] (G) ≤ 3. We also propose a polynomial time algorithm to produce an exact square coloring of a block graph G using at most χ [ # 2 ] (G) + 1 colors. Next, we study a lower bound of χ [ # 2 ] (G). A subset S of vertices of a graph G = (V , E) is called an exact square clique of G if the distance between any two vertices in S is exactly 2. The cardinality of the maximum exact square clique of G is called the exact square clique number of G and is denoted by ω [ # 2 ] (G). Clearly, ω [ # 2 ] (G) ≤ χ [ # 2 ] (G). Given a graph G and a positive integer k , the problem of deciding whether ω [ # 2 ] (G) is at least k , is known to be NP-complete for bipartite graphs and chordal graphs. In this paper, we strengthen these results by proving that this problem remains NP-complete for undirected path graphs, perfect elimination bipartite graphs, star-convex bipartite graphs and comb-convex bipartite graphs. We also compute the exact value of ω [ # 2 ] (G) for proper interval graphs, threshold graphs, block graphs and convex bipartite graphs. [ABSTRACT FROM AUTHOR]

In a graph, a perfect matching cut is an edge cut that is a perfect matching. perfect matching cut (pmc) is the problem of deciding whether a given graph has a perfect matching cut, and is known to be NP -complete. We revisit the problem and show that pmc remains NP -complete when restricted to bipartite graphs of maximum degree 3 and arbitrarily large girth. Complementing this hardness result, we give two graph classes in which pmc is polynomial-time solvable. The first one includes claw-free graphs and graphs without an induced path on five vertices, the second one properly contains all chordal graphs. Assuming the Exponential Time Hypothesis, we show there is no O ⁎ (2 o (n)) -time algorithm for pmc even when restricted to n -vertex bipartite graphs, and also show that pmc can be solved in O ⁎ (1.2721 n) time by means of an exact branching algorithm. [ABSTRACT FROM AUTHOR]

Hub labeling schemes are popular methods for computing distances on road networks and other large complex networks, often answering to a query within a few microseconds for graphs with millions of edges. In this work, we study their algorithmic applications beyond distance queries. Indeed, several implementations of hub labels were reported to have good practical performances, both in terms of pre-processing time and maximum label size. There are also a few relevant graph classes for applications for which we know how to compute hub labelings with sublinear labels in quasi linear time. These positive results raise the question of what can be computed efficiently given a graph and a hub labeling of small maximum label size as input. We focus on eccentricity queries and distance-sum queries , for several versions of these problems on directed weighted graphs, that is in part motivated by their importance in facility location problems. On the negative side, we show conditional lower bounds for these above problems on unweighted undirected sparse graphs, via standard constructions from "Fine-grained" complexity. Specifically, under the Strong Exponential-Time Hypothesis (SETH), answering to these above queries requires Ω (| V | 2 − o (1)) pre-processing time or Ω (| V | 1 − o (1)) query time, even if we are given as input a hub labeling of maximum label size in ω (log ⁡ | V |). However, things take a different turn when the hub labels have a sublogarithmic size. Indeed, for every ε > 0 there exists a δ ε > 0 such that the following hold, being given a hub labeling of maximum label size ≤ k : after pre-processing the labels in total O (2 δ ε ⋅ k ⋅ | V | 1 + ε) time, we can compute both the eccentricity and the distance-sum of any vertex in O (2 δ ε ⋅ k ⋅ | V | ε) time. Our data structure is a novel application of the orthogonal range query framework of Cabello and Knauer (2009) [17]. It can also be applied to the fast global computation of some topological indices. Finally, as a by-product of our approach, on any fixed class of unweighted graphs with bounded expansion , we can decide whether the diameter of an n -vertex graph in the class is at most k in f ε (k) ⋅ n 1 + ε time for any ε > 0 , for some "explicit" function f ε that depends on ε and the graph class considered. This result is further motivated by the empirical evidence that many classes of complex networks have bounded expansion (Demaine et al., 2019 [24]), and that some of these networks, such as the online social networks, have a relatively small diameter. [ABSTRACT FROM AUTHOR]

Motivated by the design of cost-efficient communication networks, the problem about Maximum Internal Spanning Tree that arises in a connected graph, is proposed to find a spanning tree with the maximum number of internal vertices. In 2018, Xingfu Li et al. presented a polynomial algorithm to find a maximum internal spanning tree in a connected interval graph. Based on the structure of normal orderings on interval graphs, we present a simple linear time algorithm that solve the problem when restricted to connected interval graphs in this paper. The proof provides additional insight about the linear time algorithm on interval graphs. • The MIST problem is solvable in a simple linear time algorithm under the restriction of connected interval graphs. • The structure of normal orderings on interval graphs is proposed to solve the Maximum Internal Spanning Tree problem. • The proof of the main results is more easy to understand with proper cases to prove. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) , a subset D of vertex set V , is a dominating set of G if every vertex not in D is adjacent to at least one vertex of D. A dominating set D of a graph G with no isolated vertices is called a paired dominating set (PD-set) , if the subgraph induced by D in G has a perfect matching. The Min-PD problem requires to compute a PD-set of minimum cardinality. The decision version of the Min-PD problem is NP-complete even when G belongs to restricted graph classes such as bipartite graphs, chordal graphs etc. On the other side, the problem is efficiently solvable for many graph classes including interval graphs, strongly chordal graphs, permutation graphs etc. In this paper, we study the complexity of the problem in AT-free graphs and planar graphs. The class of AT-free graphs contains cocomparability graphs, permutation graphs, trapezoid graphs, and interval graphs as subclasses. We propose a polynomial-time algorithm to compute a minimum PD-set in AT-free graphs. In addition, we also present a linear-time 2-approximation algorithm for the problem in AT-free graphs. Further, we prove that the decision version of the problem is NP-complete for planar graphs, which answers an open question asked by Lin et al. (2015) [19] and (2020) [20]. Alvarado et al. (2015) [1] conjectured that given a graph G = (V , E) , it is NP-hard to decide whether γ (G) = γ p r (G). In this paper we settle this conjecture affirmatively. [ABSTRACT FROM AUTHOR]

An injective k -coloring of a graph G = (V , E) is a function f : V → { 1 , 2 , ... , k } such that for every pair of vertices u and v having a common neighbor, f (u) ≠ f (v). The injective chromatic number χ i (G) of a graph G is the minimum k for which G admits an injective k -coloring. Given a graph G and a positive integer k , Decide Injective Coloring Problem is to decide whether G admits an injective k-coloring. Decide Injective Coloring Problem is known to be NP-complete for chordal graphs. In this paper, we strengthen this result by proving that Decide Injective coloring Problem remains NP-complete for undirected path graphs, a proper subclass of chordal graphs. Moreover, we show that it is not possible to approximate the injective chromatic number of an undirected path graph within a factor of n 1 / 3 − ε in polynomial time for every ε > 0 unless ZPP = NP. On the positive side, we prove that the injective chromatic number of an interval graph is either Δ (G) or Δ (G) + 1 , where Δ (G) is the maximum degree of G. We also characterize the interval graphs having χ i (G) = Δ (G) and χ i (G) = Δ (G) + 1. As a consequence of this characterization, we obtain a linear time algorithm to find the injective chromatic number of an interval graph. [ABSTRACT FROM AUTHOR]

K-best enumeration , which asks to output k -best solutions without duplication, is a helpful tool in data analysis for many fields. In such fields, graphs typically represent data. Thus subgraph enumeration has been paid much attention to such fields. However, k -best enumeration tends to be intractable since, in many cases, finding one optimum solution is NP-hard. To overcome this difficulty, we combine k -best enumeration with a concept of enumeration algorithms called approximation enumeration algorithms. As a main result, we propose a 4-approximation algorithm for minimal connected edge dominating sets which outputs k minimal solutions with cardinality at most 4 ⋅ OPT ‾ , where OPT ‾ is the cardinality of a minimum solution which is not outputted by the algorithm. Our proposed algorithm runs in O (n m 2 Δ) delay, where n , m , Δ are the number of vertices, the number of edges, and the maximum degree of an input graph. [ABSTRACT FROM AUTHOR]

Damian and Pemmaraju (2002) [8] introduced leaf sector covers for circle graphs and presented an O (n 2) -time algorithm to find this data structure. They subsequently employed it as an algorithmic tool, leading to the development of an 8-approximation algorithm for the dominating set problem, a (2 + ε) -approximation scheme for the dominating set problem, and a (3 + ε) -approximation scheme for the total dominating set problem. In this paper, we have improved the time complexity from O (n 2) to O (n + m) for finding a leaf sector cover. Furthermore, we employed leaf sector covers as a powerful algorithmic tool to design a 10-approximation algorithm for the total dominating set problem and a 12-approximation algorithm for the paired-dominating set problem. Moreover, we also proposed a (2 + ε) -approximation scheme for the total dominating set problem and a (4 + ε) -approximation scheme for the paired-dominating set problem. The results presented above are currently the best algorithms for circle graphs. [ABSTRACT FROM AUTHOR]

Intersection graphs are well-studied in the area of graph algorithms. Some intersection graph classes are known to have algorithms enumerating all unlabeled graphs by reverse search. Since these algorithms output graphs one by one and the numbers of graphs in these classes are vast, they work only for a small number of vertices. Binary decision diagrams (BDDs) are compact data structures for various types of data and useful for solving optimization and enumeration problems. This study proposes enumeration algorithms for five intersection graph classes, which admit O (n) -bit string representations for their member graphs. Our algorithm for each class enumerates all unlabeled graphs with n vertices over BDDs representing the binary strings in time polynomial in n. Moreover, our algorithms are extended so that it enumerates those with constraints on the maximum (bi)clique size and/or the number of edges. [ABSTRACT FROM AUTHOR]

Given a weighted graph G = (V , E) with weight functions c : E → R + and π : V → R + , and a subset U ⊆ V , the normalized cut value for U is defined as the sum of the weights of edges exiting U divided by the weight of vertices in U. The mean isoperimetry problem , ISO 1 (G , k) , for a weighted graph G is a generalization of the classical uniform sparsest cut problem in which, given a parameter k , the objective is to find k disjoint nonempty subsets of V minimizing the average normalized cut value of the parts. The robust version of the problem seeks an optimizer where the number of vertices that fall out of the subpartition is bounded by some given integer 0 ≤ ρ ≤ | V |. The problem may also be considered as the normalized version of the classical k -multiway cut problem on edge-weighted graphs. Our main result states that ISO 1 (G , k) , as well as its robust version, CRISO 1 (G , k , ρ) , subjected to the condition that each part of the subpartition induces a connected subgraph, are solvable in time O (k 2 ρ 2 π (V (T)) 3) on any weighted tree T , in which π (V (T)) is the sum of the vertex-weights. This result implies that ISO 1 (G , k) is strongly polynomial-time solvable on weighted trees when the vertex-weights are polynomially bounded and may be compared to the fact that the problem is NP-hard for weighted trees in general. As far as applications are concerned, the connectivity requirement may be interpreted as an approach to model the practical consistency of the parts, which together with having control on the size of the outlier set and applying a smooth "mean" cost function (as opposed to, say, the "max" version), characterizes our solution to CRISO 1 (G , k , ρ) on trees as one of the most flexible and accurate procedures within the framework of isoperimetry-based clustering. Also, using this, we show that both mentioned problems, ISO 1 (G , k) and CRISO 1 (G , k , ρ) as well as the ordinary robust mean isoperimetry problem RISO 1 (G , k , ρ) , admit polynomial-time O (log 1.5 ⁡ | V | log ⁡ log ⁡ | V |) -approximation algorithms for weighted graphs with polynomially bounded weights, using the Räcke-Shah tree cut sparsifier. [ABSTRACT FROM AUTHOR]

We study here algorithmic aspects of modular decomposition of hypergraphs. In the literature one can find three different definitions of modules: standard modules [25] , k -subset modules [6] , and Courcelle's modules [12]. Using fundamental tools from combinatorial decompositions such as partitive and orthogonal families, we directly derive a linear time algorithm for Courcelle's decomposition. We then introduce a general algorithmic tool for weakly partitive families and apply it for the three definitions of modules to derive polynomial time algorithms. For standard modules, we give an O (n 3 ⋅ l) time algorithm (where n is the number of vertices and l the sum of the size of the edges). For k -subset modules, we obtain an O (n 3 ⋅ l) runtime. This is an improvement from the best known algorithm for k -subset modular decomposition, which was not polynomial w.r.t. n and m , and is in O (n 3 k − 5) time [6] where k denotes the maximal size of an edge, and m the number of hyperedges. Finally we focus on applications of orthogonality to modular decompositions of tournaments, simplifying the algorithm from [24]. The question of designing a O (n ⋅ l) time algorithm for the standard modular decomposition of hypergraphs remains open. [ABSTRACT FROM AUTHOR]

We give deterministic distributed (1 + ϵ) -approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in O (1 ϵ log ⁡ n) rounds, and our independent set algorithm has a runtime of O (1 ϵ log ⁡ (1 ϵ) log ⁎ ⁡ n) rounds. For coloring, existing lower bounds imply that the dependencies on 1 ϵ and log ⁡ n are best possible. For independent set, we prove that Ω (1 ϵ) rounds are necessary. Both our algorithms make use of a tree decomposition of the input chordal graph. They iteratively peel off interval subgraphs, which are identified via the tree decomposition of the input graph, thereby partitioning the vertex set into O (log ⁡ n) layers. For coloring, each interval graph is colored independently, which results in various coloring conflicts between the layers. These conflicts are then resolved in a separate phase, using the particular structure of our partitioning. For independent set, only the first O (log ⁡ 1 ϵ) layers are required as they already contain a large enough independent set. We develop a (1 + ϵ) -approximation maximum independent set algorithm for interval graphs, which we then apply to those layers. While tree decompositions have only played a minor role in distributed computing, our work demonstrates their potential for designing efficient distributed algorithms. [ABSTRACT FROM AUTHOR]

For a pair of positive parameters D , χ , a partition P of the vertex set V of an n -vertex graph G = (V , E) into disjoint clusters of diameter at most D each is called a (D , χ) network decomposition , if the supergraph G (P) , obtained by contracting each of the clusters of P , can be properly χ -colored. The decomposition P is said to be strong (resp., weak) if each of the clusters has strong (resp., weak) diameter at most D , i.e., if for every cluster C ∈ P and every two vertices u , v ∈ C , the distance between them in the induced graph G (C) of C (resp., in G) is at most D. Network decomposition is a powerful construct, very useful in distributed computing and beyond. In this paper we show that strong (O (log ⁡ n) , O (log ⁡ n)) network decompositions can be computed in O (log 2 ⁡ n) time in the CONGEST model. We also present a tradeoff between parameters of our network decomposition. Our work is inspired by and relies on the "shifted shortest path approach", due to Blelloch et al. [11] , and Miller et al. [20]. These authors developed this approach for PRAM algorithms for padded partitions. We adapt their approach to network decompositions in the distributed model of computation. [ABSTRACT FROM AUTHOR]

Consider the following natural variation of the degree realization problem. Let G = (V , E) be a simple undirected graph of order n. Let f ∈ R ≥ 0 n be a vector of vertex requirements , and let w ∈ R ≥ 0 n be a vector of provided services at the vertices. Then w satisfies f on G if the constraints ∑ j ∈ N (i) w j = f i are satisfied for all i ∈ V , where N (i) denotes the neighbourhood of vector i. Given a requirements vector f , the Vertex-Weighted Graph Realization problem asks for a suitable graph G and a vector w of provided services that satisfy f on G. In this paper, we consider two avenues. We initiate a study that focuses on weighted realizations where the graph is required to be of a specific class by providing a full characterization of realizable requirement vectors for paths and acyclic graphs. However, checking the respective criteria is shown to be NP-hard. In the second part, we advance the study in general graphs which was started in [2]. For the unsolved cases, the question of whether a vector f is realizable can be formulated as whether its largest requirement lies within certain intervals. We describe several new, realizable intervals and show the existence of an interval that cannot be realized. The complete classification for general graphs is an open problem. [ABSTRACT FROM AUTHOR]

In the Pathwidth One Vertex Deletion (POVD) problem the input is a graph G and an integer k , and the goal is to decide whether there is a set of at most k vertices whose removal from G results in a graph with pathwidth at most 1. In this paper we give an algorithm for POVD whose running time is O ⁎ (3.888 k). [ABSTRACT FROM AUTHOR]

• A divide-and-conquer strategy on reconstruction of graphs without long holes. • The betweenness oracle is as powerful as the distance oracle on chordal graphs. • New reconstruction algorithms for new graphs, using betweenness queries. We study the query complexity of reconstructing { C ≥ 5 } -free graphs with respect to the betweenness oracle. In particular, we show that hidden { C ≥ 5 } -free graphs can be reconstructed by using O (Δ 14 ⋅ log 2 ⁡ n + Δ 9 ⋅ n log 2 ⁡ n) betweenness queries in expectation, where Δ denotes the maximum degree of the given graph and n denotes the number of vertices. In addition, we propose two improved randomized algorithms for two subclasses of { C ≥ 5 } -free graphs, namely the distance-hereditary graphs and the chordal graphs. For the former class, our algorithm uses O (Δ 10 ⋅ log 2 ⁡ n + Δ 5 ⋅ n log 2 ⁡ n) betweenness queries in expectation, and for the latter class, our algorithm uses O (Δ 2 ⋅ n log 2 ⁡ n) betweenness queries in expectation. [ABSTRACT FROM AUTHOR]

We study the problem of identifying the source of a stochastic diffusion process spreading on a graph based on the arrival times of the diffusion at a few queried nodes. In a graph G = (V , E) , an unknown source node v ⁎ ∈ V is drawn uniformly at random, and unknown edge weights w (e) for e ∈ E , representing the propagation delays along the edges, are drawn independently from a Gaussian distribution of mean 1 and variance σ 2. An algorithm then attempts to identify v ⁎ by querying nodes q ∈ V and being told the length of the shortest path between q and v ⁎ in graph G weighted by w. We consider two settings: non-adaptive , in which all query nodes must be decided in advance, and adaptive , in which each query can depend on the results of the previous ones. Both settings are motivated by an application of the problem to epidemic processes (where the source is called patient zero), which we discuss in detail. We characterize the query complexity when G is an n -node path. In the non-adaptive setting, Θ (n σ 2) queries are needed for σ 2 ≤ 1 , and Θ (n) for σ 2 ≥ 1. In the adaptive setting, somewhat surprisingly, only Θ (log ⁡ log 1 / σ ⁡ n) are needed when σ 2 ≤ 1 / 2 , and Θ (log ⁡ log ⁡ n) + O σ (1) when σ 2 ≥ 1 / 2. This is the first mathematical study of source identification with time queries in a non-deterministic diffusion process. [ABSTRACT FROM AUTHOR]

k -Clustering partitions a set of n points in a metric space into at most k clusters in a way that makes the resulted clusters satisfy both the homogeneity and the separation criteria. The diameter of a cluster is the maximum distance between pairs of points in the cluster, and the split of a cluster is the minimum distance between points of the cluster and ones outside the cluster. In this paper, we propose a new criterion for measuring the goodness of clusters: The ratio of the minimum cluster split to the maximum cluster diameter (abbr. RSD). We study the following two optimization problems: Maximizing RSD without and with cardinality constraints, i.e., each cluster should consist of at least N points. For both problems with k ≥ 3 , it is NP-hard to achieve a factor of (1 2 + ϵ) approximation for any ϵ > 0. For k = 2 , we solve the two problems optimally; For k ≥ 3 , we present a 1 2 -approximation and a 1 4 -approximation algorithm for the two problems, respectively. [ABSTRACT FROM AUTHOR]

A q-degenerate k-partition of a graph G is a collection (V 1 , V 2 , ... , V k) of k pairwise disjoint subsets of V (G) such that V (G) = ⋃ i = 1 k V i and each V i induces a q -degenerate subgraph. Such a partition is called equitable if | | V i | − | V j | | ≤ 1 for every 1 ≤ i < j ≤ k. Equitable partition of graphs can model the problem of partitioning a large network into smaller sub-modules based on some cardinal principles, and has many other applications in network science and information science. In this work, we establish theoretical and algorithmic results on equitably partitioning degenerate graphs into graphs with lower degeneracy. Specifically, we show that every n -vertex d -degenerate graph with maximum degree at most n / β has a q -degenerate k -partition (V 1 , V 2 , ... , V k) for every k ≥ α d so that each V i has size at most ⌈ n / k ⌉ whenever q , α , and β satisfy a well-defined inequality, and such a partition can be computed in cubic time. [ABSTRACT FROM AUTHOR]

The k -dimensional Weisfeiler-Leman algorithm (k - WL) is a very useful combinatorial tool in graph isomorphism testing. We address the applicability of k - WL to recognition of graph properties. Let G be an input graph with n vertices. We show that, if n is prime, then vertex-transitivity of G can be seen in a straightforward way from the output of 2 - WL on G and on the vertex-individualized copies of G. This is perhaps the first non-trivial example of using the Weisfeiler-Leman algorithm for recognition of a natural graph property rather than for isomorphism testing. On the other hand, we show that, if n is divisible by 16, then k - WL is unable to distinguish between vertex-transitive and non-vertex-transitive graphs with n vertices unless k = Ω (n). Similar results are obtained for recognition of arc-transitivity. Our lower bounds are based on an analysis of the Cai-Fürer-Immerman construction, which might be of independent interest. In particular, we provide sufficient conditions under which the Cai-Fürer-Immerman graphs can be made colorless. • The Weisfeiler-Leman algorithm is used to recognize vertex-transitivity of graphs with a prime number of vertices • This is perhaps the first example of using it for recognition of a natural graph property rather than for isomorphism testing • This is no longer possible if the number of vertices is divisible by 16 • The negative result is based on an analysis of the Cai-Fürer-Immerman construction • This analysis might be of independent interest as it provides a very straight way of making the CFI graphs colorless [ABSTRACT FROM AUTHOR]

A major breakthrough in the diagnosis of t -diagnosable systems occurred when Dahbura and Mason developed a diagnosis algorithm under the PMC model using the matching theory in bipartite graphs. In this paper we introduce a new testing model called the symmetric PMC(SPMC) model. Our main contributions are as follows: We prove that the diagnosability of an n -dimensional hypercube under the SPMC model is almost twice its diagnosability under the PMC model. We then show that the fault diagnosis problem for a t -diagnosable system under the SPMC model reduces to that of determining a maximum weighted b -matching in its diagnosis graph. Algorithm LABEL is then given to identify all the faulty vertices using the maximum b -matching of the diagnosis graph. Finally, using certain results from the theory of partitions of integers we establish the worst case complexity of our t -diagnosis algorithm. The complexity is much better than the worst case complexity of the Dahbura-Mason algorithm for the t -diagnosable problem under the PMC model. [ABSTRACT FROM AUTHOR]

We study the Steiner k -eccentricity on trees, which generalizes the previous one in the paper [On the average Steiner 3-eccentricity of trees, arXiv:2005.10319 ]. We achieve much stronger properties for the Steiner k -ecc tree than that in the previous paper. Based on this, a linear time algorithm is devised to calculate the Steiner k -eccentricity of a vertex in a tree. On the other hand, lower and upper bounds of the average Steiner k -eccentricity index of a tree on order n are established based on a novel technique which is quite different and also much easier to follow than the earlier one. [ABSTRACT FROM AUTHOR]

• We study Balanced Connected Subgraph (BCS) and its weighted version (WBCS). • We propose several new complexity and inapproximation results for these problems. • BCS is NPC and noAPX on chordal graphs. • BCS is NPX and noAPX on planar or bipartite graphs with maximum degree 4. • BCS is also NPC on graphs with diameter 3, and on bipartite graphs with diameter 4 or with maximum degree 3. This work is devoted to the study of the Balanced Connected Subgraph Problem (BCS) from a complexity, inapproximability and approximation point of view. The input is a graph G = (V , E) , with each vertex having been colored, "red" or "blue"; the goal is to find a maximum connected subgraph G ′ = (V ′ , E ′) from G that is color-balanced (having exactly | V ′ | / 2 red vertices and | V ′ | / 2 blue vertices). This problem is known to be NP -complete in general but polynomial in paths and trees. We propose a polynomial-time algorithm for block graph. We propose some complexity results for bounded-degree or bounded-diameter graphs, and also for bipartite graphs. We also propose inapproximability results for some graph classes, including chordal, planar, or subcubic graphs. [ABSTRACT FROM AUTHOR]

• We prove that Decide-UR Matching problem is NP-complete for chordal bipartite graphs and star-convex bipartite graphs. • We prove that Decide-UR Matching problem is NP-complete for chordal graphs and doubly chordal graphs. • We prove that a minimum cardinality maximal uniquely restricted matching can be computed in polynomial time for bipartite distance-hereditary graphs. • We prove that a minimum cardinality maximal uniquely restricted matching can be computed in linear time for bipartite permutation graphs, proper interval graphs, and threshold graphs. • We prove that the problem is APX-complete for bounded degree graphs. A subset M ⊆ E of edges of a graph G = (V , E) is called a matching if no two edges of M share a common vertex. A matching M in a graph G is called a uniquely restricted matching if, G [ V (M) ] , the subgraph of G induced by the set of M -saturated vertices of G contains exactly one perfect matching. A uniquely restricted matching M is maximal if M is not properly contained in any uniquely restricted matching of G. Given a graph G , the Min-Max-UR Matching problem asks to find a maximal uniquely restricted matching in G of minimum cardinality and Decide-Min-Max-UR Matching problem, the decision version of this problem takes a graph G and an integer k and asks whether G admits a maximal uniquely restricted matching of cardinality at most k. It is known that the Decide-Min-Max-UR Matching problem is NP-complete. In this paper, we strengthen this result by proving that the Decide-Min-Max-UR Matching problem remains NP -complete for chordal bipartite graphs, star-convex bipartite graphs, chordal graphs, and doubly chordal graphs. On the positive side, we prove that the Min-Max-UR Matching problem is polynomial time solvable for bipartite distance-hereditary graphs and linear time solvable for bipartite permutation graphs, proper interval graphs, and threshold graphs. Finally, we prove that the Min-Max-UR Matching problem is APX -complete for graphs with maximum degree 4. [ABSTRACT FROM AUTHOR]

The Maximum Weight Independent Set (MWIS) problem on finite undirected graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum weight sum. MWIS is one of the most investigated and most important algorithmic graph problems; it is well known to be NP-complete, and it remains NP-complete even under various strong restrictions such as for triangle-free graphs. Its complexity for P k -free graphs, k ≥ 7 , is an open problem. In [7] , it is shown that MWIS can be solved in polynomial time for (P 7 ,triangle)-free graphs. This result is extended by Maffray and Pastor [22] showing that MWIS can be solved in polynomial time for (P 7 ,bull)-free graphs. In the same paper, they also showed that MWIS can be solved in polynomial time for (S 1 , 2 , 3 ,bull)-free graphs. In this paper, using a similar approach as in [7] , we show that MWIS can be solved in polynomial time for (S 1 , 2 , 4 ,triangle)-free graphs which generalizes the result for (P 7 ,triangle)-free graphs. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of fast constructions of source-wise round-trip spanners in weighted directed graphs. For a source vertex set S ⊆ V in a graph G (V , E) , an S -sourcewise round-trip spanner of G of stretch k is a subgraph H of G such that for every pair of vertices u , v ∈ S × V , their round-trip distance in H is at most k times of their round-trip distance in G. We show that for a graph G (V , E) with n vertices and m edges, an s -sized source vertex set S ⊆ V and an integer k > 1 , there exists an algorithm that in time O (m s 1 / k log 5 ⁡ n) constructs an S -sourcewise round-trip spanner of stretch O (k log ⁡ n) and O (n s 1 / k log 2 ⁡ n) edges with high probability. Compared to the fast algorithms for constructing all-pairs round-trip spanners [26,12] , our algorithm improves the running time and the number of edges in the spanner when k is super-constant. Compared with the existing algorithm for constructing source-wise round-trip spanners [36] , our algorithm significantly improves their construction time Ω (min ⁡ { m s , n ω }) (where ω ∈ [ 2 , 2.373) and 2.373 is the matrix multiplication exponent) to nearly linear O (m s 1 / k log 5 ⁡ n) , at the expense of paying an extra O (log ⁡ n) in the stretch. As an important building block of the algorithm, we develop a graph partitioning algorithm to partition G into clusters of bounded radius and prove that for every u , v ∈ S × V at small round-trip distance, the probability of separating them in different clusters is small. The algorithm takes the size of S as input and does not need the knowledge of S. With the algorithm and a reachability vertex size estimation algorithm, we show that the recursive algorithm for constructing standard round-trip spanners [26] can be adapted to the source-wise setting. We rigorously prove the correctness and computational complexity of the adapted algorithms. Finally, we show how to remove the dependence on the edge weight in the source-wise case. [ABSTRACT FROM AUTHOR]

We study algorithms for graph problems in which the graphs are of extremely large size N so that super-linear time ω (N) or linear space Θ (N) would become impractical. We use a parameter k to characterize the computational power of a normal computer that can provide additional time and space bounded by polynomials of k in dealing with the large graphs. In particular, we are interested in strict linear-time algorithms using space O (k O (1)). In our case studies, as examples, we present (1) a randomized greedy algorithm of time O (N) and space O (k 2) for a parameterized version of the Maximal Matching problem; and (2) randomized kernelization algorithms of time O (N) and space O (k O (1)) for a number of well-known NP-hard problems. Our kernelization algorithms have their kernel sizes match the best kernel sizes by known polynomial-time kernelization algorithms with no space constraints for the problems. We also study the relationship between our proposed model and the streaming model. This study motivates a new streaming kernelization algorithm for the famous Vertex Cover problem that has an optimal update time complexity while matches the best known space complexity of streaming algorithms for the problem. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a problem called Minimum subTree problem with Degree Weights , or MTDW. This problem generalized covering tree problems like Spanning Tree , Steiner Tree , Minimum Branch Vertices , Minimum Leaf Spanning Tree , or Prize Collecting Steiner Tree. It consists, given an undirected graph G = (V , E) , a set of m + 1 mappings C 1 , C 2 , ... , C m , D : V × N → Z , a set of m integers K 1 , K 2 , ... , K m ∈ Z and a positive integer ℓ , in the search of a forest (T 1 , T 2 , ... , T ℓ) containing ℓ node-disjoint trees of G. Along with K j , the mapping C j defines a constraint that should be satisfied by the trees of the forest. For each tree T i , it associates each node v of V to the score C j (v , d T i (v)) where d T i (v) is the degree of v in T i (possibly 0 if the node is not in T i). The sum ∑ v ∈ V C j (v , d T i (v)) should not exceed K j. In addition, the forest should minimize ∑ i = 1 ℓ ∑ v ∈ V D (v , d T i (v)). We proceed to a parameterized analysis of the MTDW problem with regard to four parameters that are the number of constraints m , the value ℓ , the treewidth of the input graph G and Δ, the minimum degree above which all the constraints and D are constant (for every j ∈ 〚 1 , m 〛 , v ∈ V and d ≥ Δ , C j (v , d) = C j (v , Δ) , and D (v , d) = D (v , Δ)). For this problem, we provide a first dichotomy P versus NP -hard depending whether the previous parameters are fixed to be constant or not and a second dichotomy FPT versus W[1] -hard depending whether each of these parameters is constant, considered as a parameter, or disregard. As a side effect, we obtained parameterized algorithms, previously undescribed, for problems such that Budget Steiner Tree problem with Profits , Minimum Branch Vertices , Generalized branch vertices , or k -Bottleneck Steiner Tree. [ABSTRACT FROM AUTHOR]

We introduce the game of Cops and Eternal Robbers played on graphs, where there are infinitely many robbers that appear sequentially over distinct plays of the game. A positive integer t is fixed, and the cops are required to capture the robber in at most t time-steps in each play. The associated optimization parameter is the eternal cop number, denoted by c t ∞ , which equals the eternal domination number in the case t = 1 , and the cop number for sufficiently large t. We study the complexity of Cops and Eternal Robbers, and show that the game is NP -hard when t is a fixed constant and EXPTIME -complete for large values of t. We determine precise values of c t ∞ for paths and cycles. The eternal cop number is studied for retracts, and this approach is applied to give bounds for trees, as well as for strong and Cartesian grids. [ABSTRACT FROM AUTHOR]

• A quadratic-time algorithm for the maximum bisection problem on bounded-treewidth graphs is presented. • The running time of our algorithm is optimal, assuming some complexity-theoretic lower bounds. • Several algorithmic and complexity results for restricted graph classes are discussed. The maximum/minimum bisection problems are, given an edge-weighted graph, to find a bipartition of the vertex set into two sets whose sizes differ by at most one, such that the total weight of edges between the two sets is maximized/minimized. Although these two problems are known to be NP-hard, there is an efficient algorithm for bounded-treewidth graphs. In particular, Jansen et al. (2005) [5] gave an O (2 t n 3) -time algorithm when given a tree decomposition of width t of the input graph, where n is the number of vertices of the input graph. Eiben et al. (2021) [10] improved the dependency of n in the running time by giving an O (8 t t 5 n 2 log ⁡ n) -time algorithm. Moreover, they showed that there is no O (n 2 − ε) -time algorithm for trees under some reasonable complexity assumption. In this paper, we show an O (2 t (t n) 2) -time algorithm for both problems, which is asymptotically tight to their conditional lower bound. We also show that the exponential dependency of the treewidth is asymptotically optimal under the Strong Exponential Time Hypothesis. Finally, we discuss the (in)tractability of both problems with respect to special graph classes. [ABSTRACT FROM AUTHOR]

Prefetching constitutes a valuable tool toward the goal of efficient Web surfing. As a result, estimating the amount of resources that need to be preloaded during a surfer's browsing becomes an important task. In this regard, prefetching can be modeled as a two-player combinatorial game (Fomin et al. (2014) [6]), where a surfer and a marker alternately play on a given graph (representing the Web graph). During its turn, the marker chooses a set of k nodes to mark (prefetch), whereas the surfer, represented as a token resting on graph nodes, moves to a neighboring node (Web resource). The surfer's objective is to reach an unmarked node before all nodes become marked and the marker wins. Intuitively, since the surfer is step-by-step traversing a subset of nodes in the Web graph, a satisfactory prefetching procedure would load in cache (without any delay) all resources lying in the neighborhood of this growing subset. Motivated by the above, we consider the following maximization problem to which we refer to as the Maximum Rooted Connected Expansion (MRCE) problem. Given a graph G and a root node v 0 , we wish to find a subset of vertices S such that S is connected, S contains v 0 and the ratio | N [ S ] | | S | is maximized, where N [ S ] denotes the closed neighborhood of S , that is, N [ S ] contains all nodes in S and all nodes with at least one neighbor in S. We prove that the problem is NP-hard even when the input graph G is restricted to be a split graph. On the positive side, we demonstrate a Polynomial Time Approximation Scheme (PTAS) for split graphs. Furthermore, we present a 1 6 (1 − 1 e) -approximation algorithm for general graphs based on techniques for the Budgeted Connected Domination problem (Khuller et al. (2014) [20]). Finally, we provide a polynomial-time algorithm for the special case of interval graphs. Our algorithm returns an optimal solution for MRCE in O (n 3) time, where n is the number of nodes in G , and in logarithmic space. [ABSTRACT FROM AUTHOR]

We initiate the systematic algorithmic study for gerrymandering over graphs that was recently introduced by Cohen-Zemach, Lewenberg and Rosenschein. Namely, we study a strategic procedure for a political districting designer to draw electoral district boundaries so that a particular target candidate can win in an election. We focus on the existence of such a strategy under the plurality voting rule, and give interesting contrasts which classify easy and hard instances with respect to polynomial-time solvability. For example, we prove that the problem for trees is strongly NP -complete (thus unlikely to have a pseudo-polynomial-time algorithm), but has a pseudo-polynomial-time algorithm when the number of candidates is constant. Another example is to prove that the problem for complete graphs is NP -complete when the number of electoral districts is two, while is solvable in polynomial time when it is more than two. [ABSTRACT FROM AUTHOR]

• The approximability and the computational complexity of the Maximum Happy Set problem (MaxHS) are studied. • A (2 Δ + 1) -approximation algorithm for MaxHS on graphs with maximum degree Δ is presented. • The approximation ratio is improved to Δ if the maximum degree Δ is a constant. • The polynomial-time solvability of MaxHS on block/interval graphs is proved. • The NP-hardness of MaxHS on bipartite/cubic graphs is proved. In this paper we study the approximability of the Maximum Happy Set problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph G = (V , E) and a subset S ⊆ V of vertices, a vertex v is happy if v and all its neighbors are in S ; otherwise unhappy. Given an undirected graph G = (V , E) and an integer k , the goal of MaxHS is to find a subset S ⊆ V of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a (2 Δ + 1) -approximation algorithm for MaxHS on graphs with maximum degree Δ. Next, we show that the approximation ratio can be improved to Δ if the maximum degree Δ of the input graph is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to block graphs, or interval graphs. We prove nevertheless that MaxHS on bipartite graphs or on cubic graphs remains NP-hard. [ABSTRACT FROM AUTHOR]

• We analyze the approximability of the independent feedback vertex set problem. • The problem is hard to approximate on planar bipartite graphs. • There is an efficient approximation algorithm for bipartite graphs of bounded maximum degree. • The problem is solvable in polynomial time if a given bipartite graph is of maximum degree three. Given an undirected graph G with n vertices, the independent feedback vertex set problem is to find a vertex subset F of G with the minimum number of vertices such that F is both an independent set and a feedback vertex set of G , if it exists. This problem is known to be NP-hard for bipartite planar graphs of maximum degree four. In this paper, we study the approximability of the problem. We first show that, for any fixed ε > 0 , unless P = NP , there exists no polynomial-time n 1 − ε -approximation algorithm even for bipartite planar graphs. We then give an α (Δ − 1) / 2 -approximation algorithm for bipartite graphs G of maximum degree Δ, which runs in t (α , G) + O (Δ n) time, under the assumption that there is an α -approximation algorithm for the original feedback vertex set problem on bipartite graphs which runs in t (α , G) time. This algorithmic result also yields a polynomial-time (exact) algorithm for the independent feedback vertex set problem on bipartite graphs of maximum degree three. [ABSTRACT FROM AUTHOR]

More than two decades ago, combinatorial topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems. In this work, we show that combinatorial topology can also be useful for analyzing distributed algorithms in failure-free networks of arbitrary structure. To illustrate this, we analyze consensus, set-agreement, and approximate agreement in networks, and derive lower bounds for these problems under classical computational settings, such as the local model and dynamic networks. [ABSTRACT FROM AUTHOR]

We study the task of gathering k energy-constrained mobile agents in an undirected edge-weighted graph. Each agent is initially placed on an arbitrary node and has a limited amount of energy, which constrains the distance it can move. Since this may render gathering at a single point impossible, we study three variants of near-gathering : The goal is to move the agents into a configuration that minimizes either (i) the radius of a ball containing all agents, (ii) the maximum distance between any two agents, or (iii) the average distance between the agents. We prove that (i) is polynomial-time solvable, (ii) has a polynomial-time 2-approximation with a matching NP-hardness lower bound, while (iii) admits a polynomial-time 2 (1 − 1 k) -approximation, but no FPTAS, unless P = NP. We extend some of our results to additive approximation. [ABSTRACT FROM AUTHOR]

We present an algorithm to color a graph G with no triangle and no induced 7-vertex path (i.e., a { P 7 , C 3 } -free graph), where every vertex is assigned a list of possible colors which is a subset of { 1 , 2 , 3 }. While this is a special case of the problem solved in Bonomo et al. (2018) [1] , that does not require the absence of triangles, the algorithm here is both faster and conceptually simpler. The complexity of the algorithm is O (| V (G) | 5 (| V (G) | + | E (G) |)) , and if G is bipartite, it improves to O (| V (G) | 2 (| V (G) | + | E (G) |)). Moreover, we prove that there are finitely many minimal obstructions to list 3-coloring { P t , C 3 } -free graphs if and only if t ≤ 7. This implies the existence of a polynomial time certifying algorithm for list 3-coloring in { P 7 , C 3 } -free graphs. We furthermore determine other cases of t , ℓ , and k such that the family of minimal obstructions to list k -coloring in { P t , C ℓ } -free graphs is finite. [ABSTRACT FROM AUTHOR]

A subset D ⊆ V of a graph G = (V , E) is called a global total k -dominating set of G if D is a total k -dominating set of both G and the complement G ‾ of G. The Minimum Global Total k -Domination problem is to find a global total k -dominating set of minimum cardinality of the input graph G and Decide Global Total k -Domination problem is the decision version of Minimum Global Total k -Domination problem. The Decide Global Total k -Domination problem is known to be NP -complete for general graphs as well as for bipartite graphs. In this paper, we strengthen the NP -completeness result of Decide Global Total k -Domination problem by showing that this problem remains NP -complete for perfect elimination bipartite graphs, star-convex bipartite graphs and doubly chordal graphs. On the positive side, we give a polynomial time algorithm for the Minimum Global Total k -Domination problem for chordal bipartite graphs, which is a subclass of bipartite graphs. We propose a 2 (1 + ln ⁡ | V |) -approximation algorithm for the Minimum Global Total k -Domination problem for any graph. We show that Minimum Global Total k -Domination problem cannot be approximated within (1 − ϵ) ln ⁡ | V | for any ϵ > 0 unless P = NP for any integer k ≥ 1. We further show that for bipartite graphs, Minimum Global Total k -Domination problem cannot be approximated within (1 6 − ϵ) ln ⁡ | V | for any ϵ > 0 unless P = NP for any k ≥ 1. Finally, we show that the Minimum Global Total k -Domination problem is APX -complete for bounded degree bipartite graphs for any fixed integer k ≥ 1. [ABSTRACT FROM AUTHOR]

The Almost Induced Matching problem asks whether we can delete at most k vertices from the input graph such that each vertex in the remaining graph has a degree exactly one. This paper studies parameterized algorithms for this problem by taking the size k of the deletion set as the parameter. We give a 7 k -vertex kernel and an O ⁎ (1.7485 k) -time and polynomial-space algorithm, both of which are the best-known results. The linear-vertex kernel is obtained by using an extended crown decomposition and careful analysis, and the parameterized algorithm is based on a branch-and-search paradigm. [ABSTRACT FROM AUTHOR]

• Designed an optimally efficient graph-based sorting algorithm. • An application of the topological sort optimized for efficiency. • Developed a stable sorting algorithm that is more time-efficient and space-efficient than MergeSort. • Introduces a new graph merging operation that can be applied in other graph applications. • The research achieved the Dean's Award at UC Santa Cruz for excellence in undergraduate research. The quest for efficient sorting is ongoing, and we will explore a graph-based stable sorting strategy, in particular employing comparison graphs. We use the topological sort to map the comparison graph to a linear domain, and we can manipulate our graph such that the resulting topological sort is the sorted array. By taking advantage of the many relations between Hamiltonian paths and topological sorts in comparison graphs, we design a Divide-and-Conquer algorithm that runs in the optimal O (n log ⁡ n) time. In the process, we construct a new merge process for graphs with relevant invariant properties for our use. Furthermore, this method is more space-efficient than the famous MergeSort since we modify our fixed graph only. [ABSTRACT FROM AUTHOR]

The minimum tracking set problem is an optimization problem that deals with monitoring communication paths that can be used for exchanging point-to-point messages using as few tracking devices as possible. More precisely, a tracking set of a given graph G and a set of source-destination pairs of vertices is a subset T of vertices of G such that the vertices in T traversed by any source-destination shortest path P uniquely identify P. The minimum tracking set problem has been introduced in Banik et al., CIAC (2017) [1] for the case of a single source-destination pair. There, the authors show that the problem is APX-hard and that it can be 2-approximated for the class of planar graphs, even though no hardness result is known for this case. In this paper we focus on the case of multiple source-destination pairs and we present the first O ˜ (n) -approximation algorithm for general graphs. Moreover, we prove that the problem remains NP-hard even for cubic planar graphs and all pairs S × D , where S and D are the sets of sources and destinations, respectively. Finally, for the case of a single source-destination pair, we design an (exact) FPT algorithm w.r.t. the maximum number of vertices at the same distance from the source. [ABSTRACT FROM AUTHOR]