An official website of the United States government
In the spanning-tree congestion problem (STC), we are given a graph G, and the objective is to compute a spanning tree of G that minimizes the maximum edge congestion. While STC is known to be NP-hard, even for some restricted graph classes, several key questions regarding its computational complexity remain open, and we address some of these in our paper. (i) For graphs of degree at most Δ, it is known that STC is NP-hard when Δ≥8. We provide a complete resolution of this variant, by showing that STC remains NP-hard for each degree bound Δ≥3. (ii) In the decision version of STC, given an integer K, the goal is to determine whether the congestion of G is at most K. We prove that this variant is polynomial-time solvable for K-edge-connected graphs.
more »
« less
This content will become publicly available on May 1, 2027
Two Complexity Results on Spanning-Tree Congestion Problems
Abstract. In the spanning-tree congestion problem (STC), we are given a graph G, and the objective is to compute a spanning tree of G that minimizes the maximum edge congestion. While STC is known to be NP-hard, even for some restricted graph classes, several key questions regarding its computational complexity remain open, and we address some of these in our paper. (i) For graphs of degree at most d, it is known that STC is NP-hard when d ≥ 8. We provide a complete resolution of this variant, by showing that STC remains NP-hard for each degree bound d ≥ 3. (ii) In the decision version of STC, given an integer K, the goal is to determine whether the congestion of G is at most K. We prove that this variant is polynomial-time solvable for K-edge-connected graphs.
more »
« less
- Award ID(s):
- 2153723
- PAR ID:
- 10694074
- Publisher / Repository:
- LATIN'26
- Date Published:
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract In the spanning tree congestion problem, given a connected graphG, the objective is to compute a spanning treeTinGthat minimizes its maximum edge congestion, where the congestion of an edgeeofTis the number of edges inGfor which the unique path inTbetween their endpoints traversese. The problem is known to be$$\mathbb{N}\mathbb{P}$$ -hard, but its approximability is still poorly understood, and it is not even known whether the optimum solution can be efficiently approximated with ratioo(n). In the decision version of this problem, denoted$${\varvec{K}-\textsf {STC}}$$ , we need to determine ifGhas a spanning tree with congestion at mostK. It is known that$${\varvec{K}-\textsf {STC}}$$ is$$\mathbb{N}\mathbb{P}$$ -complete for$$K\ge 8$$ , and this implies a lower bound of 1.125 on the approximation ratio of minimizing congestion. On the other hand,$${\varvec{3}-\textsf {STC}}$$ can be solved in polynomial time, with the complexity status of this problem for$$K\in { \left\{ 4,5,6,7 \right\} }$$ remaining an open problem. We substantially improve the earlier hardness results by proving that$${\varvec{K}-\textsf {STC}}$$ is$$\mathbb{N}\mathbb{P}$$ -complete for$$K\ge 5$$ . This leaves only the case$$K=4$$ open, and improves the lower bound on the approximation ratio to 1.2. Motivated by evidence that minimizing congestion is hard even for graphs of small constant radius, we also consider$${\varvec{K}-\textsf {STC}}$$ restricted to graphs of radius 2, and we prove that this variant is$$\mathbb{N}\mathbb{P}$$ -complete for all$$K\ge 6$$ .more » « less
-
Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let G be a connected bounded-degree graph. Given an edge e in G we would like to decide whether e belongs to a connected subgraph math formula consisting of math formula edges (for a prespecified constant math formula), where the decision for different edges should be consistent with the same subgraph math formula. Can this task be performed by inspecting only a constant number of edges in G? Our main results are: We show that if every t-vertex subgraph of G has expansion math formula then one can (deterministically) construct a sparse spanning subgraph math formula of G using few inspections. To this end we analyze a “local” version of a famous minimum-weight spanning tree algorithm. We show that the above expansion requirement is sharp even when allowing randomization. To this end we construct a family of 3-regular graphs of high girth, in which every t-vertex subgraph has expansion math formula. We prove that for this family of graphs, any local algorithm for the sparse spanning graph problem requires inspecting a number of edges which is proportional to the girth.more » « less
-
In recent years several compressed indexes based on variants of the Burrows-Wheeler transformation have been introduced. Some of these are used to index structures far more complex than a single string, as was originally done with the FM-index [Ferragina and Manzini, J. ACM 2005]. As such, there has been an increasing effort to better understand under which conditions such an indexing scheme is possible. This has led to the introduction of Wheeler graphs [Gagie et al., Theor. Comput. Sci., 2017]. Gagie et al. showed that de Bruijn graphs, generalized compressed suffix arrays, and several other BWT related structures can be represented as Wheeler graphs and that Wheeler graphs can be indexed in a way which is space-efficient. Hence, being able to recognize whether a given graph is a Wheeler graph, or being able to approximate a given graph by a Wheeler graph, could have numerous applications in indexing. Here we resolve the open question of whether there exists an efficient algorithm for recognizing if a given graph is a Wheeler graph. We present - The problem of recognizing whether a given graph G=(V,E) is a Wheeler graph is NP-complete for any edge label alphabet of size sigma >= 2, even when G is a DAG. This holds even on a restricted, subset of graphs called d-NFA's for d >= 5. This is in contrast to recent results demonstrating the problem can be solved in polynomial time for d-NFA's where d <= 2. We also show the recognition problem can be solved in linear time for sigma =1; - There exists an 2^{e log sigma + O(n + e)} time exact algorithm where n = |V| and e = |E|. This algorithm relies on graph isomorphism being computable in strictly sub-exponential time; - We define an optimization variant of the problem called Wheeler Graph Violation, abbreviated WGV, where the aim is to remove the minimum number of edges in order to obtain a Wheeler graph. We show WGV is APX-hard, even when G is a DAG, implying there exists a constant C >= 1 for which there is no C-approximation algorithm (unless P = NP). Also, conditioned on the Unique Games Conjecture, for all C >= 1, it is NP-hard to find a C-approximation; - We define the Wheeler Subgraph problem, abbreviated WS, where the aim is to find the largest subgraph which is a Wheeler Graph (the dual of the WGV). In contrast to WGV, we prove that the WS problem is in APX for sigma=O(1); The above findings suggest that most problems under this theme are computationally difficult. However, we identify a class of graphs for which the recognition problem is polynomial-time solvable, raising the open question of which parameters determine this problem's difficulty.more » « less
-
In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NP-hard and hard to approximate within a factor of n1−ε for any ε > 0. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In H-free graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NP-hard and APX-hard whenever H contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of H is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomial-time solvability results for small graphs H such as P5, P6, the claw, or the fork. We prove that for every such “possibly tractable” graph H there exists an algorithm that, given an H-free graph G and an accuracy parameter ε > 0, finds an independent set in G of cardinality within a factor of (1 – ε) of the optimum in time exponential in a polynomial of log | V(G) | and ε−1. That is, we show that for every graph H for which Maximum Independent Set is not known to be APX-hard in H-free graphs, the problem admits a quasi-polynomial time approximation scheme in this graph class. Our algorithm works also in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set.more » « less
