Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Supergraphs Satisfying CMSO Properties
74
0
0.0
(
0
)
Added by
Mateus de Oliveira Oliveira
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Mateus de Oliveira Oliveira
Ask ChatGPT about the research
No Arabic abstract
Let CMSO denote the counting monadic second order logic of graphs. We give a constructive proof that for some computable function $f$, there is an algorithm $mathfrak{A}$ that takes as input a CMSO sentence $varphi$, a positive integer $t$, and a connected graph $G$ of maximum degree at most $Delta$, and determines, in time $f(|varphi|,t)cdot 2^{O(Delta cdot t)}cdot |G|^{O(t)}$, whether $G$ has a supergraph $G$ of treewidth at most $t$ such that $Gmodels varphi$. The algorithmic metatheorem described above sheds new light on certain unresolved questions within the framework of graph completion algorithms. In particular, using this metatheorem, we provide an explicit algorithm that determines, in time $f(d)cdot 2^{O(Delta cdot d)}cdot |G|^{O(d)}$, whether a connected graph of maximum degree $Delta$ has a planar supergraph of diameter at most $d$. Additionally, we show that for each fixed $k$, the problem of determining whether $G$ has an $k$-outerplanar supergraph of diameter at most $d$ is strongly uniformly fixed parameter tractable with respect to the parameter $d$. This result can be generalized in two directions. First, the diameter parameter can be replaced by any contraction-closed effectively CMSO-definable parameter $mathbf{p}$. Examples of such parameters are vertex-cover number, dominating number, and many other contraction-bidimensional parameters. In the second direction, the planarity requirement can be relaxed to bounded genus, and more generally, to bounded local treewidth.
rate research
Read More
We introduce the notion of z-topological orderings for digraphs. We prove that given a digraph G on n vertices admitting a z-topological order- ing, together with such an ordering, one may count the number of subgraphs of G that at the same time satisfy a monadic second order formula {phi} and are the union of k directed paths, in time f ({phi}, k, z) * n^O(k*z) . Our result implies the polynomial time solvability of many natural counting problems on digraphs admitting z-topological orderings for constant values of z and k. Concerning the relationship between z-topological orderability and other digraph width measures, we observe that any digraph of directed path-width d has a z- topological ordering for z <= 2d + 1. On the other hand, there are digraphs on n vertices admitting a z-topological order for z = 2, but whose directed path-width is {Theta}(log n). Since graphs of bounded directed path-width can have both arbitrarily large undirected tree-width and arbitrarily large clique width, our result provides for the first time a suitable way of partially trans- posing metatheorems developed in the context of the monadic second order logic of graphs of constant undirected tree-width and constant clique width to the realm of digraph width measures that are closed under taking subgraphs and whose constant levels incorporate families of graphs of arbitrarily large undirected tree-width and arbitrarily large clique width.
We construct Feynman rules and Supergraphs in SIM(2) superspace. To test our methods we perform a one-loop calculation of the effective action of the SIM(2) supersymmetric Wess-Zumino model including a term which explicitly breaks Lorentz invariance. The renormalization of the model is also discussed.
Stochastic models such as Continuous-Time Markov Chains (CTMC) and Stochastic Hybrid Automata (SHA) are powerful formalisms to model and to reason about the dynamics of biological systems, due to their ability to capture the stochasticity inherent in biological processes. A classical question in formal modelling with clear relevance to biological modelling is the model checking problem. i.e. calculate the probability that a behaviour, expressed for instance in terms of a certain temporal logic formula, may occur in a given stochastic process. However, one may not only be interested in the notion of satisfiability, but also in the capacity of a system to mantain a particular emergent behaviour unaffected by the perturbations, caused e.g. from extrinsic noise, or by possible small changes in the model parameters. To address this issue, researchers from the verification community have recently proposed several notions of robustness for temporal logic providing suitable definitions of distance between a trajectory of a (deterministic) dynamical system and the boundaries of the set of trajectories satisfying the property of interest. The contributions of this paper are twofold. First, we extend the notion of robustness to stochastic systems, showing that this naturally leads to a distribution of robustness scores. By discussing two examples, we show how to approximate the distribution of the robustness score and its key indicators: the average robustness and the conditional average robustness. Secondly, we show how to combine these indicators with the satisfaction probability to address the system design problem, where the goal is to optimize some control parameters of a stochastic model in order to best maximize robustness of the desired specifications.
Given a Counting Monadic Second Order (CMSO) sentence $psi$, the CMSO$[psi]$ problem is defined as follows. The input to CMSO$[psi]$ is a graph $G$, and the objective is to determine whether $Gmodels psi$. Our main theorem states that for every CMSO sentence $psi$, if CMSO$[psi]$ is solvable in polynomial time on globally highly connected graphs, then CMSO$[psi]$ is solvable in polynomial time (on general graphs). We demonstrate the utility of our theorem in the design of parameterized algorithms. Specifically we show that technical problem-specific ingredients of a powerful method for designing parameterized algorithms, recursive understanding, can be replaced by a black-box invocation of our main theorem. We also show that our theorem can be easily deployed to show fixed parameterized tractability of a wide range of problems, where the input is a graph $G$ and the task is to find a connected induced subgraph of $G$ such that few vertices in this subgraph have neighbors outside the subgraph, and additionally the subgraph has a CMSO-definable property.
Let $mathbb{F}_{q}$ be the finite field of $q$ elements and let $D_{2n}=langle x,ymid x^n=1, y^2=1, yxy=x^{n-1}rangle$ be the dihedral group of order $n$. Left ideals of the group algebra $mathbb{F}_{q}[D_{2n}]$ are known as left dihedral codes over $mathbb{F}_{q}$ of length $2n$, and abbreviated as left $D_{2n}$-codes. Let ${rm gcd}(n,q)=1$. In this paper, we give an explicit representation for the Euclidean hull of every left $D_{2n}$-code over $mathbb{F}_{q}$. On this basis, we determine all distinct Euclidean LCD codes and Euclidean self-orthogonal codes which are left $D_{2n}$-codes over $mathbb{F}_{q}$. In particular, we provide an explicit representation and a precise enumeration for these two subclasses of left $D_{2n}$-codes and self-dual left $D_{2n}$-codes, respectively. Moreover, we give a direct and simple method for determining the encoder (generator matrix) of any left $D_{2n}$-code over $mathbb{F}_{q}$, and present several numerical examples to illustrative our applications.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
