28023212
The Steiner Tree Problem in Kalmanson Matrices and in Circulant Matrices
AbstractWe investigate the computational complexity of two special cases of the Steiner tree problem where the distance matrix is a Kalmanson matrix or a circulant matrix, respectively. For Kalmanson matrices we develop an efficient polynomial time algorithm that is based on dynamic programming. For circulant matrices we give an 
$$\mathcal{N}\mathcal{P}$$
-hardness proof and thus establish computational intractability.
11379371
Partitioning Graphs into Two Trees
6054148
Hamiltonian cycles in circulant digraphs with two stripes
Abstract The circulant traveling salesman problem ( CTSP ) is the problem of finding a minimum weight Hamiltonian cycle in a weighted graph with circulant distance matrix. The computational complexity of this problem is not known. In fact, even the complexity of deciding Hamiltonicity of the underlying graph is unknown. This paper provides a characterization of Hamiltonian digraphs with circulant distance matrix containing only two nonzero stripes . The corresponding conditions can be checked in polynomial time. Secondly, we show that all Hamiltonian cycles of a circulant 2-digraph are periodic. Based on these two results, a method for enumerating all Hamiltonian cycles in such digraphs is described. Moreover, two simple algorithms are derived for solving the sum and bottleneck versions of CTSP for circulant distance matrices with two nonzero stripes.
431690
Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult
AbstractWe consider the problem of coloring a planar graph with the
minimum number of colors so that each color class avoids one or
more forbidden graphs as subgraphs. We perform a detailed study of
the computational complexity of this problem. We present a complete picture for the case with a single forbidden
connected (induced or noninduced) subgraph. The 2-coloring
problem is NP-hard if the forbidden subgraph is a tree with at
least two edges, and it is polynomially solvable in all other
cases. The 3-coloring problem is NP-hard if the forbidden
subgraph is a path with at least one edge, and it is polynomially solvable in all other
cases. We also derive results for several forbidden sets of
cycles. In particular, we prove that it is NP-complete to decide if a planar
graph can be 2-colored so that no cycle of length at most 5 is
monochromatic.
17103586
The complexity of coloring graphs without long induced paths
We discuss the computational complexity of determining the chromatic number of graphs without long induced paths. We prove NP-completeness of deciding whether a Ps-free graph is 5-colorable and of deciding whether a Pi2-free graph is 4-colorable. Moreover, we give a polynomial time algorithm for deciding whether a Ps-free graph is 3-colorable.
44716494
Polynomial Graph-Colorings
For directed graphs G and H, we say that G is H-colorable, if there is a graph homomorphism from G into H; that is, there is a mapping f from the vertex set of G into the vertex set of H such that whenever there is an edge (x, y) in G, then (f(x), f(y)) is an edge in H. We introduce a new technique for proving that the H-coloring problem is polynomial time decidable for some fixed graphs H. Among others, this is the case if H is a semipath (a “path” with edges directed in either direction), which has not been known before. We also show the existence of a tree T, for which the T-coloring problem is NP-complete.
15492927
Counting Convex Polygons in Planar Point Sets
Given a set S of n points in the plane, we compute in time O(n3) the total number of convex polygons whose vertices are a subset of S. We give an O(m · n3) algorithm for computing the number of convex k-gons with vertices in S, for all values k = 3,…, m; previously known bounds were exponential (O(nk/2). We also compute the number of empty convex polygons (resp.,k-gons, k m) with vertices in S in time O(n3) (resp., O(m · n3)).
43889321
It is tough to be a plumber
In the Linux computer game KPlumber, the objective is to rotate tiles in a raster of squares so as to complete a system of pipes. We give a complexity classification for the original game and various special cases of it that arise from restricting the set of six possible tiles.Most of the cases are NP-complete. One polynomially solvable case is settled by formulating it as a perfect matching problem; other polynomial cases are settled by simple sweepline techniques. Moreover, we show that all the unsettled cases are polynomial time equivalent.