From a Zoo to a Zoology: Towards a General Theory of Graph Polynomials

We outline a general theory of graph polynomials which covers all the examples we found in the vast literature, in particular, the chromatic polynomial, various generalizations of the Tutte polynomial, matching polynomials, interlace polynomials, and the cover polynomial of digraphs. We introduce two classes of (hyper)graph polynomials definable in second order logic, and outline a research program for their classification in terms of definability and complexity considerations, and various notions of reducibilities.     

Complexity of the Bollobás–Riordan Polynomial. Exceptional Points and Uniform Reductions

The coloured Tutte polynomial by Bollobás and Riordan is, as a generalization of the Tutte polynomial, the most general graph polynomial for coloured graphs that satisfies certain contraction-deletion identities. Jaeger, Vertigan, and Welsh showed that the classical Tutte polynomial is #P-hard to evaluate almost everywhere by establishing reductions along curves and lines.     

Acyclic colorings of subcubic graphs

It is known that the acyclic chromatic number of a subcubic graph is at most four, and its acyclic edge chromatic number is at most five. We present algorithms that prove these two facts. Let n be the number of vertices of a graph. Our first algorithm takes O(n) time and uses four colors to properly color the vertices of any subcubic graph so that there is no 2-colored cycle. Our second algorithm takes O(n) time and uses five colors to properly color the edges of any subcubic graph so that there is no 2-colored cycle. Both are the first linear-time algorithms for the problems they solve.     

Complexity of approximation of 3-edge-coloring of graphs

The problem to find a 4-edge-coloring of a 3-regular graph is solvable in polynomial time but an analogous problem for 3-edge-coloring is NP-hard. To make the gap more precise, we study complexity of approximation algorithms for invariants measuring how far is a 3-regular graph from having a 3-edge-coloring. We show that it is an NP-hard problem to approximate such invariants with an error O(n1−ε), where n denotes the order of the graph and 0<ε<1 is a constant.     

Spanning Trees and the Complexity of Flood-Filling Games

We consider problems related to the combinatorial game (Free-) Flood-It, in which players aim to make a coloured graph monochromatic with the minimum possible number of flooding operations. We show that the minimum number of moves required to flood any given graph G is equal to the minimum, taken over all spanning trees T of G, of the number of moves required to flood T. This result is then applied to give two polynomial-time algorithms for flood-filling problems. Firstly, we can compute in polynomial time the minimum number of moves required to flood a graph with only a polynomial number of connected subgraphs. Secondly, given any coloured connected graph and a subset of the vertices of bounded size, the number of moves required to connect this subset can be computed in polynomial time.     

Complexity and Approximability of the Cover Polynomial

The cover polynomial and its geometric version introduced by Chung & Graham and D??Antona & Munarini, respectively, are two-variate graph polynomials for directed graphs. They count the (weighted) number of ways to cover a graph with disjoint directed cycles and paths, can be thought of as interpolations between determinant and permanent, and are proposed as directed analogues of the Tutte polynomial. Jaeger, Vertigan, and Welsh showed that the Tutte polynomial is #P-hard to evaluate at all but a few special points and curves. It turns out that the same holds for the cover polynomials: We prove that, in almost the whole plane, the problem of evaluating the cover polynomial and its geometric version is #P-hard under polynomial time Turing reductions, while only three points in the cover polynomial and two points in the geometric cover polynomial are easy. We also study the complexity of approximately evaluating the geometric cover polynomial. Under the reasonable complexity assumptions RP ?? NP and RFP ?? #P, we give a succinct characterization of a large class of points at which approximating the geometric cover polynomial within any polynomial factor is not possible.     

Polynomial-Time Algorithms for Energy Games with Special Weight Structures

Energy games belong to a class of turn-based two-player infinite-duration games played on a weighted directed graph. It is one of the rare and intriguing combinatorial problems that lie in NP∩co-NP, but are not known to be in P. The existence of polynomial-time algorithms has been a major open problem for decades and apart from pseudopolynomial algorithms there is no algorithm that solves any non-trivial subclass in polynomial time. In this paper, we give several results based on the weight structures of the graph. First, we identify a notion of penalty and present a polynomial-time algorithm when the penalty is large. Our algorithm is the first polynomial-time algorithm on a large class of weighted graphs. It includes several worst-case instances on which previous algorithms, such as value iteration and random facet algorithms, require at least sub-exponential time. Our main technique is developing the first non-trivial approximation algorithm and showing how to convert it to an exact algorithm. Moreover, we show that in a practical case in verification where weights are clustered around a constant number of values, the energy game problem can be solved in polynomial time. We also show that the problem is still as hard as in general when the clique-width is bounded or the graph is strongly ergodic, suggesting that restricting the graph structure does not necessarily help.     

On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms

For a graph G=(V,E) and a color set C, let f:E→C be an edge-coloring of G in which two adjacent edges may have the same color. Then, the graph G edge-colored by f is rainbow connected if every two vertices of G have a path in which all edges are assigned distinct colors. Chakraborty et al. defined the problem of determining whether the graph colored by a given edge-coloring is rainbow connected. Chen et al. introduced the vertex-coloring version of the problem as a variant, and we introduce the total-coloring version in this paper. We settle the precise computational complexities of all the three problems with regards to graph diameters, and also characterize these with regards to certain graph classes: cacti, outer planer and series-parallel graphs. We then give FPT algorithms for the three problems on general graphs when parameterized by the number of colors in C; our FPT algorithms imply that all the three problems can be solved in polynomial time for any graph with n vertices if |C|=O(logn).     

Parallel bioinspired algorithms for NP complete graph problems

It is no longer believed that DNA computing will outperform digital computers when it comes to the computation of intractable problems. In this paper, we emphasise the in silico implementation of DNA-inspired algorithms as the only way to compete with other algorithms for solving NP-complete problems. For this, we provide sticker algorithms for some of the most representative NP-complete graph problems. The simple data structures and bit-vertical operations make them suitable for some parallel architectures. The parallel algorithms might solve either moderate-size problems in an exact manner or, when combined with a heuristic, large problems in polynomial time.     

Single-machine scheduling with deteriorating jobs under a series–parallel graph constraint

This paper considers single-machine scheduling problems with deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. In addition, the jobs are related by a series–parallel graph. It is shown that for the general linear problem to minimize the makespan, polynomial algorithms exist. It is also shown that for the proportional linear problem of minimization of the total weighted completion time, polynomial algorithms exist, too.     

Algorithms for Partition of Some Class of Graphs under Compaction and Vertex-Compaction

The compaction problem is to partition the vertices of an input graph G onto the vertices of a fixed target graph H, such that adjacent vertices of G remain adjacent in H, and every vertex and non-loop edge of H is covered by some vertex and edge of G respectively, i.e., the partition is a homomorphism of G onto H (except the loop edges). Various computational complexity results, including both NP-completeness and polynomial time solvability, have been presented earlier for this problem for various classes of target graphs H. In this paper, we pay attention to the input graphs G, and present polynomial time algorithms for the problem for some class of input graphs, keeping the target graph H general as any reflexive or irreflexive graph. Our algorithms also give insight as for which instances of the input graphs, the problem could possibly be NP-complete for certain target graphs. With the help of our results, we are able to further refine the structure of the input graph that would be necessary for the problem to be possibly NP-complete, when the target graph is a cycle. Thus, when the target graph is a cycle, we enhance the class of input graphs for which the problem is polynomial time solvable. We also present analogous results for a variation of the compaction problem, which we call the vertex-compaction problem. Using our results, we also provide important relationships between compaction, retraction, and vertex-compaction to cycles.     

Win-win kernelization for degree sequence completion problems

We study provably effective and efficient data reduction for a class of NP-hard graph modification problems based on vertex degree properties. We show fixed-parameter tractability for NP-hard graph completion (that is, edge addition) cases while we show that there is no hope to achieve analogous results for the corresponding vertex or edge deletion versions. Our algorithms are based on transforming graph completion problems into efficiently solvable number problems and exploiting f-factor computations for translating the results back into the graph setting. Our core observation is that we encounter a win-win situation: either the number of edge additions is small or the problem is polynomial-time solvable. This approach helps in answering an open question by Mathieson and Szeider [JCSS 2012] concerning the polynomial kernelizability of Degree Constraint Edge Addition and leads to a general method of approaching polynomial-time preprocessing for a wider class of degree sequence completion problems.     

Inapproximability of the Tutte polynomial of a planar graph

The Tutte polynomial of a graph G is a two-variable polynomial T(G; x, y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: given as input a planar graph G, determine T(G; x, y). Vertigan completely mapped the complexity of exactly computing the Tutte polynomial of a planar graph. He showed that the problem can be solved in polynomial time if (x, y) is on the hyperbola H _q given by (x ? 1)(y ? 1) = q for q = 1 or q = 2 or if (x, y) is one of the two special points (x, y) = (?1, ?1) or (x, y) = (1, 1). Otherwise, the problem is #P-hard. In this paper, we consider the problem of approximating T(G; x, y), in the usual sense of “fully polynomial randomized approximation scheme” or FPRAS. Roughly speaking, an FPRAS is required to produce, in polynomial time and with high probability, an answer that has small relative error. Assuming that NP is different from RP, we show that there is no FPRAS for the Tutte polynomial in a large portion of the (x, y) plane. In particular, there is no FPRAS if x > 1, y < ?1 or if y > 1, x < ?1 or if x < 0, y < 0 and q > 5. Also, there is no FPRAS if x < 1, y < 1 and q = 3. For q > 5, our result is intriguing because it shows that there is no FPRAS at (x, y) =?(1 ? q/(1 + ε), ?ε) for any positive ε but it leaves open the limit point ε =?0, which corresponds to approximately counting q-colorings of a planar graph.     

On packing shortest cycles in graphs

We study the problems to find a maximum packing of shortest edge-disjoint cycles in a graph of given girth g (g-ESCP) and its vertex-disjoint analogue g-VSCP. In the case g=3, Caprara and Rizzi (2001) have shown that g-ESCP can be solved in polynomial time for graphs with maximum degree 4, but is APX-hard for graphs with maximum degree 5, while g-VSCP can be solved in polynomial time for graphs with maximum degree 3, but is APX-hard for graphs with maximum degree 4. For g∈{4,5}, we show that both problems allow polynomial time algorithms for instances with maximum degree 3, but are APX-hard for instances with maximum degree 4. For each g?6, both problems are APX-hard already for graphs with maximum degree 3.     

Nonconstructive advances in polynomial-time complexity

The field of computational complexity for concrete, practical combinatorial problems has developed in a remarkably smooth fashion. One can point to several features of the theory of polynomial-time computability which make it especially well-behaved, including: (1) the modelling of feasible computing by polynomial-time complexity is well-supported by the fact that almost all known polynomial-time algorithms for natural problems have running times bounded by polynomials of small degree; (2) problems are invariably known to be decidable in polynomial time by direct evidence in the form of efficient algorithms; (3) while the theory is formulated in terms of decision problems, almost all known algorithms proceed by actually constructing a solution to the problem at hand.Herein we illustrate how recent advances in graph theory and graph algorithms dramatically alter this situation on all three counts. Powerful and easy-to-apply tools are now available for classifying problems as decidable in polynomial time by nonconstructively proving only the existence of polynomial-time decision algorithms. These tools neither specify the degree of the polynomial, nor produce the decision algorithm, nor guarantee that such an algorithm is of any use in constructing a solution. These developments present both practitioners and theories with novel challenges.     

Approximating minimum spanning tree of depth 2

We prove that the problem of finding, in an undirected graph with non-negative costs on edges, a minimum cost rooted spanning tree of depth 2 is NP-hard. We then prove that, in a graph of order n , this problem cannot be approximated within better than O )ln n ), unless problems in NP can be solved by slightly superpolynomial algorithms. We also prove that the metric version of the problem is MAX-SNP-hard and, consequently, cannot be approximated by polynomial time approximation schemes, unless P=NP. We devise approximation algorithms for several restricted cases and, finally, a polynomial time algorithm approximating the general problem within ratio ln n .     

Exact Computation of the Topology and Geometric Invariants of the Voronoi Diagram of Spheres in 3D

In this paper, we are addressing the exact computation of the Delaunay graph (or quasi-triangulation) and the Voronoi diagram of spheres using Wu’s algorithm. Our main contributions are first a methodology for automated derivation of invariants of the Delaunay empty circumsphere predicate for spheres and the Voronoi vertex of four spheres, then the application of this methodology to get all geometrical invariants that intervene in this problem and the exact computation of the Delaunay graph and the Voronoi diagram of spheres. To the best of our knowledge, there does not exist a comprehensive treatment of the exact computation with geometrical invariants of the Delaunay graph and the Voronoi diagram of spheres. Starting from the system of equations defining the zero-dimensional algebraic set of the problem, we are applying Wu’s algorithm to transform the initial system into an equivalent Wu characteristic (triangular) set. In the corresponding system of algebraic equations, in each polynomial (except the first one), the variable with higher order from the preceding polynomial has been eliminated (by pseudo-remainder computations) and the last polynomial we obtain is a polynomial of a single variable. By regrouping all the formal coefficients for each monomial in each polynomial, we get polynomials that are invariants for the given problem. We rewrite the original system by replacing the invariant polynomials by new formal coefficients. We repeat the process until all the algebraic relationships (syzygies) between the invariants have been found by applying Wu’s algorithm on the invariants. Finally, we present an incremental algorithm for the construction of Voronoi diagrams and Delaunay graphs of spheres in 3D and its application to Geodesy.     

Minimum cost service composition in service overlay networks

In service computing, it is often desirable to find the service composition solution for a given service composition request such that the total cost of the service composition solution is minimized. In this paper, we study the problem of finding the minimum cost service composition (MCSC) for a general service composition request which is represented by a directed acyclic graph (DAG). We first prove that the general case of the MCSC problem is NP-Hard. We then show that optimal solutions can be found in polynomial time for some special structured service composition requests. To this end, we derive a sufficient condition on the service composition request graph and propose corresponding algorithms to find the optimal solutions in polynomial time. Using such algorithms as building blocks, we propose heuristic algorithms to decompose the general service composition request graph into service composition request subgraphs with optimal structures. Simulation results demonstrate the effectiveness of the proposed heuristic algorithms.     

Simplicity in Eulerian circuits: Uniqueness and safety

An Eulerian circuit in a directed graph is one of the most fundamental Graph Theory notions. Detecting if a graph G has a unique Eulerian circuit can be done in polynomial time via the BEST theorem by de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte (1941–1951) [15], [16] (involving counting arborescences), or via a tailored characterization by Pevzner, 1989 (involving computing the intersection graph of simple cycles of G), both of which thus rely on overly complex notions for the simpler uniqueness problem.In this paper we give a new linear-time checkable characterization of directed graphs with a unique Eulerian circuit. This is based on a simple condition of when two edges must appear consecutively in all Eulerian circuits, in terms of cut nodes of the underlying undirected graph of G. As a by-product, we can also compute in linear-time all maximal safe walks appearing in all Eulerian circuits, for which Nagarajan and Pop proposed in 2009 [12] a polynomial-time algorithm based on Pevzner characterization.