-
Enumeration of minimal transversals of hypergraphs of bounded VC-dimension
Authors:
Arnaud Mary
Abstract:
We consider the problem of enumerating all minimal transversals (also called minimal hitting sets) of a hypergraph $\mathcal{H}$. An equivalent formulation of this problem known as the \emph{transversal hypergraph} problem (or \emph{hypergraph dualization} problem) is to decide, given two hypergraphs, whether one corresponds to the set of minimal transversals of the other. The existence of a polyn…
▽ More
We consider the problem of enumerating all minimal transversals (also called minimal hitting sets) of a hypergraph $\mathcal{H}$. An equivalent formulation of this problem known as the \emph{transversal hypergraph} problem (or \emph{hypergraph dualization} problem) is to decide, given two hypergraphs, whether one corresponds to the set of minimal transversals of the other. The existence of a polynomial time algorithm to solve this problem is a long standing open question. In \cite{fredman_complexity_1996}, the authors present the first sub-exponential algorithm to solve the transversal hypergraph problem which runs in quasi-polynomial time, making it unlikely that the problem is (co)NP-complete.
In this paper, we show that when one of the two hypergraphs is of bounded VC-dimension, the transversal hypergraph problem can be solved in polynomial time, or equivalently that if $\mathcal{H}$ is a hypergraph of bounded VC-dimension, then there exists an incremental polynomial time algorithm to enumerate its minimal transversals. This result generalizes most of the previously known polynomial cases in the literature since they almost all consider classes of hypergraphs of bounded VC-dimension. As a consequence, the hypergraph transversal problem is solvable in polynomial time for any class of hypergraphs closed under partial subhypergraphs. We also show that the proposed algorithm runs in quasi-polynomial time in general hypergraphs and runs in polynomial time if the conformality of the hypergraph is bounded, which is one of the few known polynomial cases where the VC-dimension is unbounded.
△ Less
Submitted 3 July, 2024; v1 submitted 30 June, 2024;
originally announced July 2024.
-
Reconfiguration of graphs with connectivity constraints
Authors:
Nicolas Bousquet,
Arnaud Mary
Abstract:
A graph $G$ realizes the degree sequence $S$ if the degrees of its vertices is $S$. Hakimi gave a necessary and sufficient condition to guarantee that there exists a connected multigraph realizing $S$. Taylor later proved that any connected multigraph can be transformed into any other via a sequence of flips (maintaining connectivity at any step). A flip consists in replacing two edges $ab$ and…
▽ More
A graph $G$ realizes the degree sequence $S$ if the degrees of its vertices is $S$. Hakimi gave a necessary and sufficient condition to guarantee that there exists a connected multigraph realizing $S$. Taylor later proved that any connected multigraph can be transformed into any other via a sequence of flips (maintaining connectivity at any step). A flip consists in replacing two edges $ab$ and $cd$ by the diagonals $ac$ and $bd$. In this paper, we study a generalization of this problem. A set of subsets of vertices $\mathcal{CC}$ is \emph{nested} if for every $C,C' \in \mathcal{CC}$ either $C \cap C' = \emptyset$ or one is included in the other. We are interested in multigraphs realizing a degree sequence $S$ and such that all the sets of a nested collection $\mathcal{CC}$ induce connected subgraphs. Such constraints naturally appear in tandem mass spectrometry.
We show that it is possible to decide in polynomial if there exists a graph realizing $S$ where all the sets in $\mathcal{CC}$ induce connected subgraphs. Moreover, we prove that all such graphs can be obtained via a sequence of flips such that all the intermediate graphs also realize $S$ and where all the sets of $\mathcal{CC}$ induce connected subgraphs. Our proof is algorithmic and provides a polynomial time approximation algorithm on the shortest sequence of flips between two graphs whose ratio depends on the depth of the nested partition.
△ Less
Submitted 14 September, 2018;
originally announced September 2018.
-
Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension
Authors:
Laurent Beaudou,
Florent Foucaud,
Peter Dankelmann,
Michael A. Henning,
Arnaud Mary,
Aline Parreau
Abstract:
The metric dimension of a graph is the minimum size of a set of vertices such that each vertex is uniquely determined by the distances to the vertices of that set. Our aim is to upper-bound the order $n$ of a graph in terms of its diameter $d$ and metric dimension $k$. In general, the bound $n\leq d^k+k$ is known to hold. We prove a bound of the form $n=\mathcal{O}(kd^2)$ for trees and outerplanar…
▽ More
The metric dimension of a graph is the minimum size of a set of vertices such that each vertex is uniquely determined by the distances to the vertices of that set. Our aim is to upper-bound the order $n$ of a graph in terms of its diameter $d$ and metric dimension $k$. In general, the bound $n\leq d^k+k$ is known to hold. We prove a bound of the form $n=\mathcal{O}(kd^2)$ for trees and outerplanar graphs (for trees we determine the best possible bound and the corresponding extremal examples). More generally, for graphs having a tree decomposition of width $w$ and length $\ell$, we obtain a bound of the form $n=\mathcal{O}(kd^2(2\ell+1)^{3w+1})$. This implies in particular that $n=\mathcal{O}(kd^{\mathcal{O}(1)})$ for graphs of constant treewidth and $n=\mathcal{O}(f(k)d^2)$ for chordal graphs, where $f$ is a doubly-exponential function. Using the notion of distance-VC dimension (introduced in 2014 by Bousquet and Thomassé) as a tool, we prove the bounds $n\leq (dk+1)^{t-1}+1$ for $K_t$-minor-free graphs, and $n\leq (dk+1)^{d(3\cdot 2^{r}+2)}+1$ for graphs of rankwidth at most $r$.
△ Less
Submitted 20 July, 2018; v1 submitted 5 October, 2016;
originally announced October 2016.
-
On the Enumeration of Minimal Dominating Sets and Related Notions
Authors:
Mamadou Moustapha Kanté,
Vincent Limouzy,
Arnaud Mary,
Lhouari Nourine
Abstract:
A dominating set $D$ in a graph is a subset of its vertex set such that each vertex is either in $D$ or has a neighbour in $D$. In this paper, we are interested in the enumeration of (inclusion-wise) minimal dominating sets in graphs, called the Dom-Enum problem. It is well known that this problem can be polynomially reduced to the Trans-Enum problem in hypergraphs, i.e., the problem of enumeratin…
▽ More
A dominating set $D$ in a graph is a subset of its vertex set such that each vertex is either in $D$ or has a neighbour in $D$. In this paper, we are interested in the enumeration of (inclusion-wise) minimal dominating sets in graphs, called the Dom-Enum problem. It is well known that this problem can be polynomially reduced to the Trans-Enum problem in hypergraphs, i.e., the problem of enumerating all minimal transversals in a hypergraph. Firstly we show that the Trans-Enum problem can be polynomially reduced to the Dom-Enum problem. As a consequence there exists an output-polynomial time algorithm for the Trans-Enum problem if and only if there exists one for the Dom-Enum problem. Secondly, we study the Dom-Enum problem in some graph classes. We give an output-polynomial time algorithm for the Dom-Enum problem in split graphs, and introduce the completion of a graph to obtain an output-polynomial time algorithm for the Dom-Enum problem in $P_6$-free chordal graphs, a proper superclass of split graphs. Finally, we investigate the complexity of the enumeration of (inclusion-wise) minimal connected dominating sets and minimal total dominating sets of graphs. We show that there exists an output-polynomial time algorithm for the Dom-Enum problem (or equivalently Trans-Enum problem) if and only if there exists one for the following enumeration problems: minimal total dominating sets, minimal total dominating sets in split graphs, minimal connected dominating sets in split graphs, minimal dominating sets in co-bipartite graphs.
△ Less
Submitted 8 July, 2014;
originally announced July 2014.
