Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTesting properties of signed graphs
69
0
0.0
(
0
)
Added by
Simon Apers
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In graph property testing the task is to distinguish whether a graph satisfies a given property or is far from having that property, preferably with a sublinear query and time complexity. In this work we initiate the study of property testing in signed graphs, where every edge has either a positive or a negative sign. We show that there exist sublinear algorithms for testing three key properties of signed graphs: balance (or 2-clusterability), clusterability and signed triangle freeness. We consider both the dense graph model, where we can query the (signed) adjacency matrix of a signed graph, and the bounded-degree model, where we can query for the neighbors of a node and the sign of the connecting edge. Our algorithms use a variety of tools from graph property testing, as well as reductions from one setting to the other. Our main technical contribution is a sublinear algorithm for testing clusterability in the bounded-degree model. This contrasts with the property of k-clusterability which is not testable with a sublinear number of queries. The tester builds on the seminal work of Goldreich and Ron for testing bipartiteness.
rate research
Read More
A graph is said to be circular-arc if the vertices can be associated with arcs of a circle so that two vertices are adjacent if and only if the corresponding arcs overlap. It is proved that the isomorphism of circular-arc graphs can be tested by the Weisfeiler-Leman algorithm after individualization of two vertices.
We propose a new setting for testing properties of distributions while receiving samples from several distributions, but few samples per distribution. Given samples from $s$ distributions, $p_1, p_2, ldots, p_s$, we design testers for the following problems: (1) Uniformity Testing: Testing whether all the $p_i$s are uniform or $epsilon$-far from being uniform in $ell_1$-distance (2) Identity Testing: Testing whether all the $p_i$s are equal to an explicitly given distribution $q$ or $epsilon$-far from $q$ in $ell_1$-distance, and (3) Closeness Testing: Testing whether all the $p_i$s are equal to a distribution $q$ which we have sample access to, or $epsilon$-far from $q$ in $ell_1$-distance. By assuming an additional natural condition about the source distributions, we provide sample optimal testers for all of these problems.
It is known that testing isomorphism of chordal graphs is as hard as the general graph isomorphism problem. Every chordal graph can be represented as the intersection graph of some subtrees of a tree. The leafage of a chordal graph, is defined to be the minimum number of leaves in the representing tree. We construct a fixed-parameter tractable algorithm testing isomorphism of chordal graphs with bounded leafage. The key point is a fixed-parameter tractable algorithm finding the automorphism group of a colored order-3 hypergraph with bounded sizes of color classes of vertices.
For a clustered graph, i.e, a graph whose vertex set is recursively partitioned into clusters, the C-Planarity Testing problem asks whether it is possible to find a planar embedding of the graph and a representation of each cluster as a region homeomorphic to a closed disk such that 1. the subgraph induced by each cluster is drawn in the interior of the corresponding disk, 2. each edge intersects any disk at most once, and 3. the nesting between clusters is reflected by the representation, i.e., child clusters are properly contained in their parent cluster. The computational complexity of this problem, whose study has been central to the theory of graph visualization since its introduction in 1995 [Qing-Wen Feng, Robert F. Cohen, and Peter Eades. Planarity for clustered graphs. ESA95], has only been recently settled [Radoslav Fulek and Csaba D. Toth. Atomic Embeddability, Clustered Planarity, and Thickenability. To appear at SODA20]. Before such a breakthrough, the complexity question was still unsolved even when the graph has a prescribed planar embedding, i.e, for embedded clustered graphs. We show that the C-Planarity Testing problem admits a single-exponential single-parameter FPT algorithm for embedded clustered graphs, when parameterized by the carving-width of the dual graph of the input. This is the first FPT algorithm for this long-standing open problem with respect to a single notable graph-width parameter. Moreover, in the general case, the polynomial dependency of our FPT algorithm is smaller than the one of the algorithm by Fulek and Toth. To further strengthen the relevance of this result, we show that the C-Planarity Testing problem retains its computational complexity when parameterized by several other graph-width parameters, which may potentially lead to faster algorithms.
A signed graph is a pair $(G, sigma)$, where $G$ is a graph and $sigma: E(G) to {+, -}$ is a signature which assigns to each edge of $G$ a sign. Various notions of coloring of signed graphs have been studied. In this paper, we extend circular coloring of graphs to signed graphs. Given a signed graph $(G, sigma)$ a circular $r$-coloring of $(G, sigma)$ is an assignment $psi$ of points of a circle of circumference $r$ to the vertices of $G$ such that for every edge $e=uv$ of $G$, if $sigma(e)=+$, then $psi(u)$ and $psi(v)$ have distance at least $1$, and if $sigma(e)=-$, then $psi(v)$ and the antipodal of $psi(u)$ have distance at least $1$. The circular chromatic number $chi_c(G, sigma)$ of a signed graph $(G, sigma)$ is the infimum of those $r$ for which $(G, sigma)$ admits a circular $r$-coloring. For a graph $G$, we define the signed circular chromatic number of $G$ to be $max{chi_c(G, sigma): sigma text{ is a signature of $G$}}$. We study basic properties of circular coloring of signed graphs and develop tools for calculating $chi_c(G, sigma)$. We explore the relation between the circular chromatic number and the signed circular chromatic number of graphs, and present bounds for the signed circular chromatic number of some families of graphs. In particular, we determine the supremum of the signed circular chromatic number of $k$-chromatic graphs of large girth, of simple bipartite planar graphs, $d$-degenerate graphs, simple outerplanar graphs and series-parallel graphs. We construct a signed planar simple graph whose circular chromatic number is $4+frac{2}{3}$. This is based and improves on a signed graph built by Kardos and Narboni as a counterexample to a conjecture of M{a}v{c}ajov{a}, Raspaud, and v{S}koviera.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
