Search

We study homomorphism polynomials, which are polynomials that enumerate all homomorphisms from a pattern graph H to n-vertex graphs. These polynomials have received a lot of attention recently for their crucial role in several new algorithms for counting and detecting graph patterns, and also for obtaining natural polynomial families which are complete for algebraic complexity classes VBP, VP, and VNP. We discover that, in the monotone setting, the formula complexity, the ABP complexity, and the circuit complexity of such polynomial families are exactly characterized by the treedepth, the pathwidth, and the treewidth of the pattern graph respectively. Furthermore, we establish a single, unified framework, using our characterization, to collect several known results that were obtained independently via different methods. For instance, we attain superpolynomial separations between circuits, ABPs, and formulas in the monotone setting, where the polynomial families separating the classes all correspond to well-studied combinatorial problems. Moreover, our proofs rediscover fine-grained separations between these models for constant-degree polynomials., LIPIcs, Vol. 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pages 83:1-83:20

We show that the TEMPORAL GRAPH EXPLORATION PROBLEM is NP-complete, even when the underlying graph has pathwidth 2 and at each time step, the current graph is connected. (C) 2018 Elsevier B.V. All rights reserved.

As a natural variant of the many decycling notions studied in graphs, we consider the problem to decide whether a given graph G has a matching M such that G − M is a forest. We establish NP-completeness of this problem for 2-connected planar subcubic graphs, and describe polynomial time algorithms that also determine such a matching if it exists for graphs that are claw- and paw-free, P 5 -free, chordal, and C 4 -free distance hereditary.

We show that the Temporal Graph Exploration Problem is NP-complete, even when the underlying graph has pathwidth 2 and at each time step, the current graph is connected.

We show that the Temporal Graph Exploration Problem is NP-complete, even when the underlying graph has pathwidth 2 and at each time step, the current graph is connected.

We give an algorithm for computing the directed pathwidth of a digraph with n vertices in $$O(1.89^{n})$$O(1.89n) time. This is the first algorithm with running time better than the straightforward $$O^{*}(2^n)$$O?(2n). As a special case, it computes the pathwidth of an undirected graph in the same amount of time, improving on the algorithm due to Suchan and Villanger which runs in $$O(1.9657^n)$$O(1.9657n) time.

In the Intervalizing Coloured Graphs problem, one must decide for a given graph G = (V, E) with a proper vertex colouring of G whether G is the subgraph of a properly coloured interval graph. For the case that the number of colors is fixed, we give an exact algorithm that uses 2O(n/logn)$2^{\mathcal {O}(n/\log n)}$ time. We also give an O?(2n)$\mathcal {O}^{\ast }(2^{n})$ algorithm for the case that the number of colors is not fixed.

In this work we describe an algorithm to generate tree-decomposable minimally rigid graphs on a given set of vertices V. The main idea is based on the well-known fact that all minimally rigid graphs, also known as Laman graphs, can be generated via Henneberg sequences. Given that not each minimally rigid graph is tree-decomposable, we identify a set of conditions on the way Henneberg steps are applied so that the resulting graph is tree decomposable. We show that the worst case running time of the algorithm is O (vertical bar V vertical bar(3)). (C) 2016 Elsevier Ltd. All rights reserved.

Let (Formula presented.) be a directed graph. A vertex (Formula presented.) (respectively an edge (Formula presented.)) is a strong articulation point (respectively a strong bridge) if its removal increases the number of strongly connected components of (Formula presented.). We implement and engineer fast algorithms for computing all the strong articulation points and all the strong bridges of a directed graph, based on the linear-time algorithms presented in Italiano et al. (Theor Comput Sci 447:74–84, 2012). Our implementations are tested against real-world graphs taken from several application domains, including social networks, communication graphs, web graphs, peer2peer networks and product co-purchase graphs. The algorithms implemented turn out to be very efficient in practice, and are able to run on large scale graphs, i.e., on graphs with ten million vertices and half billion edges. Our experiments on such graphs highlight some properties of strong articulation points, which might be of independent interest.

This paper considers the problem of inferring a graph from the number of occurrences of vertex-labeled paths, which is closely related to the pre-image problem for graphs: to reconstruct a graph from its feature space representation. It is shown that both exact and approximate versions of the problem can be solved in polynomial time in the size of an output graph by using dynamic programming algorithms if the graphs are trees whose maximum degree is bounded by a constant and the lengths of given paths and alphabet size are bounded by constants. On the other hand, it is shown that this problem is strongly NP-hard even for trees of bounded degree if the maximum length of paths is not bounded. The problem of inferring a string from the number of occurrences of fixed size substrings is also studied.

A t-spanner of a graph G is a spanning subgraph S in which the distance between every pair of vertices is at most t times their distance in G. If S is required to be a tree then S is called a tree t-spanner of G. In 1998, Fekete and Kremer showed that on unweighted planar graphs deciding whether G admits a tree t-spanner is polynomial time solvable for t⩽3 and is NP-complete when t is part of the input. They also left as an open problem if the problem is polynomial time solvable for every fixed t⩾4. In this work we resolve the open question of Fekete and Kremer by proving much more general results:•The problem of finding a t-spanner of treewidth at most k in a given planar graph G is fixed parameter tractable parameterized by k and t. Moreover, for every fixed t and k, the running time of our algorithm is linear.•Our technique allows to extend the result from planar graphs to much more general classes of graphs. An apex graph is a graph that can be made planar by the removal of a single vertex. We prove that the problem of finding a t-spanner of treewidth k is fixed parameter tractable on graphs that do not contain some fixed apex graph as a minor, i.e. on apex-minor-free graphs. The class of apex-minor-free graphs contains planar graphs and graphs of bounded genus.•Finally, we show that the tractability border of the t-spanner problem cannot be extended beyond the class of apex-minor-free graphs and in this sense our results are tight. In particular, for every t⩾4, the problem of finding a tree t-spanner is NP-complete on K6-minor-free graphs.

The problem of computing minimum distortion embeddings of a given graph into a line (path) was introduced in 2004 and has quickly attracted significant attention with subsequent results appearing at recent stoc and soda conferences. So far, all such results concern approximation algorithms or exponential-time exact algorithms. We give the first polynomial-time algorithms for computing minimum distortion embeddings of graphs into a path when the input graphs belong to specific graph classes. In particular, we solve this problem in polynomial time for bipartite permutation graphs and threshold graphs. For both graph classes, the distortion can be arbitrarily large. The graphs that we consider are unweighted.

A spanning tree T of a graph G is called a treet-spanner, if the distance between any two vertices in T is at most t-times their distance in G. A graph that has a tree t-spanner is called a treet-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t≥4, and is linearly solvable for t=1 and t=2. The case t=3 still remains open. A directed path graph is called a 2-sep directed path graph if all of its minimal a−b vertex separator for every pair of non-adjacent vertices a and b are of size two. Le and Le [H.-O. Le, V.B. Le, Optimal tree 3-spanners in directed path graphs, Networks 34 (2) (1999) 81–87] showed that directed path graphs admit tree 3-spanners. However, this result has been shown to be incorrect by Panda and Das [B.S. Panda, Anita Das, On tree 3-spanners in directed path graphs, Networks 50 (3) (2007) 203–210]. In fact, this paper observes that even the class of 2-sep directed path graphs, which is a proper subclass of directed path graphs, need not admit tree 3-spanners in general. It, then, presents a structural characterization of tree 3-spanner admissible 2-sep directed path graphs. Based on this characterization, a linear time recognition algorithm for tree 3-spanner admissible 2-sep directed path graphs is presented. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep directed path graph is proposed.

In this paper, the mutual exclusion scheduling problem is addressed. Given a simple and undirected graph G and an integer k, the problem is to find a minimum coloring of G such that each color is used at most k times. When restricted to interval graphs or related classes like circular-arc graphs and tolerance graphs, the problem has some applications in workforce planning. Unfortunately, the problem is shown to be NP-hard for interval graphs, even if k is a constant greater than or equal to four [H.L. Bodlaender and K. Jansen Restrictions of graph partition problems. Part I, Theoretical Computer Science 148(1995) pp. 93–109]. Several polynomial-time solvable cases significant in practice are exhibited here, for which we took care to devise simple and efficient algorithms (in particular linear-time and space algorithms). On the other hand, by reinforcing the NP-hardness result of Bodlaender and Jansen, we obtain a more precise cartography of the complexity of the problem for the classes of graphs studied.

For a given graph G=(V,E), the interval completion problem of G is to find an edge set F such that the supergraph H=(V,E∪F) of G is an interval graph and |F| is minimum. It has been shown that it is equivalent to the minimum sum cut problem, the profile minimization problem and a kind of graph searching problems. Furthermore, it has applications in computational biology, archaeology, and clone fingerprinting. In this paper, we show that it is NP-complete on split graphs and propose an efficient algorithm on primitive starlike graphs.

We consider the problem of recognizing AT-free graphs. Although there is a simple O(n3) algorithm, no faster method for solving this problem had been known. Here we give three different algorithms which have a better time complexity for graphs which are sparse or have a sparse complement; in particular we give algorithms which recognize AT-free graphs in O (n m +n 2 ) , O ( m 3/2 +n 2 ) , and O(n2.82+nm). In addition we give a new characterization of graphs with bounded asteroidal number by the help of the knotting graph, a combinatorial structure which was introduced by Gallai for considering comparability graphs.

A potential maximal clique of a graph is a vertex set that induces a maximal clique in some minimal triangulation of that graph. It is known that if these objects can be listed in polynomial time for a class of graphs, the treewidth and the minimum fill-in are polynomially tractable for these graphs. We show here that the potential maximal cliques of a graph can be generated in polynomial time in the number of minimal separators of the graph. Thus, the treewidth and the minimum fill-in are polynomially tractable for all classes of graphs with a polynomial number of minimal separators.

We study the following independent set reconfiguration problem: given two independent sets I and J of a graph G, both of size at least k, is it possible to transform I into J by adding and removing vertices one-by-one, while maintaining an independent set of size at least k throughout? This problem is known to be PSPACE-hard in general. For the case that G is a cograph on n vertices, we show that it can be solved in polynomial time. More generally, we show that for a graph class G that includes all chordal and claw-free graphs, the problem can be solved in polynomial time for graphs that can be obtained from a collection of graphs from G using disjoint union and complete join operations.

Motivated by the desire to speed up dynamic programming algorithms for graphs of bounded treewidth, we initiate a study of the tradeoff between width and pathwidth of tree-decompositions. We therefore investigate the catwidth parameter catw(G) which is the minimum width of any tree-decomposition (T,X) of a graph G when the pathwidth pw(T) of the tree T is 1. The catwidth parameter lies between the treewidth and the pathwidth of the graph, tw(G)⩽catw(G)⩽pw(G), and just as treewidth relates to chordal graphs and pathwidth relates to interval graphs, catwidth relates to what we call catval graphs. We introduce the notion of an extended asteroidal triple (XAT) and characterize catval graphs as the XAT-free chordal graphs. We provide alternative characterizations of these graphs, show that there are graph classes for which the various parameters differ by an arbitrary amount, and consider algorithms for computing catwidth.

A majority dominating function on the vertex set of a graph G=(V,E) is a function g:V→{1,−1} such that g(N[v])⩾1 for at least half of the vertices v in V. The weight of a majority dominating function is denoted as g(V) and is ∑ g(v) over all v in V. The majority domination number of a graph is the minimum possible weight of a majority dominating function, and is denoted as γmaj(G). We determine the majority domination numbers of certain families of graphs. Moreover, we show that the decision problem corresponding to computing the majority domination number of an arbitrary disjoint union of complete graphs is NP-complete.

A general method for the computation of various parameters measuring the vulnerability of a graph is introduced. Four measures of vulnerability are considered, i.e., the toughness, scattering number, vertex integrity and the size of a minimum balanced separator. We show how to compute these parameters by polynomial-time algorithms for various classes of intersection graphs like permutation graphs, bounded dimensional cocomparability graphs, interval graphs, trapezoid graphs and circular versions of these graph classes.

Extended abstract published in FAW 2010 (LNCS, Springer); In this paper we investigate the structural properties of $k$-path separable graphs, that are the graphs that can be separated by a set of $k$ shortest paths. We identify several graph families having such path separability, and we show that this property is closed under minor taking. In particular we establish a list of forbidden minors for $1$-path separable graphs.

In this paper, we extend the notion of similarity matrix, which has been used to define similarity between nodes of two graphs, to the case of colored graphs, where the coloring is either on the nodes or on the edges of both graphs. The proposed method tries to find the optimal matching between the nodes or edges of both graphs but only performs the comparison when their colors are the same. The proposed cost function nevertheless uses the connectivity between all nodes and edges of both graphs. We then also show how to extend this to the notion of low rank similarity matrix, by defining it as a constrained optimization problem.

The contribution of this paper is twofold. It presents a new approach to the matched drawability problem of pairs of planar graphs and it provides four algorithms based on this approach for drawing the pairs 〈outerplane,maximalouterpillar〉, 〈outerplane,generalized outerpath〉, 〈outerplane,wheel〉 and 〈wheel,wheel〉. Further, it initiates the study of the matched drawability of triples of planar graphs: it presents an algorithm to compute a matched drawing of a triple of cycles and an algorithm to compute a matched drawing of a caterpillar and two unlabeled level planar graphs. The results extend previous work on the subject and relate to existing literature about simultaneous embeddability and unlabeled level planarity.

A natural way to draw two planar graphs whose vertex sets are matched is to assign each matched pair a unique y-coordinate. In this paper we introduce the concept of such matched drawings, which are a relaxation of simultaneous geometric embeddings with mapping. We study which classes of graphs allow matched drawings and show that (i) two 3-connected planar graphs or a 3-connected planar graph and a tree may not be matched drawable, while (ii) two trees or a planar graph and a planar graph of some special families—such as unlabeled level planar (ULP) graphs or the family of "carousel graphs"—are always matched drawable. Research partially supported by the MIUR Project "MAINSTREAM: Algorithms for massive information structures and data streams".

The efficient distributed construction of a maximal independent set (MIS) of a graph is of fundamental importance. We study the problem in the class of Growth-Bounded Graphs, which includes for example the well-known Unit Disk Graphs. In contrast to the fastest (time-optimal) existing approach [11], we assume that no geometric information (e.g., distances in the graph's embedding) is given. Instead, nodes employ randomization for their decisions. Our algorithm computes a MIS in O(log log n • log* n) rounds with very high probability for graphs with bounded growth, where n denotes the number of nodes in the graph. In view of Linial's Ω(log* n) lower bound for computing a MIS in ring networks [12], which was extended to randomized algorithms independently by Naor [18] and Linial [13], our solution is close to optimal.In a nutshell, our algorithm shows that for computing a MIS, randomization is a viable alternative to distance information.

Given a graph G , the Minimum Dominating Trail Set (MDTS) problem consists in finding a minimum cardinality collection of pairwise edge-disjoint trails such that each edge of G has at least one endvertex on some trail. The MDTS problem is NP –hard for general graphs. In this paper an algorithmic approach for the MDTS problem on (two-terminal) series parallel graphs is presented.

We introduce a natural heuristic for approximating the treewidth of graphs. We prove that this heuristic gives a constant factor approximation for the treewidth of graphs with bounded asteroidal number. Using a different technique, we give a O(logk) approximation algorithm for the treewidth of arbitrary graphs, where k is the treewidth of the input graph.

Using the specific structure of the minimal separators of AT-free graphs, we give a polynomial time algorithm that computes a triangulation whose width is no more than twice the treewidth of the input graph.

In this note, simple approximation algorithms for the weighted independent set problem are presented with a performance ratio depending on $\Delta(G)$. These algorithms do not improve the best approximation algorithm known so far for this problem but they are of interest because of their simplicity. Precisely, we show how an optimum weighted independent set in bipartite graphs and a $\rho$-approximation of {\wis} in $k$-partite graphs respectively allows to obtain a ${2\over \Delta(G)}$-approximation and a ${k\over \Delta(G)}\rho$-approximation in general graphs. Note that the ratio ${2\over \Delta(G)}$ is the best bound known for the particular cases $\Delta(G)=3$ or $\Delta(G)=4$.

22nd International Workshop WG '96; International audience; We solve the Union-Find problem (UF) efficiently for the case the input is restricted to several graph classes, namely partial k-trees for any fixed k, d-dimensional grids for any fixed dimension d and for planar graphs. For the later we develop a technique of decomposing such a graph into small subgraphs, patching, that might be useful for other algorithmic problems on planar graphs, too. By efficiency we do not only mean ``linear time'' in a theoretical setting but also a practical reorganization of memory such that a dynamic data structures for UF is allocated consecutively and thus to reduce the amount of page fault produced by UF implementations drastically.