Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPartitions versus sets : a case of duality
289
0
0.0
(
0
)
Added by
Frederic Mazoit
Publication date
2009
fields
Informatics Engineering
and research's language is
English
Authors
Laurent Lyaudet
Ask ChatGPT about the research
No Arabic abstract
In a recent paper, Amini et al. introduce a general framework to prove duality theorems between special decompositions and their dual combinatorial object. They thus unify all known ad-hoc proofs in one single theorem. While this unification process is definitely good, their main theorem remains quite technical and does not give a real insight of why some decompositions admit dual objects and why others do not. The goal of this paper is both to generalise a little this framework and to give an enlightening simple proof of its central theorem.
rate research
Read More
Motivated by recent computational models for redistricting and detection of gerrymandering, we study the following problem on graph partitions. Given a graph $G$ and an integer $kgeq 1$, a $k$-district map of $G$ is a partition of $V(G)$ into $k$ nonempty subsets, called districts, each of which induces a connected subgraph of $G$. A switch is an operation that modifies a $k$-district map by reassigning a subset of vertices from one district to an adjacent district; a 1-switch is a switch that moves a single vertex. We study the connectivity of the configuration space of all $k$-district maps of a graph $G$ under 1-switch operations. We give a combinatorial characterization for the connectedness of this space that can be tested efficiently. We prove that it is NP-complete to decide whether there exists a sequence of 1-switches that takes a given $k$-district map into another; and NP-hard to find the shortest such sequence (even if a sequence of polynomial length is known to exist). We also present efficient algorithms for computing a sequence of 1-switches that takes a given $k$-district map into another when the space is connected, and show that these algorithms perform a worst-case optimal number of switches up to constant factors.
Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph $G$. A partition of $V(G)$ is emph{connected} if every part induces a connected subgraph. In many applications, it is desirable to obtain parts of roughly the same size, possibly with some slack $s$. A emph{Balanced Connected $k$-Partition with slack $s$}, denoted emph{$(k,s)$-BCP}, is a partition of $V(G)$ into $k$ nonempty subsets, of sizes $n_1,ldots , n_k$ with $|n_i-n/k|leq s$, each of which induces a connected subgraph (when $s=0$, the $k$ parts are perfectly balanced, and we call it emph{$k$-BCP} for short). A emph{recombination} is an operation that takes a $(k,s)$-BCP of a graph $G$ and produces another by merging two adjacent subgraphs and repartitioning them. Given two $k$-BCPs, $A$ and $B$, of $G$ and a slack $sgeq 0$, we wish to determine whether there exists a sequence of recombinations that transform $A$ into $B$ via $(k,s)$-BCPs. We obtain four results related to this problem: (1) When $s$ is unbounded, the transformation is always possible using at most $6(k-1)$ recombinations. (2) If $G$ is Hamiltonian, the transformation is possible using $O(kn)$ recombinations for any $s ge n/k$, and (3) we provide negative instances for $s leq n/(3k)$. (4) We show that the problem is PSPACE-complete when $k in O(n^{varepsilon})$ and $s in O(n^{1-varepsilon})$, for any constant $0 < varepsilon le 1$, even for restricted settings such as when $G$ is an edge-maximal planar graph or when $k=3$ and $G$ is planar.
The question whether a partition $mathcal{P}$ and a hierarchy $mathcal{H}$ or a tree-like split system $mathfrak{S}$ are compatible naturally arises in a wide range of classification problems. In the setting of phylogenetic trees, one asks whether the sets of $mathcal{P}$ coincide with leaf sets of connected components obtained by deleting some edges from the tree $T$ that represents $mathcal{H}$ or $mathfrak{S}$, respectively. More generally, we ask whether a refinement $T^*$ of $T$ exists such that $T^*$ and $mathcal{P}$ are compatible. We report several characterizations for (refinements of) hierarchies and split systems that are compatible with (sets of) partitions. In addition, we provide a linear-time algorithm to check whether refinements of trees and a given partition are compatible. The latter problem becomes NP-complete but fixed-parameter tractable if a set of partitions is considered instead of a single partition. We finally explore the close relationship of the concept of compatibility and so-called Fitch maps.
We introduce the notion of specular sets which are subsets of groups called here specular and which form a natural generalization of free groups. These sets are an abstract generalization of the natural codings of linear involutions. We prove several results concerning the subgroups generated by return words and by maximal bifix codes in these sets.
Let $G$ be a graph(directed or undirected) having $k$ number of blocks. A $mathcal{B}$-partition of $G$ is a partition into $k$ vertex-disjoint subgraph $(hat{B_1},hat{B_1},hdots,hat{B_k})$ such that $hat{B}_i$ is induced subgraph of $B_i$ for $i=1,2,hdots,k.$ The terms $prod_{i=1}^{k}det(hat{B}_i), prod_{i=1}^{k}text{per}(hat{B}_i)$ are det-summands and per-summands, respectively, corresponding to the $mathcal{B}$-partition. The determinant and permanent of a graph having no loops on its cut-vertices is equal to summation of det-summands and per-summands, respectively, corresponding to all possible $mathcal{B}$-partitions. Thus, in this paper we calculate determinant and permanent of some graphs, which include block graph with negatives cliques, signed unicyclic graph, mix complete graph, negative mix complete graph, and star mix block graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
