Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCounting Minimal Transversals of $beta$-Acyclic Hypergraphs
183
0
0.0
(
0
)
Added by
Benjamin Bergougnoux
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We prove that one can count in polynomial time the number of minimal transversals of $beta$-acyclic hypergraphs. In consequence, we can count in polynomial time the number of minimal dominating sets of strongly chordal graphs, continuing the line of research initiated in [M.M. Kante and T. Uno, Counting Minimal Dominating Sets, TAMC17].
rate research
Read More
We bound the number of minimal hypergraph transversals that arise in tri-partite 3-uniform hypergraphs, a class commonly found in applications dealing with data. Let H be such a hypergraph on a set of vertices V. We give a lower bound of 1.4977 |V | and an upper bound of 1.5012 |V | .
We study the size of certain acyclic domains that arise from geometric and combinatorial constructions. These acyclic domains consist of all permutations visited by commuting equivalence classes of maximal reduced decompositions if we consider the symmetric group and, more generally, of all c-singletons of a Cambrian lattice associated to the weak order of a finite Coxeter group. For this reason, we call these sets Cambrian acyclic domains. Extending a closed formula of Galambos--Reiner for a particular acyclic domain called Fishburns alternating scheme, we provide explicit formulae for the size of any Cambrian acyclic domain and characterize the Cambrian acyclic domains of minimum or maximum size.
We study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to $H$-free graphs, that is, to graphs that do not contain some fixed graph~$H$ as an induced subgraph. By combining known and new results, we determine the computational complexity of both problems on $H$-free graphs for every graph $H$ except when $H=sP_1+P_4$ for some $sgeq 1$. As part of our approach, we introduce the Subset Vertex Cover problem and prove that it is polynomial-time solvable for $(sP_1+P_4)$-free graphs for every $sgeq 1$.
A tight Hamilton cycle in a $k$-uniform hypergraph ($k$-graph) $G$ is a cyclic ordering of the vertices of $G$ such that every set of $k$ consecutive vertices in the ordering forms an edge. R{o}dl, Ruci{n}ski, and Szemer{e}di proved that for $kgeq 3$, every $k$-graph on $n$ vertices with minimum codegree at least $n/2+o(n)$ contains a tight Hamilton cycle. We show that the number of tight Hamilton cycles in such $k$-graphs is $exp(nln n-Theta(n))$. As a corollary, we obtain a similar estimate on the number of Hamilton $ell$-cycles in such $k$-graphs for all $ellin{0,dots,k-1}$, which makes progress on a question of Ferber, Krivelevich and Sudakov.
The Minimum Path Cover problem on directed acyclic graphs (DAGs) is a classical problem that provides a clear and simple mathematical formulation for several applications in different areas and that has an efficient algorithmic solution. In this paper, we study the computational complexity of two constrained variants of Minimum Path Cover motivated by the recent introduction of next-generation sequencing technologies in bioinformatics. The first problem (MinPCRP), given a DAG and a set of pairs of vertices, asks for a minimum cardinality set of paths covering all the vertices such that both vertices of each pair belong to the same path. For this problem, we show that, while it is NP-hard to compute if there exists a solution consisting of at most three paths, it is possible to decide in polynomial time whether a solution consisting of at most two paths exists. The second problem (MaxRPSP), given a DAG and a set of pairs of vertices, asks for a path containing the maximum number of the given pairs of vertices. We show its NP-hardness and also its W[1]-hardness when parametrized by the number of covered pairs. On the positive side, we give a fixed-parameter algorithm when the parameter is the maximum overlapping degree, a natural parameter in the bioinformatics applications of the problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
