Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStability of Special Graph Classes
140
0
0.0
(
0
)
Added by
Robin Weishaupt
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Frei et al. [6] showed that the problem to decide whether a graph is stable with respect to some graph parameter under adding or removing either edges or vertices is $Theta_2^{text{P}}$-complete. They studied the common graph parameters $alpha$ (independence number), $beta$ (vertex cover number), $omega$ (clique number), and $chi$ (chromatic number) for certain variants of the stability problem. We follow their approach and provide a large number of polynomial-time algorithms solving these problems for special graph classes, namely for graphs without edges, complete graphs, paths, trees, forests, bipartite graphs, and co-graphs.
rate research
Read More
Let $t$ be a positive real number. A graph is called $t$-tough, if the removal of any cutset $S$ leaves at most $|S|/t$ components. The toughness of a graph is the largest $t$ for which the graph is $t$-tough. A graph is minimally $t$-tough, if the toughness of the graph is $t$ and the deletion of any edge from the graph decreases the toughness. In this paper we investigate the minimum degree and the recognizability of minimally $t$-tough graphs in the class of chordal graphs, split graphs, claw-free graphs and $2K_2$-free graphs.
Let $T$ be a right exact functor from an abelian category $mathscr{B}$ into another abelian category $mathscr{A}$. Then there exists a functor ${bf p}$ from the product category $mathscr{A}timesmathscr{B}$ to the comma category $(Tdownarrowmathscr{A})$. In this paper, we study the property of the extension closure of some classes of objects in $(Tdownarrowmathscr{A})$, the exactness of the functor ${bf p}$ and the detail description of orthogonal classes of a given class ${bf p}(mathcal{X},mathcal{Y})$ in $(Tdownarrowmathscr{A})$. Moreover, we characterize when special precovering classes in abelian categories $mathscr{A}$ and $mathscr{B}$ can induce special precovering classes in $(Tdownarrowmathscr{A})$. As an application, we prove that under suitable cases, the class of Gorenstein projective left $Lambda$-modules over a triangular matrix ring $Lambda=left(begin{smallmatrix}R & M O & S end{smallmatrix} right)$ is special precovering if and only if both the classes of Gorenstein projective left $R$-modules and left $S$-modules are special precovering. Consequently, we produce a large variety of examples of rings such that the class of Gorenstein projective modules is special precovering over them.
We prove three results on the dimension structure of complexity classes. 1. The Point-to-Set Principle, which has recently been used to prove several new theorems in fractal geometry, has resource-bounded instances. These instances characterize the resource-bounded dimension of a set $X$ of languages in terms of the relativized resource-bounded dimensions of the individual elements of $X$, provided that the former resource bound is large enough to parameterize the latter. Thus for example, the dimension of a class $X$ of languages in EXP is characterized in terms of the relativized p-dimensions of the individual elements of $X$. 2. Every language that is $leq^P_m$-reducible to a p-selective set has p-dimension 0, and this fact holds relative to arbitrary oracles. Combined with a resource-bounded instance of the Point-to-Set Principle, this implies that if NP has positive dimension in EXP, then no quasipolynomial time selective language is $leq^P_m$-hard for NP. 3. If the set of all disjoint pairs of NP languages has dimension 1 in the set of all disjoint pairs of EXP languages, then NP has positive dimension in EXP.
Algebraic Branching Programs(ABPs) are standard models for computing polynomials. Syntactic multilinear ABPs (smABPs) are restrictions of ABPs where every variable is allowed to occur at most once in every path from the start to the terminal node. Proving lower bounds against syntactic multilinear ABPs remains a challenging open question in Algebraic Complexity Theory. The current best known bound is only quadratic [Alon-Kumar-Volk, ECCC 2017]. In this article we develop a new approach upper bounding the rank of the partial derivative matrix of syntactic multlinear ABPs: Convert the ABP to a syntactic mulilinear formula with a super polynomial blow up in the size and then exploit the structural limitations of resulting formula to obtain a rank upper bound. Using this approach, we prove exponential lower bounds for special cases of smABPs and circuits - namely sum of Oblivious Read-Once ABPs, r-pass mulitlinear ABPs and sparse ROABPs. En route, we also prove super-polynomial lower bound for a special class of syntactic multilinear arithmetic circuits.
We present an approach to non-uniform complexity in which single-pass instruction sequences play a key part, and answer various questions that arise from this approach. We introduce several kinds of non-uniform complexity classes. One kind includes a counterpart of the well-known non-uniform complexity class P/poly and another kind includes a counterpart of the well-known non-uniform complexity class NP/poly. Moreover, we introduce a general notion of completeness for the non-uniform complexity classes of the latter kind. We also formulate a counterpart of the well-known complexity theoretic conjecture that NP is not included in P/poly. We think that the presented approach opens up an additional way of investigating issues concerning non-uniform complexity.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
