Search

The concept of standard basis for a module is generalized to that for a mixed module that can be written as sums of more than one modules over different rings. An algorithm to compute a standard basis for a mixed module is presented, along with a proof of its correctness and termination in finite steps. The algorithm is demonstrated in several examples appearing in computations of codimensions of divergent diagrams. A parametric extension of the standard basis (comprehensive standard system, CSS) for a mixed-module is also presented, along with a proof of its correctness and termination in finite steps and its computational algorithms. The algorithm is demonstrated in several examples in the classification of divergent diagrams including applications of Mather's lemma and the complete transversal theorem. [ABSTRACT FROM AUTHOR]

The fuzzy concept lattice is one of the effective tools for data mining, and granular reduction is one of its significant research contents. However, little research has been done on granular reduction at different granularities in formal fuzzy contexts (FFCs). Furthermore, the complexity of the composition of the fuzzy concept lattice limits the interest in its research. Therefore, how to simplify the concept lattice structure and how to construct granular reduction methods with granularity have become urgent issues that need to be investigated. To this end, firstly, the concept of an object granule with granularity is defined. Secondly, two reduction algorithms, one based on Boolean reasoning and the other on a graph-theoretic heuristic, are formulated while keeping the structure of this object granule unchanged. Further, to simplify the structure of the fuzzy concept lattice, a partial order relation with parameters is proposed. Finally, the feasibility and effectiveness of our proposed reduction approaches are verified by data experiments. [ABSTRACT FROM AUTHOR]

Nowadays, the application of artificial intelligence (AI) algorithms and techniques is ubiquitous and transversal. Fields that take advantage of AI advances include sound and music processing. The advances in interdisciplinary research potentially yield new insights that may further advance the AI methods in this field. This special issue aims to report recent progress and spur new research lines in AI-driven sound and music processing, especially within interdisciplinary research scenarios. [ABSTRACT FROM AUTHOR]

The clique transversal problem is a critical concept in graph theory, focused on identifying a minimum subset of vertices that intersects all maximal cliques in a graph. This problem and its variations—such as the k-fold clique, { k } -clique, minus clique, and signed clique transversal problems—have received significant interest due to their theoretical importance and practical applications. This paper examines the k-fold clique, { k } -clique, minus clique, and signed clique transversal problems on distance-hereditary graphs. Known for their distinctive structural properties, distance hereditary graphs provide an ideal framework for studying these problem variants. By exploring these issues in the context of distance-hereditary graphs, this research enhances the understanding of the computational challenges and the potential for developing efficient algorithms to address these problems. [ABSTRACT FROM AUTHOR]

The Lovász local lemma (LLL) is a keystone principle in probability theory, guaranteeing the existence of configurations which avoid a collection ℬ$$ \mathcal{B} $$ of "bad" events which are mostly independent and have low probability. A seminal algorithm of Moser and Tardos (J. ACM, 2010, 57, 11) (which we call the MT algorithm) gives nearly‐automatic randomized algorithms for most constructions based on the LLL. However, deterministic algorithms have lagged behind. We address three specific shortcomings of the prior deterministic algorithms. First, our algorithm applies to the LLL criterion of Shearer (Combinatorica, 1985, 5, 241–245); this is more powerful than alternate LLL criteria and also leads to cleaner and more legible bounds. Second, we provide parallel algorithms with much greater flexibility. Third, we provide a derandomized version of the MT‐distribution, that is, the distribution of the variables at the termination of the MT algorithm. We show applications to non‐repetitive vertex coloring, independent transversals, strong coloring, and other problems. [ABSTRACT FROM AUTHOR]

In this paper we present an incremental algorithm for computing the transversal hypergraph. Our algorithm is an optimized version of Berge's algorithm [2] for solving the transversal hypergraph problem. The original algorithm of Berge is the simplest and most direct scheme for generating all minimal transversals of a hypergraph. Here we present an optimized version of Berge's algorithm that we call BergeOpt. We show that BergeOpt can significantly reduce the number of expensive inclusion tests. [ABSTRACT FROM AUTHOR]

In this paper, a new combinatorial structure is introduced for image encryption, which has an excellent encryption effect on security and efficiency. An n-transversal in a Latin square has the function of classifying all the matrix's positions, and it can provide a pair of orthogonal Latin squares. Employing an n-transversal of a Latin square, we can permutate all the pixels of an image group by group for the first time, then use two Latin squares for auxiliary diffusion based on a chaotic sequence, and finally, make use of a pair of orthogonal Latin squares to perform the second scrambling. The whole encryption process is "scrambling–diffusion–scrambling". The experimental results indicated that this algorithm passed various tests and achieved a secure and fast encryption effect, which outperformed many of the latest papers. The final information entropy was very close to 8, and the correlation coefficient was approximately 0. All these tests verified the robustness and practicability of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. In particular, we prove that for every s \geq 1, both problems are polynomial-time solvable for sP3-free graphs and (sP1 + P5)-free graphs; here, the graph sP3 denotes the disjoint union of s paths on three vertices and the graph sP1 + P5 denotes the disjoint union of s isolated vertices and a path on five vertices. Our new results for Feedback Vertex Set extend all known polynomial-time results for Feedback Vertex Set on H-free graphs, namely for sP2-free graphs [Chiarelli et al., Theoret. Comput. Sci., 705 (2018), pp. 75--83], (sP1+P3)-free graphs [Dabrowski et al., Algorithmica, 82 (2020), pp. 2841--2866] and P5-free graphs [Abrishami et al., Induced subgraphs of bounded treewidth and the container method, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2021, pp. 1948--1964]. Together, the new results also show that both problems exhibit the same behavior on H-free graphs (subject to some open cases). This is in part due to a new general algorithm we design for finding in a (sP3)-free or (sP1 + P5)-free graph G a largest induced subgraph whose blocks belong to some finite class \scrC of graphs. We also compare our results with the state-of-the-art results for the Odd Cycle Transversal problem, which is known to behave differently on H-free graphs. [ABSTRACT FROM AUTHOR]

The Independent Cutset problem asks whether there is a set of vertices in a given graph that is both independent and a cutset. This problem is ▪-complete even when the input graph is planar and has maximum degree five. We first present a O ⁎ (1.4423 n) -time algorithm to compute a minimum independent cutset (if any). Since the property of having an independent cutset is MSO 1 -expressible, our main results are concerned with structural parameterizations for the problem considering parameters incomparable with clique-width. We present ▪-time algorithms under the following parameters: the dual of the maximum degree, the dual of the solution size, the size of a dominating set (where a dominating set is given as an additional input), the size of an odd cycle transversal, the distance to chordal graphs, and the distance to P 5 -free graphs. We close by introducing the notion of α -domination, which generalizes key ideas of this article. [ABSTRACT FROM AUTHOR]

The transversal hypergraph problem asks to enumerate the minimal hitting sets of a hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP'95] gave an algorithm running in output-polynomial time, but whose space requirement also scales with the output. We improve this to polynomial delay and space. Central to our approach is the extension problem, deciding for a set X of vertices whether it is contained in any minimal hitting set. We show that this is one of the first natural problems to be W [ 3 ] -complete. We give an algorithm for the extension problem running in time O (m | X | + 1 n) and prove a SETH-lower bound showing that this is close to optimal. We apply our enumeration method to the discovery problem of minimal unique column combinations from data profiling. Our empirical evaluation suggests that the algorithm outperforms its worst-case guarantees on hypergraphs stemming from real-world databases. [ABSTRACT FROM AUTHOR]

An independent transversal (IT) in a graph with a given vertex partition is an independent set consisting of one vertex in each partition class. Several sufficient conditions are known for the existence of an IT in a given graph and vertex partition, which have been used over the years to solve many combinatorial problems. Some of these IT existence theorems have algorithmic proofs, but there remains a gap between the best existential bounds and the bounds obtainable by efficient algorithms. Recently, Graf and Haxell (2018) described a new (deterministic) algorithm that asymptotically closes this gap, but there are limitations on its applicability. In this article, we develop a randomized algorithm that is much more widely applicable, and demonstrate its use by giving efficient algorithms for two problems concerning the strong chromatic number of graphs. [ABSTRACT FROM AUTHOR]

A dominating set D of a graph G is a set of vertices such that any vertex in G is in D or its neighbor is in D. Enumeration of minimal dominating sets in a graph is one of the central problems in enumeration study since enumeration of minimal dominating sets corresponds to the enumeration of minimal hypergraph transversals. The output-polynomial time enumeration of minimal hypergraph transversals is an interesting open problem. On the other hand, enumeration of dominating sets including non-minimal ones has not been received much attention. In this paper, we address enumeration problems for dominating sets from sparse graphs which are degenerate graphs and graphs with large girth, and we propose two algorithms for solving the problems. The first algorithm enumerates all the dominating sets for a k -degenerate graph in O k time per solution using O n + m space, where n and m are respectively the number of vertices and edges in an input graph. That is, the algorithm is optimal for graphs with constant degeneracy such as trees, planar graphs, H -minor free graphs with some fixed H. The second algorithm enumerates all the dominating sets in constant time per solution for input graphs with girth at least nine. [ABSTRACT FROM AUTHOR]

We study the Max Partial $H$-Coloring problem: given a graph $G$, find the largest induced subgraph of $G$ that admits a homomorphism into $H$, where $H$ is a fixed pattern graph without loops. Note that when $H$ is a complete graph on $k$ vertices, the problem reduces to finding the largest induced $k$-colorable subgraph, which for $k=2$ is equivalent (by complementation) to Odd Cycle Transversal. We prove that for every fixed pattern graph $H$ without loops, Max Partial $H$-Coloring can be solved in $\{P_5,F\}$-free graphs in polynomial time, whenever $F$ is a threshold graph; in $\{P_5,{bull}\}$-free graphs in polynomial time; in $P_5$-free graphs in time $n^{\mathcal{O}(\omega(G))}$; and in $\{P_6,{1-subdivided claw}\}$-free graphs in time $n^{\mathcal{O}(\omega(G)^3)}$. Here, $n$ is the number of vertices of the input graph $G$ and $\omega(G)$ is the maximum size of a clique in $G$. Furthermore, by combining the mentioned algorithms for $P_5$-free and for $\{P_6,{1-subdivided claw}\}$-free graphs with a simple branching procedure, we obtain subexponential-time algorithms for Max Partial $H$-Coloring in these classes of graphs. Finally, we show that even a restricted variant of Max Partial $H$-Coloring is $\mathsf{NP}$-hard in the considered subclasses of $P_5$-free graphs if we allow loops on $H$. [ABSTRACT FROM AUTHOR]

In this paper, we study the dualization in distributive lattices, a generalization of the well-known hypergraph dualization problem. We in particular propose equivalent formulations of the problem in terms of graphs, hypergraphs, and posets. It is known that hypergraph dualization amounts to generate all minimal transversals of a hypergraph, or all minimal dominating sets of a graph. In this new framework, a poset on vertices is given together with the input (hyper)graph, and minimal "ideal solutions" are to be generated. This in particular allows us to study the complexity of the problem under various combined restrictions on graph classes and poset types, including bipartite, split, and co-bipartite graphs, and variants of neighborhood inclusion posets. For example, we show that while the enumeration of minimal dominating sets is possible with linear delay in split graphs, the problem, within the same class, gets as hard as for general graphs when generalized to this framework. More surprisingly, this result holds even when the poset is only comparing vertices with included neighborhoods in the graph. If both the poset and the graph class are sufficiently restricted, we show that the dualization is tractable relying on existing algorithms from the literature. [ABSTRACT FROM AUTHOR]

A class domination coloring (also called cd-Coloring or dominated coloring) of a graph is a proper coloring in which every color class is contained in the neighborhood of some vertex. The minimum number of colors required for any cd-coloring of G , denoted by χ c d (G) , is called the class domination chromatic number (cd-chromatic number) of G. In this work, we consider two problems associated with the cd-coloring of a graph in the context of exact exponential-time algorithms and parameterized complexity. (1) Given a graph G on n vertices, find its cd-chromatic number. (2) Given a graph G and integers k and q , can we delete at most k vertices such that the cd-chromatic number of the resulting graph is at most q ? For the first problem, we give an exact algorithm with running time O (2 n n 4 log n). Also, we show that the problem is FPT with respect to the number q of colors as the parameter on chordal graphs. On graphs of girth at least 5, we show that the problem also admits a kernel with O (q 3) vertices. For the second (deletion) problem, we show NP -hardness for each q ≥ 2. Further, on split graphs, we show that the problem is NP -hard if q is a part of the input and FPT with respect to k and q as combined parameters. As recognizing graphs with cd-chromatic number at most q is NP -hard in general for q ≥ 4 , the deletion problem is unlikely to be FPT when parameterized by the size of the deletion set on general graphs. We show fixed parameter tractability for q ∈ { 2 , 3 } using the known algorithms for finding a vertex cover and an odd cycle transversal as subroutines. • An exact algorithm that runs in time O (2 n n 4 log n). • An FPT algorithm parameterized by the number of colors and the treewidth. • FPT algorithms when input graph is restricted to special graph classes. • 3 - cd-Coloring is FPT parameterized by the solution size. [ABSTRACT FROM AUTHOR]

The Lovász local lemma (LLL) is a probabilistic tool to generate combinatorial structures with good "local" properties. The "LLL‐distribution" further shows that these structures have good global properties in expectation. The seminal algorithm of Moser and Tardos turned the simplest, variable‐based form of the LLL into an efficient algorithm; this has since been extended to other probability spaces including random permutations. One can similarly define an "MT‐distribution" for these algorithms, that is, the distribution of the configuration they produce. We show new bounds on the MT‐distribution in the variable and permutation settings which are significantly stronger than those known to hold for the LLL‐distribution. As some example illustrations, we show a nearly tight bound on the minimum implicate size of a CNF Boolean formula, and we obtain improved bounds on weighted Latin transversals and partial Latin transversals. [ABSTRACT FROM AUTHOR]

We study the problem, given a hypergraph H , how to generate its transversal (or dual) hypergraph G , using tools from Boolean resolution. We show how to compute the residual dual of H given a subset E of its minimal transversals. This is the hypergraph whose minimal transversals are exactly those missing from E to become the dual of H. We give a novel algorithm for the problem based on the notion of subtransversal. Though its complexity is superpolynomial, it gives new insight to the problem of hypergraph duality. Another variant of the algorithm seems also promising to efficiently test hypergraph duality in practice. [ABSTRACT FROM AUTHOR]

In the Graph bipartization (or Odd Cycle Transversal) problem, the objective is to decide whether a given graph G can be made bipartite by the deletion of k vertices for some given k. The parameterized complexity of Odd Cycle Transversal was resolved in the breakthrough paper of Reed, Smith and Vetta [Operations Research Letters, 2004], who developed an algorithm running in time O (3 k k m n). The question of improving the dependence on the input size to linear, which was another long standing open problem in the area, was resolved by Iwata et al. [SICOMP 2016] and Ramanujan and Saurabh [TALG 2017], who presented O (4 k (m + n)) and 4 k k O (1) (m + n) algorithms respectively. In this paper, we obtain a faster algorithm that runs in time 3 k k O (1) (m + n) and hence preserves the linear dependence on the input size while nearly matching the dependence on k incurred by the algorithm of Reed, Smith and Vetta. [ABSTRACT FROM AUTHOR]

Abstract We consider the problem of enumerating all minimal hitting sets of a given hypergraph (V , R) , where V is a finite set, called the vertex set and R is a set of subsets of V called the hyperedges. We show that, when the hypergraph admits a balanced subdivision , then a recursive decomposition can be used to obtain efficiently all minimal hitting sets of the hypergraph. We apply this decomposition framework to get incremental polynomial-time algorithms for finding minimal hitting sets and minimal set covers for a number of hypergraphs induced by a set of points and a set of geometric objects. The set of geometric objects includes half-spaces, hyper-rectangles and balls, in fixed dimension. A distinguishing feature of the algorithms we obtain is that they admit an efficient global parallel implementation, in the sense that all minimal hitting sets can be generated in polylogarithmic time in | V | , | R | and the total number of minimal transversals M , using a polynomial number of processors. For half-spaces in R 2 , we show that the above two enumeration problems can be solved, using a different technique, with amortized polynomial delay. [ABSTRACT FROM AUTHOR]

Streaming is a model where an input graph is provided one edge at a time, instead of being able to inspect it at will. In this work, we take a parameterized approach by assuming a vertex cover of the graph is given, building on work of Bishnu et al. [COCOON 2020]. We show the further potency of combining this parameter with the Adjacency List streaming model to obtain results for vertex deletion problems. This includes kernels, parameterized algorithms, and lower bounds for the problems of Π -free Deletion , H -free Deletion , and the more specific forms of Cluster Vertex Deletion and Odd Cycle Transversal. We focus on the complexity in terms of the number of passes over the input stream, and the memory used. This leads to a pass/memory trade-off, where a different algorithm might be favourable depending on the context and instance. We also discuss implications for parameterized complexity in the non-streaming setting. [ABSTRACT FROM AUTHOR]

The aim of this paper is to compute all the Frenet apparatus of non-transversal intersection curves (hyper-curves) of three implicit hypersurfaces in Euclidean 4-space. The tangential direction at a transversal intersection point can be computed easily, but at a non-transversal intersection point, it is difficult to calculate even the tangent vector. If three normal vectors are parallel at a point, the intersection is “tangential intersection”; and if three normal vectors are not parallel but are linearly dependent at a point, we have “almost tangential” intersection at the intersection point. We give algorithms for each case to find the Frenet vectors ( t , n , b 1 , b 2 ) and the curvatures ( k 1 , k 2 , k 3 ) of the non-transversal intersection curve. [ABSTRACT FROM AUTHOR]

In this paper, we study some average properties of hypergraphs and the average complexity of algorithms applied to hypergraphs under different probabilistic models. Our approach is both theoretical and experimental since our goal is to obtain a random model that is able to capture the real-data complexity. Starting from a model that generalizes the Erdös–Renyi model [10,11] , we obtain asymptotic estimations on the average number of transversals, irredundants and minimal transversals in a random hypergraph. We use those results to obtain an upper bound on the average complexity of algorithms to generate the minimal transversals of a hypergraph. Then we make our random model more complex in order to bring it closer to real-data and identify cases where the average number of minimal transversals is at most polynomial, quasi-polynomial or exponential. [ABSTRACT FROM AUTHOR]

We develop an algorithm for the efficient and stable simulation of large-scale elastic rod assemblies. We observe that the time-integration step is severely restricted by a strong nonlinearity in the response of stretching modes to transversal impact, the degree of this nonlinearity varying greatly with the shape of the rod. Building on these observations, we propose a collision response algorithm that adapts its degree of nonlinearity. We illustrate the advantages of the resulting algorithm by analyzing simulations involving elastic rod assemblies of varying density and scale, with up to 1.7 million individual contacts per time step. [ABSTRACT FROM AUTHOR]

The BIPARTITE CONTRACTION problem takes as input an n-vertex graph G and an integer κ, and the task is to determine whether we can obtain a bipartite graph from G by a sequence of at most κ edge contractions. We show that BIPARTITE CONTRACTION is fixed-parameter tractable when parameterized by κ. Despite a strong resemblance between Bipartite Contraction and the classical ODD CYCLE TRANSVERSAL (OCT) problem, the methods developed to tackle OCT do not seem to be directly applicable to BIPARTITE CONTRACTION. To obtain our result, we combine several techniques and concepts that are central in parameterized complexity: iterative compression, irrelevant vertices, and important separators. To the best of our knowledge, this is the first time the irrelevant vertex technique and the concept of important separators are applied in unison. Furthermore, our algorithm may serve as a comprehensible example of the usage of the irrelevant vertex technique. [ABSTRACT FROM AUTHOR]

The concept of q-rung orthopair fuzzy sets generalizes the notions of intuitionistic fuzzy sets and Pythagorean fuzzy sets to describe complicated uncertain information more effectively. Their most dominant attribute is that the sum of the q th power of the truth-membership and the q th power of the falsity-membership must be equal to or less than one, so they can broaden the space of uncertain data. This set can adjust the range of indication of decision data by changing the parameter q, q ≥ 1 . In this research study, we design a new framework for handling uncertain data by means of the combinative theory of q-rung orthopair fuzzy sets and hypergraphs. We define q-rung orthopair fuzzy hypergraphs to achieve the advantages of both theories. Further, we propose certain novel concepts, including adjacent levels of q-rung orthopair fuzzy hypergraphs, (α , β) -level hypergraphs, transversals, and minimal transversals of q-rung orthopair fuzzy hypergraphs. We present a brief comparison of our proposed model with other existing theories. Moreover, we implement some interesting concepts of q-rung orthopair fuzzy hypergraphs for decision-making to prove the effectiveness of our proposed model. [ABSTRACT FROM AUTHOR]