Complexity results for minimum sum edge coloring

In the Minimum Sum Edge Coloring problem we have to assign positive integers to the edges of a graph such that adjacent edges receive different integers and the sum of the assigned numbers is minimal. We show that the problem is (a) NP-hard for planar bipartite graphs with maximum degree 3, (b) NP-hard for 3-regular planar graphs, (c) NP-hard for partial 2-trees, and (d) APX-hard for bipartite graphs.     

两类广义控制问题的NP-完全性

研究两类广义控制问题的复杂性: k-步长控制问题和k-距离控制问题, 证明了k-步长控制问题在弦图和平面二部图上都是NP-完全的. 作为上述结果的推论, 给出了k-距离控制问题在弦图和二部图上NP-完全性的新的证明, 并进一步证明了k-距离控制问题在平面二部图上也是NP-完全的.     

Polynomial kernels for 3-leaf power graph modification problems

A graph G=(V,E) is a 3-leaf power iff there exists a tree T the leaf set of which is V and such that uv∈E iff u and v are at distance at most 3 in T. The 3-leaf power graph edge modification problems, i.e. edition (also known as the closest 3-leaf power), completion and edge-deletion are FPT when parameterized by the size of the edge set modification. However, polynomial kernels were known for none of these three problems. For each of them, we provide kernels with O(k³) vertices that can be computed in linear time. We thereby answer an open problem first mentioned by Dom et al. (2004) [8].     

A short proof of the NP-completeness of minimum sum interval coloring

In the minimum sum coloring problem we have to assign positive integers to the vertices of a graph in such a way that neighbors receive different numbers and the sum of the numbers is minimized. Szkalicki has shown that minimum sum coloring is NP-hard for interval graphs. Here we present a simpler proof of this result.     

On star and caterpillar arboricity

We give new bounds on the star arboricity and the caterpillar arboricity of planar graphs with given girth. One of them answers an open problem of Gyárfás and West: there exist planar graphs with track number 4. We also provide new NP-complete problems.     

The complexity of detecting fixed-density clusters

We study the complexity of finding a subgraph of a certain size and a certain density, where density is measured by the average degree. Let γ:N→Q₊ be any density function, i.e., γ is computable in polynomial time and satisfies γ(k)?k-1 for all k∈N. Then γ-CLUSTER is the problem of deciding, given an undirected graph G and a natural number k, whether there is a subgraph of G on k vertices that has average degree at least γ(k). For γ(k)=k-1, this problem is the same as the well-known CLIQUE problem, and thus NP-complete. In contrast to this, the problem is known to be solvable in polynomial time for γ(k)=2. We ask for the possible functions γ such that γ-CLUSTER remains NP-complete or becomes solvable in polynomial time. We show a rather sharp boundary: γ CLUSTER is NP-complete if γ=2+Ω(1/k^1-ε) for some ε>0 and has a polynomial-time algorithm for γ=2+O(1/k). The algorithm also shows that for γ=2+O(1/k^1-o(1)), γ-CLUSTER is solvable in subexponential time 2^no(1).     

Edge decompositions into two kinds of graphs

Let H be an arbitrary graph and let K_1,2 be the 2-edge star. By a {K_1,2,H}-decomposition of a graph G we mean a partition of the edge set of G into subsets inducing subgraphs isomorphic to K_1,2 or H. Let J be an arbitrary connected graph of odd size. We show that the problem to decide if an instance graph G has a {K_1,2,H}-decomposition is NP-complete if H has a component of an odd size and H≠pK_1,2∪qJ, where pK_1,2∪qJ is the disjoint union of p copies of K_1,2 and q copies of J. Moreover, we prove polynomiality of this problem for H=qJ.     

Improved bounds on acyclic edge colouring

We prove that the acyclic chromatic index a^′(G)?6Δ for all graphs with girth at least 9. We extend the same method to obtain a bound of 4.52Δ with the girth requirement g?220. We also obtain a relationship between g and a^′(G).     

Searching for an edge in a graph with restricted test sets

Consider the (2,n) group testing problem with test sets of cardinality at most 2. We determine the worst case number c₂ of tests for this restricted group testing problem.Furthermore, using a game theory approach we solve the generalization of this group testing problem to the following search problem, which was suggested by Aigner in [M. Aigner, Combinatorial Search, Wiley-Teubner, 1988]: Suppose a graph G(V,E) contains one defective edge e. We search for the endpoints of e by asking questions of the form “Is at least one of the vertices of X an endpoint of e?”, where X is a subset of V with |X|≤2. What is the minimum number c₂(G) of questions, which are needed in the worst case to identify e?We derive sharp upper and lower bounds for c₂(G). We also show that the determination of c₂(G) is an NP-complete problem. Moreover, we establish some results on c₂ for random graphs.     

The external constraint 4 nonempty part sandwich problem

List partitions generalize list colourings. Sandwich problems generalize recognition problems. The polynomial dichotomy (NP-complete versus polynomial) of list partition problems is solved for 4-dimensional partitions with the exception of one problem (the list stubborn problem) for which the complexity is known to be quasipolynomial. Every partition problem for 4 nonempty parts and only external constraints is known to be polynomial with the exception of one problem (the 2K₂-partition problem) for which the complexity of the corresponding list problem is known to be NP-complete. The present paper considers external constraint 4 nonempty part sandwich problems. We extend the tools developed for polynomial solutions of recognition problems obtaining polynomial solutions for most corresponding sandwich versions. We extend the tools developed for NP-complete reductions of sandwich partition problems obtaining the classification into NP-complete for some external constraint 4 nonempty part sandwich problems. On the other hand and additionally, we propose a general strategy for defining polynomial reductions from the 2K₂-partition problem to several external constraint 4 nonempty part sandwich problems, defining a class of 2K₂-hard problems. Finally, we discuss the complexity of the Skew Partition Sandwich Problem.     

Open problems around exact algorithms

We list a number of open questions around worst case time bounds and worst case space bounds for NP-hard problems. We are interested in exponential time solutions for these problems with a relatively good worst case behavior. We summarize what is known on these problems, we discuss related results, and we provide pointers to the literature.     

The computational complexity of basic decision problems in 3-dimensional topology

We study the computational complexity of basic decision problems of 3-dimensional topology, such as to determine whether a triangulated 3-manifold is irreducible, prime, ∂-irreducible, or homeomorphic to a given 3-manifold M. For example, we prove that the problem to recognize whether a triangulated 3-manifold is homeomorphic to a 3-sphere, or to a 2-sphere bundle over a circle, or to a real projective 3-space, or to a handlebody of genus g, is decidable in nondeterministic polynomial time (NP) of size of the triangulation. We also show that the problem to determine whether a triangulated orientable 3-manifold is irreducible (or prime) is in PSPACE and whether it is ∂-irreducible is in coNP. The proofs improve and extend arguments of prior author’s article on the recognition problem for the 3-sphere.      

On the computational complexity of partial covers of Theta graphs

By use of elementary geometric arguments we prove the existence of a special integral solution of a certain system of linear equations. The existence of such a solution then yields the NP-hardness of the decision problem on the existence of locally injective homomorphisms to Theta graphs with three distinct odd path lengths.     

Approximating maximum edge 2-coloring in simple graphs

We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of roughly 0.842 and runs in O(n³m) time, where n (respectively, m) is the number of vertices (respectively, edges) in the input graph. The previously best ratio achieved by a polynomial-time approximation algorithm was .     

Multigraph realizations of degree sequences: Maximization is easy, minimization is hard

The following minimization problem is shown to be NP-hard: Given a graphic degree sequence, find a realization of this degree sequence as loopless multigraph that minimizes the number of edges in the underlying support graph. The corresponding maximization problem is known to be solvable in polynomial time.     

Complexity of the packing coloring problem for trees

Packing coloring is a partitioning of the vertex set of a graph with the property that vertices in the i-th class have pairwise distance greater than i. The main result of this paper is a solution of an open problem of Goddard et al. showing that the decision whether a tree allows a packing coloring with at most k classes is NP-complete.We further discuss specific cases when this problem allows an efficient algorithm. Namely, we show that it is decideable in polynomial time for graphs of bounded treewidth and diameter, and fixed parameter tractable for chordal graphs.We accompany these results by several observations on a closely related variant of the packing coloring problem, where the lower bounds on the distances between vertices inside color classes are determined by an infinite nondecreasing sequence of bounded integers.     

A note on two fixed point problems

We extend the applicability of the Exterior Ellipsoid Algorithm for approximating n-dimensional fixed points of directionally nonexpanding functions. Such functions model many practical problems that cannot be formulated in the smaller class of globally nonexpanding functions. The upper bound 2n²ln(2/) on the number of function evaluations for finding -residual approximations to the fixed points remains the same for the larger class. We also present a modified version of a hybrid bisection-secant method for efficient approximation of univariate fixed point problems in combustion chemistry.     

Regularity and perturbation results for mixed second order elliptic problems

We study a mixed boundary value problem for elliptic second order equations obtaining optimal regularity results under weak assumptions on the data. We also consider the dependence of the solution with respect to perturbations of the boundary sets carrying the Dirichlet and the Neumann conditions.