Search

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]

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]

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]

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]

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]

• 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]

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]

In the 2-Club Cluster Vertex Deletion (resp., 2-Club Cluster Edge Deletion) 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 (resp., edges) whose removal from G results in a graph in which the diameter of every connected component is at most 2. In this paper we give algorithms for 2-Club Cluster Vertex Deletion and 2-Club Cluster Edge Deletion whose running times are O ⁎ (3.104 k) and O ⁎ (2.562 k) , respectively. Our algorithms were obtained using automated generation of branching rules. Our results improve the previous O ⁎ (3.303 k) -time algorithm for 2-Club Cluster Vertex Deletion [Liu et al., FAW-AAIM 2012] and the O ⁎ (2.695 k) -time algorithm for 2-Club Cluster Edge Deletion [Abu-Khzam et al., TCS 2023]. [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]

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]

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]

The multi-service center problem is a variant of facility location problems. In the problem, we consider locating p facilities on a graph, each of which provides distinct service required by all vertices. Each vertex incurs the cost determined by the sum of the weighted distances to the p facilities. The aim of the problem is to minimize the maximum cost among all vertices. This problem is known to be NP-hard for general graphs, while it is solvable in polynomial time when p is a fixed constant. In this paper, we give sharp analyses for the complexity of the problem from the viewpoint of graph classes and weights on vertices. We first propose a polynomial-time algorithm for trees when p is a part of input. In contrast, we prove that the problem becomes strongly NP-hard even for cycles. We also show that when vertices are allowed to have negative weights, the problem becomes NP-hard for paths of only three vertices and strongly NP-hard for stars. [ABSTRACT FROM AUTHOR]

Given an edge-weighted undirected graph G = (V , E , w) and a subset T ⊆ V of p terminals, a k-Steiner forest spanning all the terminals in T includes k branches, where every branch is a Steiner tree. The diameter of a k -Steiner forest is referred to as the maximum distance between two terminals of a branch. This paper studies the minimum diameter k-Steiner forest problem (MD k SFP) and establishes the relationship between MD k SFP and the absolute k-Steiner center problem (A k SCP). We first obtain a 2-factor dual approximation algorithm for A k SCP, and then achieve a 2-approximation algorithm for MD k SFP based on the 2-approximation to A k SCP. Furthermore, we develop an improved 2 ρ -approximation algorithm for MD k SFP, where ρ < 1 in general, by perturbing the sites of facilities and re-clustering the terminals. [ABSTRACT FROM AUTHOR]

A mixed domination of a graph G = (V , E) is a mixed set D of vertices and edges such that for every edge or vertex, if it is not in D , then it is adjacent or incident to at least one vertex or edge in D. The Mixed Domination problem is to check whether there is a mixed domination of size at most k in a graph. Mixed domination is a mixture concept of vertex domination and edge domination, and the mixed domination problem has been studied from the view of approximation algorithms, parameterized algorithms, and so on. In this paper, we give a branch-and-search algorithm with running time bound of O ⁎ (4.172 k) , which improves the previous bound of O ⁎ (7.465 k). For kernelization, it is known that the problem parameterized by k in general graphs is unlikely to have a polynomial kernel. We show the problem in planar graphs allows linear kernel by giving a kernel of 11 k − 16 vertices. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) without an isolated edge, a set D ⊆ E is an edge total dominating set of G if every edge e ∈ E is adjacent to at least one edge of D. The Minimum Edge Total Dominating Set problem is to compute a minimum cardinality edge total dominating set of G. It is known that the decision version of the problem is NP-complete for bipartite graphs, chordal graphs, and planar graphs. On the positive side, the problem is efficiently solvable for trees. In this paper, we further study the complexity of this problem in other graph classes. We design a linear-time algorithm to compute a minimum cardinality edge total dominating set in chain graphs, a subclass of bipartite graphs. We also propose linear-time algorithms for two subclasses of chordal graphs, namely, split graphs and proper interval graphs with no cut vertices. In addition, we show that the problem is APX-complete for graphs with maximum degree 3 and propose an approximation algorithm for the problem in k -regular graphs, where k ≥ 4. We discuss the complexity difference between the Minimum Edge Dominating Set problem and Minimum Edge Total Dominating Set problem which seem to be closely related. [ABSTRACT FROM AUTHOR]

To solve reachability is to determine whether there is a path from one vertex to the other in a graph. Standard graph traversal algorithms such as DFS and BFS take linear time to solve reachability; however, their space complexity is also linear. On the other hand, Savitch's algorithm takes quasipolynomial time, although the space-bound is O (log 2 ⁡ n). In this paper, we study space-efficient algorithms for deciding reachability that runs in polynomial time. We show a polynomial-time algorithm that solves reachability in directed graphs using O (w log ⁡ n) space. Our algorithm requires access to a tree decomposition of width w for the underlying undirected graph of the input. This requirement can be waived for graphs for which recursive balanced vertex separators can be computed space-efficiently. [ABSTRACT FROM AUTHOR]

Partitioning a network into k pieces is a fundamental problem in network science. A simple measure of partitioning a network is provided by the Max k -Uncut problem. Given an n -vertex undirected graph G with nonnegative weights defined on edges, and a positive integer k , the Max k -Uncut problem asks to find a k -partition of the vertices of G to maximize the total weight of edges that are not in the cut. This problem is the complement of the classic Min k -Cut problem, and has close relation to many combinatorial optimization problems, including the famous Densest k -Subgraph problem. In this paper, we propose a greedy approximation algorithm for the Max k -Uncut problem with performance ratio 1 − 2 (k − 1) n. The algorithm is very simple, which consists of only k − 1 min cut computations. The algorithm has fast running time O (k n 2) and is hence implementable. The experimental results show that the algorithm has excellent practical performance. [ABSTRACT FROM AUTHOR]

In 2005, Goddard et al. (2005) [12] asked the computational complexity of determining the maximum cardinality of a matching whose vertex set induces a disconnected graph. In this paper, we answer this question. In fact, we consider the generalized problem of finding c-disconnected matchings ; such matchings are ones whose vertex sets induce subgraphs with at least c connected components. We show that, for every fixed c ≥ 2 , this problem is NP - complete even if we restrict the input to bounded diameter bipartite graphs, while can be solved in polynomial time if c = 1. For the case when c is part of the input, we show that the problem is NP - complete for chordal graphs, while being solvable in polynomial time for interval graphs. Finally, we explore the parameterized complexity of the problem. We present an FPT algorithm under the treewidth parameterization, and an XP algorithm for graphs with a polynomial number of minimal separators when parameterized by c. We complement these results by showing that, unless NP ⊆ coNP / poly , the related Induced Matching problem does not admit a polynomial kernel when parameterized by vertex cover and size of the matching nor when parameterized by vertex deletion distance to clique and size of the matching. As for Connected Matching , we show how to obtain a maximum connected matching in linear time given an arbitrary maximum matching in the input. • NP-complete even for bipartite graphs, for every fixed c at least 2. • NP-complete even for chordal graphs if c is part of the input. • Solvable in polynomial time for interval graphs and in FPT time when parameterized by treewidth. • Induced Matching is unlikely to admit polynomial kernels under common structural parameterizations. [ABSTRACT FROM AUTHOR]

Graph editing problems offer an interesting perspective on sub- and supergraph identification problems for a large variety of target properties. They have also attracted significant attention in recent years, particularly in the area of parameterized complexity as the problems have rich parameter ecologies. In this paper we examine generalisations of the notion of editing a graph to obtain a regular subgraph. In particular we extend the notion of regularity to include two variants of edge-regularity along with the unifying constraint of strong regularity. We present a number of results, with the central observation that these problems retain the general complexity profile of their regularity-based inspiration: when the number of edits k and the maximum degree r are taken together as a combined parameter, the problems are tractable (i.e. in FPT ), but are otherwise intractable. We also examine variants of the basic editing to obtain a regular subgraph problem from the perspective of parameterizing by the treewidth of the input graph. In this case the treewidth of the input graph essentially becomes a limiting parameter on the natural k + r parameterization. [ABSTRACT FROM AUTHOR]

In the Bicluster Editing (resp., Flip Consensus Tree) problem the input is a bipartite graph G = (V 1 , V 2 , E) and an integer k , and the goal is to decide whether there is a set F ⊆ V 1 × V 2 such that the graph (V 1 , V 2 , E △ F) does not contain an induced path on four vertices (resp., an induced path on five vertices whose endpoints are in V 2). In this paper we give algorithms for Bicluster Editing and Flip Consensus Tree whose running times are O ⁎ (2.22 k) and O (3.24 k) , respectively. This improves over the O ⁎ (2.636 k) -time algorithm for Bicluster Editing of Tsur [IPL 2021] and the O ⁎ (3.68 k) -time algorithm for Flip Consensus Tree of Komusiewicz and Uhlmann [Algorithmica 2014]. [ABSTRACT FROM AUTHOR]

In the game of Kayles , two players select alternatingly a vertex from a given graph G , but may never choose a vertex that is adjacent or equal to an already chosen vertex. The last player that can select a vertex wins the game. In this paper, we give an exact algorithm to determine which player has a winning strategy in this game. To analyze the running time of the algorithm, we introduce the notion of a K-set: a nonempty set of vertices W ⊆ V is a K-set in a graph G = ( V , E ) , if G [ W ] is connected and there exists an independent set X such that W = V − N [ X ] . The running time of the algorithm is bounded by a polynomial factor times the number of K-sets in G . We prove that the number of K-sets in a graph with n vertices is bounded by O ( 1.6052 n ) . A computer-generated case analysis improves this bound to O ( 1.6031 n ) K-sets, and thus we have an upper bound of O ( 1.6031 n ) on the running time of the algorithm for Kayles . We also show that the number of K-sets in a tree is bounded by n ⋅ 3 n / 3 and thus Kayles can be solved on trees in O ( 1.4423 n ) time. We show that apart from a polynomial factor, the number of K-sets in a tree is sharp. As corollaries, we obtain that determining which player has a winning strategy in the games G avoid ( POS DNF 2 ) and G seek ( POSDNF 3 ) can also be determined in O ( 1.6031 n ) time. In G avoid ( POSDNF 2 ) , we have a positive formula F on n Boolean variables in Disjunctive Normal Form with two variables per clause. Initially, all variables are false, and players alternately set a variable from false to true; the first player that makes F true loses the game. The game G seek ( POSDNF 3 ) is similar, but now there are three variables per clause, and the first player that makes F true wins the game. [ABSTRACT FROM AUTHOR]