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.
10937579
Eliminating graphs by means of parallel knock-out schemes
In 1997 Lampert and Slater introduced parallel knock-out schemes, an iterative process on graphs that goes through several rounds. In each round of this process, every vertex eliminates exactly one of its neighbors. The parallel knock-out number of a graph is the minimum number of rounds after which all vertices have been eliminated (if possible). The parallel knock-out number is related to well-known concepts like perfect matchings, hamiltonian cycles, and 2-factors. We derive a number of combinatorial and algorithmic results on parallel knock-out numbers: for families of sparse graphs (like planar graphs or graphs of bounded tree-width), the parallel knock-out number grows at most logarithmically with the number n of vertices; this bound is basically tight for trees. Furthermore, there is a family of bipartite graphs for which the parallel knock-out number grows proportionally to the square root of n. We characterize trees with parallel knock-out number at most 2, and we show that the parallel knock-out number for trees can be computed in polynomial time via a dynamic programming approach (whereas in general graphs this problem is known to be NP-hard). Finally, we prove that the parallel knock-out number of a claw-free graph is either infinite or less than or equal to 2.
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.
11379371
Partitioning Graphs into Two Trees
14343122
Backbone Colorings for Networks
We study backbone colorings, a variation on classical vertex colorings: Given a graph G=(V,E) and a spanning subgraph H (the backbone) of G, a backbone coloring for G and H is a proper vertex coloring V →{ 1,2,... } in which the colors assigned to adjacent vertices in H differ by at least two. We concentrate on the cases where the backbone is either a spanning tree or a spanning path.
5145089
A faster off-line algorithm for the TCP acknowledgement problem
In a recent paper [Proceedings of STOC'98, 1998, pp. 389-398], Dooly, Goldman and Scott study a problem that is motivated by the networking problem of dynamically adjusting delays of acknowledgements in the Transmission Control Protocol (TCP). Among other results, they give an O(n2) off-line algorithm for computing the optimal way of acknowledging n packet arrivals and departures.In this brief note, we observe that there is a faster off-line algorithm for this problem with time complexity O(n).
22610152
Counting k-Subsets and Convex k-gons in the Plane
We consider problems of the following type: Let S be a set of n points in the plane, let p be some point in S and let K be an integer, 3≤k≤n. We show how to compute the overall number of convex k-gons with corners at points in S, for any fixed k≥4.
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.
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)).