Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA note on block-and-bridge preserving maximum common subgraph algorithms for outerplanar graphs
64
0
0.0
(
0
)
Added by
Nils Kriege
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Schietgat, Ramon and Bruynooghe proposed a polynomial-time algorithm for computing a maximum common subgraph under the block-and-bridge preserving subgraph isomorphism (BBP-MCS) for outerplanar graphs. We show that the article contains the following errors: (i) The running time of the presented approach is claimed to be $mathcal{O}(n^{2.5})$ for two graphs of order $n$. We show that the algorithm of the authors allows no better bound than $mathcal{O}(n^4)$ when using state-of-the-art general purpose methods to solve the matching instances arising as subproblems. This is even true for the special case, where both input graphs are trees. (ii) The article suggests that the dissimilarity measure derived from BBP-MCS is a metric. We show that the triangle inequality is not always satisfied and, hence, it is not a metric. Therefore, the dissimilarity measure should not be used in combination with techniques that rely on or exploit the triangle inequality in any way. Where possible, we give hints on techniques that are suitable to improve the algorithm.
rate research
Read More
The complexity of the maximum common connected subgraph problem in partial $k$-trees is still not fully understood. Polynomial-time solutions are known for degree-bounded outerplanar graphs, a subclass of the partial $2$-trees. On the other hand, the problem is known to be ${bf NP}$-hard in vertex-labeled partial $11$-trees of bounded degree. We consider series-parallel graphs, i.e., partial $2$-trees. We show that the problem remains ${bf NP}$-hard in biconnected series-parallel graphs with all but one vertex of degree $3$ or less. A positive complexity result is presented for a related problem of high practical relevance which asks for a maximum common connected subgraph that preserves blocks and bridges of the input graphs. We present a polynomial time algorithm for this problem in series-parallel graphs, which utilizes a combination of BC- and SP-tree data structures to decompose both graphs.
The maximum independent set problem is one of the most important problems in graph algorithms and has been extensively studied in the line of research on the worst-case analysis of exact algorithms for NP-hard problems. In the weighted version, each vertex in the graph is associated with a weight and we are going to find an independent set of maximum total vertex weight. In this paper, we design several reduction rules and a fast exact algorithm for the maximum weighted independent set problem, and use the measure-and-conquer technique to analyze the running time bound of the algorithm. Our algorithm works on general weighted graphs and it has a good running time bound on sparse graphs. If the graph has an average degree at most 3, our algorithm runs in $O^*(1.1443^n)$ time and polynomial space, improving previous running time bounds for the problem in cubic graphs using polynomial space.
A semi-proper orientation of a given graph $G$, denoted by $(D,w)$, is an orientation $D$ with a weight function $w: A(D)rightarrow mathbb{Z}_+$, such that the in-weight of any adjacent vertices are distinct, where the in-weight of $v$ in $D$, denoted by $w^-_D(v)$, is the sum of the weights of arcs towards $v$. The semi-proper orientation number of a graph $G$, denoted by $overrightarrow{chi}_s(G)$, is the minimum of maximum in-weight of $v$ in $D$ over all semi-proper orientation $(D,w)$ of $G$. This parameter was first introduced by Dehghan (2019). When the weights of all edges eqaul to one, this parameter is equal to the proper orientation number of $G$. The optimal semi-proper orientation is a semi-proper orientation $(D,w)$ such that $max_{vin V(G)}w_D^-(v)=overrightarrow{chi}_s(G)$. Araujo et al. (2016) showed that $overrightarrow{chi}(G)le 7$ for every cactus $G$ and the bound is tight. We prove that for every cactus $G$, $overrightarrow{chi}_s(G) le 3$ and the bound is tight. Ara{u}jo et al. (2015) asked whether there is a constant $c$ such that $overrightarrow{chi}(G)le c$ for all outerplanar graphs $G.$ While this problem remains open, we consider it in the weighted case. We prove that for every outerplanar graph $G,$ $overrightarrow{chi}_s(G)le 4$ and the bound is tight.
We propose a weighted common subgraph (WCS) matching algorithm to find the most similar subgraphs in two labeled weighted graphs. WCS matching, as a natural generalization of the equal-sized graph matching or subgraph matching, finds wide applications in many computer vision and machine learning tasks. In this paper, the WCS matching is first formulated as a combinatorial optimization problem over the set of partial permutation matrices. Then it is approximately solved by a recently proposed combinatorial optimization framework - Graduated NonConvexity and Concavity Procedure (GNCCP). Experimental comparisons on both synthetic graphs and real world images validate its robustness against noise level, problem size, outlier number, and edge density.
Subgraph counting is a fundamental problem in analyzing massive graphs, often studied in the context of social and complex networks. There is a rich literature on designing efficient, accurate, and scalable algorithms for this problem. In this work, we tackle this challenge and design several new algorithms for subgraph counting in the Massively Parallel Computation (MPC) model: Given a graph $G$ over $n$ vertices, $m$ edges and $T$ triangles, our first main result is an algorithm that, with high probability, outputs a $(1+varepsilon)$-approximation to $T$, with optimal round and space complexity provided any $S geq max{(sqrt m, n^2/m)}$ space per machine, assuming $T=Omega(sqrt{m/n})$. Our second main result is an $tilde{O}_{delta}(log log n)$-rounds algorithm for exactly counting the number of triangles, parametrized by the arboricity $alpha$ of the input graph. The space per machine is $O(n^{delta})$ for any constant $delta$, and the total space is $O(malpha)$, which matches the time complexity of (combinatorial) triangle counting in the sequential model. We also prove that this result can be extended to exactly counting $k$-cliques for any constant $k$, with the same round complexity and total space $O(malpha^{k-2})$. Alternatively, allowing $O(alpha^2)$ space per machine, the total space requirement reduces to $O(nalpha^2)$. Finally, we prove that a recent result of Bera, Pashanasangi and Seshadhri (ITCS 2020) for exactly counting all subgraphs of size at most $5$, can be implemented in the MPC model in $tilde{O}_{delta}(sqrt{log n})$ rounds, $O(n^{delta})$ space per machine and $O(malpha^3)$ total space. Therefore, this result also exhibits the phenomenon that a time bound in the sequential model translates to a space bound in the MPC model.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
