The tree-independence number tree- alpha $\text{tree\unicode{x02010}}\alpha $, first defined and studied by Dallard, Milani & ccaron;, and & Scaron;torgel, is a variant of treewidth tailored to solving the max...
详细信息
The tree-independence number tree- alpha $\text{tree\unicode{x02010}}\alpha $, first defined and studied by Dallard, Milani & ccaron;, and & Scaron;torgel, is a variant of treewidth tailored to solving the maximum independent set problem. Over a series of papers, Abrishami et al. developed the so-called central bag method to study induced obstructions to bounded treewidth. Among others, they showed that, in a certain superclass C ${\mathscr{C}}$ of (even hole, diamond, pyramid)-free graphs, treewidth is bounded by a function of the clique number. In this paper, we relax the bounded clique number assumption, and show that C ${\mathscr{C}}$ has bounded tree- alpha $\,\text{tree\unicode{x02010}}\,\alpha $. Via existing results, this yields a polynomial-time algorithm for the Maximum Weight Independent Set problem in this class. Our result also corroborates, for this class of graphs, a conjecture of Dallard, Milani & ccaron;, and & Scaron;torgel that in a hereditary graph class, tree- alpha $\,\text{tree\unicode{x02010}}\,\alpha $ is bounded if and only if the treewidth is bounded by a function of the clique number.
We design a framework for assisted normative reasoning based on Aristotelian diagrams and algorithmic graph theory which can be employed to address heterogeneous tasks of deductive reasoning. Here we focus on two prob...
详细信息
ISBN:
(纸本)9781643684727;9781643684734
We design a framework for assisted normative reasoning based on Aristotelian diagrams and algorithmic graph theory which can be employed to address heterogeneous tasks of deductive reasoning. Here we focus on two problems of normative determination: we show that the algorithms used to address these problems are computationally efficient and their operations are traceable by humans. Finally, we discuss an application of our framework to a scenario regulated by the GDPR.
An independent set in a graph G is a collection of vertices with no edge between any two. The Independent Set problem is a classic NP-Hard problem that takes in a graph G and the task is to find an independent set in ...
详细信息
An independent set in a graph G is a collection of vertices with no edge between any two. The Independent Set problem is a classic NP-Hard problem that takes in a graph G and the task is to find an independent set in G of maximum size. An induced subgraph of G is another graph, H, where the vertex set of H is a subset V (H) ⊆ V (G), and the edge set of H is all edges uv in E(G) where u, v ∈ V (H). A graph is said to be H-free if it does not contain H as an induced subgraph. Lastly, quasi-polynomial functions are functions that grow (slightly) faster than polynomial functions by allowing poly-log terms in their exponents, for example, n log2(n) is a quasi-polynomial function. In this thesis, we will provide a quasi-polynomial time algorithm for Independent Set on Pk-free graphs, where Pk denotes a path with k vertices. We will later extend this result in multiple ways. First, we give a quasi-polynomial time algorithm for Independent Set as well as related problems, such as Feedback Vertex Set on C>k-free graphs, which are graphs that do not contain induced cycles with more than k vertices. Additionally, we will give a quasi-polynomial time algorithm for Independent Set on H-free graphs where H is a forest of paths and subdivided claws. A subdivided claw is a graph formed by taking three paths of any desired length along with a vertex v that is a neighbor of exactly one end vertex in each of the three paths. This last result resolves an open problem first investigated by Alekseev in *** a seemingly different research thread, we will characterize graph classes with few minimal separators. A minimal separator is a set S such that there are two vertices u, v in different components of G − S and for any proper subset S ′ ⊂ S, u and v are in the same component of G − S ′ . A class F of graphs is called tame if every graph in F on n vertices contains at most n O(1) minimal separators, quasi-tame if every graph in F on n vertices contains at mostn logO(1)(n) minimal sepa
In the vertex connectivity problem, given an undirected n-vertex m-edge graph G, we need to compute the minimum number of vertices that can disconnect G after removing them. This problem is one of the most well-studie...
详细信息
ISBN:
(纸本)9781665455190
In the vertex connectivity problem, given an undirected n-vertex m-edge graph G, we need to compute the minimum number of vertices that can disconnect G after removing them. This problem is one of the most well-studied graph problems. From 2019, a new line of work [Nanongkai et al. STOC'19;SODA'20;STOC'21] has used randomized techniques to break the quadratic-time barrier and, very recently, culminated in an almost-linear time algorithm via the recently announced maxflow algorithm by Chen et al. In contrast, all known deterministic algorithms are much slower. The fastest algorithm [Gabow FOCS'00] takes O(m( n + min{c(5/2), cn(3/4)})) time where c is the vertex connectivity. It remains open whether there exists a subquadratic-time deterministic algorithm for any constant c > 3. In this paper, we give the first deterministic almost-linear time vertex connectivity algorithm for all constants c. Our running time is m(1+o(1))2(O( c2)) time, which is almost-linear for all c = o(root log n). This is the first deterministic algorithm that breaks the O(n(2))-time bound on sparse graphs where m = O(n), which is known for more than 50 years ago [Kleitman'69]. Towards our result, we give a new reduction framework to vertex expanders which in turn exploits our new almost-linear time construction of mimicking network for vertex connectivity. The previous construction by Kratsch and Wahlstrom [FOCS'12] requires large polynomial time and is randomized.
The generation of constitutional isomer chemical spaces has been a subject of cheminformatics since the early 1960s, with applications in structure elucidation and elsewhere. In order to perform such a generation effi...
详细信息
The generation of constitutional isomer chemical spaces has been a subject of cheminformatics since the early 1960s, with applications in structure elucidation and elsewhere. In order to perform such a generation efficiently, exhaustively and isomorphism-free, the structure generator needs to ensure the building of canonical graphs already during the generation step and not by subsequent filtering. Here we present MAYGEN, an open-source, pure-Java development of a constitutional isomer molecular generator. The principles of MAYGEN's architecture and algorithm are outlined and the software is benchmarked in single-threaded mode against the state-of-the-art, but closed-source solution MOLGEN, as well as against the best open-source solution PMG. Based on the benchmarking, MAYGEN is on average 47 times faster than PMG and on average three times slower than MOLGEN in performance.
We give a deterministic algorithm for computing a global minimum vertex cut in a vertex-weighted graph with n vertices and m edges in Ô(mn) time. We use Õ(·) and Ô· to hide log(n) and no(1) fa...
详细信息
ISBN:
(纸本)9798400715105
We give a deterministic algorithm for computing a global minimum vertex cut in a vertex-weighted graph with n vertices and m edges in Ô(mn) time. We use Õ(·) and Ô· to hide log(n) and no(1) factors, respectively. This breaks the long-standing Ω(n4)-time barrier in dense graphs, achievable by trivially computing all-pairs maximum flows. Up to subpolynomial factors, we match the fastest randomized Õ(mn)-time algorithm by [Henzinger, Rao and Gabow FOCS’96], and affirmatively answer the question by [Gabow FOCS’00] whether deterministic O(mn)-time algorithms exist even for unweighted graphs. Our algorithm works in directed graphs, *** unweighted undirected graphs, we present a faster deterministic Ô(mκ)-time algorithm where κ≤ n is the size of the global minimum vertex cut. For a moderate value of κ, this strictly improves upon all previous deterministic algorithms in unweighted graphs with running time Ô(m(n+κ2)) [Even’75], Ô(m(n+κ√n)) [Gabow FOCS’00], and Ô(m2O(κ2)) [Saranurak and Yingchareonthawornchai FOCS’22]. Recently, a linear-time algorithm has been shown by [Korhonen’24] for small κ.Our approach applies the common-neighborhood clustering, recently introduced by [Blikstad, Jiang, Mukhopadhyay and Yingchareonthawornchai STOC’25], in novel ways, e.g., on top of weighted graphs and on top of vertex-expander decomposition. We also exploit pseudorandom objects often used in computational complexity communities, including crossing families based on dispersers from [TaShma, Umans and Zuckerman STOC’01, Wigderson and Zuckerman Combinatorica’99] and selectors based on linear lossless condensers [Cheraghchi’11, Guruswami, Umans and Vadhan JACM’09]. To our knowledge, this is the first application of selectors in graph algorithms.
A recent breakthrough by [LNPSY STOC’21] showed that solving s-t vertex connectivity is sufficient (up to polylogarithmic factors) to solve (global) vertex connectivity in the sequential model. This raises a natural ...
详细信息
ISBN:
(纸本)9798400715105
A recent breakthrough by [LNPSY STOC’21] showed that solving s-t vertex connectivity is sufficient (up to polylogarithmic factors) to solve (global) vertex connectivity in the sequential model. This raises a natural question: What is the relationship between s-t and global vertex connectivity in other computational models? In this paper, we demonstrate that the connection between global and s-t variants behaves very differently across computational *** parallel and distributed models, we obtain almost tight reductions from global to s-t vertex connectivity. In PRAM, this leads to a nω+o(1)-work and no(1)-depth algorithm for vertex connectivity, improving over the 35-year-old Õ(nω+1)-work O(log2n)-depth algorithm by [LLW FOCS’86], where ω is the matrix multiplication exponent and n is the number of vertices. In CONGEST, the reduction implies the first sublinear-round vertex connectivity algorithm when the diameter is moderately small. This answers an open question in [JM STOC’23].In contrast, we show that global vertex connectivity is strictly harder than s-t vertex connectivity in the two-party communication setting, requiring n1.5 bits of communication. The s-t variant was known to be solvable in Õ(n) communication [BvdBEMN FOCS’22]. Our results resolve open problems raised by [MN STOC’20, BvdBEMN FOCS’22, AS SOSA’23].At the heart of our results is a new graph decomposition framework we call common-neighborhood clustering, which can be applied in multiple models. Finally, we observe that global vertex connectivity cannot be solved without using s-t vertex connectivity by proving an s-t to global reduction in dense graphs in the PRAM and communication models.
The vertex connectivity of an m-edge n-vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In this paper, we give a reduction from the ver...
详细信息
ISBN:
(纸本)9781450380539
The vertex connectivity of an m-edge n-vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In this paper, we give a reduction from the vertex connectivity problem to a set of maxflow instances. Using this reduction, we can solve vertex connectivity in (O) over tilde (m(alpha)) time for any alpha >= 1, if there is a m(alpha)-time maxflow algorithm. Using the current best maxflow algorithm that runs in m(4/3+o(1)) time (Kathuria, Liu and Sidford, FOCS 2020), this yields a m(4/3+o(1) )- time vertex connectivity algorithm. This is the first improvement in the running time of the vertex connectivity problem in over 20 years, the previous best being an (O) over tilde (mn)-time algorithm due to Henzinger, Rao, and Gabow (FOCS 1996). Indeed, no algorithm with an o(mn) running time was known before our work, even if we assume an (O) over tilde (m)-time maxflow algorithm. Our new technique is robust enough to also improve the best (O) over tilde (mn)-time bound for directed vertex connectivity to mn(1-1/12+o(1)) time.
The SURJECTIVE H-COLOURING problem is to test if a given graph allows a vertex-SURJECTIVE homomorphism to a fixed graph H. The complexity of this problem has been well studied for undirected (partially) reflexive grap...
详细信息
The SURJECTIVE H-COLOURING problem is to test if a given graph allows a vertex-SURJECTIVE homomorphism to a fixed graph H. The complexity of this problem has been well studied for undirected (partially) reflexive graphs. We introduce endo-triviality, the property of a structure that all of its endomorphisms that do not have range of size 1 are automorphisms, as a means to obtain complexity-theoretic classifications of SURJECTIVE H-COLOURING in the case of reflexive digraphs. Chen (2014) proved, in the setting of constraint satisfaction problems, that SURJECTIVE H-COLOURING is NP-complete if H has the property that all of its polymorphisms are essentially unary. We give the first concrete application of his result by showing that every endo-trivial reflexive digraph H has this property. We then use the concept of endo-triviality to prove, as our main result, a dichotomy for SURJECTIVE H-COLOURING when H is a reflexive tournament: if H is transitive, then SURJECTIVE H-COLOURING is in NL;otherwise, it is NP-complete. By combining this result with some known and new results, we obtain a complexity classification for SURJECTIVE H-COLOURING when H is a partially reflexive digraph of size at most 3.
暂无评论