The firefighter problem for graphs of maximum degree three

We show that the firefighter problem is NP-complete for trees of maximum degree three, but in P for graphs of maximum degree three if the fire breaks out at a vertex of degree at most two.     

The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes

The exact weighted independent set (EWIS) problem consists in determining whether a given vertex-weighted graph contains an independent set of given weight. This problem is a generalization of two well-known problems, the NP-complete subset sum problem and the strongly NP-hard maximum weight independent set (MWIS) problem. Since the MWIS problem is polynomially solvable for some special graph classes, it is interesting to determine the complexity of this more general EWIS problem for such graph classes.We focus on the class of perfect graphs, which is one of the most general graph classes where the MWIS problem can be solved in polynomial time. It turns out that for certain subclasses of perfect graphs, the EWIS problem is solvable in pseudo-polynomial time, while on some others it remains strongly NP-complete. In particular, we show that the EWIS problem is strongly NP-complete for bipartite graphs of maximum degree three, but solvable in pseudo-polynomial time for cographs, interval graphs and chordal graphs, as well as for some other related graph classes.     

On Generating Triangle-Free Graphs

We show that the problem to decide whether a graph can be made triangle-free with at most k edge deletions remains NP-complete even when restricted to planar graphs of maximum degree seven. In addition, we provide polynomial-time data reduction rules for this problem and obtain problem kernels consisting of 6k vertices for general graphs and 11k/3 vertices for planar graphs.     

On maximum planar induced subgraphs

The nonplanar vertex deletion or vertex deletion vd(G) of a graph G is the smallest nonnegative integer k, such that the removal of k vertices from G produces a planar graph G^′. In this case G^′ is said to be a maximum planar induced subgraph of G. We solve a problem proposed by Yannakakis: find the threshold for the maximum degree of a graph G such that, given a graph G and a nonnegative integer k, to decide whether vd(G)?k is NP-complete. We prove that it is NP-complete to decide whether a maximum degree 3 graph G and a nonnegative integer k satisfy vd(G)?k. We prove that unless P=NP there is no polynomial-time approximation algorithm with fixed ratio to compute the size of a maximum planar induced subgraph for graphs in general. We prove that it is Max SNP-hard to compute vd(G) when restricted to a cubic input G. Finally, we exhibit a polynomial-time -approximation algorithm for finding a maximum planar induced subgraph of a maximum degree 3 graph.     

Partition the vertices of a graph into one independent set and one acyclic set

For a given graph G, if the vertices of G can be partitioned into an independent set and an acyclic set, then we call G a near-bipartite graph. This paper studies the recognition of near-bipartite graphs. We give simple characterizations for those near-bipartite graphs having maximum degree at most 3 and those having diameter 2. We also show that the recognition of near-bipartite graphs is NP-complete even for graphs where the maximum degree is 4 or where the diameter is 4.     

NP-completeness of 4-incidence colorability of semi-cubic graphs

The incidence coloring conjecture, proposed by Brualdi and Massey in 1993, states that the incidence coloring number of every graph is at most Δ+2, where Δ is the maximum degree of a graph. The conjecture was shown to be false in general by Guiduli in 1997, following the work of Algor and Alon. However, in 2005 Maydanskiy proved that the conjecture holds for any graph with Δ?3. It is easily deduced that the incidence coloring number of a semi-cubic graph is 4 or 5. In this paper, we show that it is already NP-complete to determine if a semi-cubic graph is 4-incidence colorable, and therefore it is NP-complete to determine if a general graph is k-incidence colorable.     

Polynomial recognition of equal unions in hypergraphs with few vertices of large degree

A family of nonempty sets has the equal union property if there exist two nonempty disjoint subfamilies having equal unions. If every point belongs to the unions, then we say the family has the full equal union property. Recognition of both properties is NP-complete even when restricted to families for which the degree of every point is at most three. In this paper we show that both recognition problems can be solved in polynomial time for families in which there is a bound on the number of points whose degree exceeds two.     

A note on graphs spanned by Eulerian graphs

We show that the problem raised by Boesch, Suffel, and Tindell of determining whether or not a graph is spanned by an Eulerian subgraph is NP-complete. We also note that there does exist a good algorithm for determining if a graph is spanned by a subgraph having positive even degree at every node.     

Graphs with homeomorphically irreducible spanning trees

It is an NP-complete problem to decide whether a graph contains a spanning tree with no vertex of degree 2. We show that these homeomorphically irreducible spanning trees are contained in all graphs with minimum degree at least c√n and in triangulations of the plane. They are nearly present in all graphs of diameter 2. They do not necessarily occur in r-regular or r-connected graphs.     

Plane Graphs with Parity Constraints

Let S be a set of n points in general position in the plane. Together with S we are given a set of parity constraints, that is, every point of S is labeled either even or odd. A graph G on S satisfies the parity constraint of a point ${p\in S}$ if the parity of the degree of p in G matches its label. In this paper, we study how well various classes of planar graphs can satisfy arbitrary parity constraints. Specifically, we show that we can always find a plane tree, a two-connected outerplanar graph, or a pointed pseudo-triangulation that satisfy all but at most three parity constraints. For triangulations we can satisfy about 2/3 of the parity constraints and we show that in the worst case there is a linear number of constraints that cannot be fulfilled. In addition, we prove that for a given simple polygon H with polygonal holes on S, it is NP-complete to decide whether there exists a triangulation of H that satisfies all parity constraints.     

Deciding Frattini is NP-complete

We show that it is a NP-complete problem to decide whether a finite poset arises as the (Birkhoff) dual of the Frattini sublattice of some finite distributive lattice.This work was supported in part by Swiss NSF grant 20-32644.91.     

On Bipartite and Multipartite Clique Problems

In this paper, we introduce the maximum edge biclique problem in bipartite graphs and the edge/node weighted multipartite clique problem in multipartite graphs. Our motivation for studying these problems came from abstractions of real manufacturing problems in the computer industry and from formal concept analysis. We show that the weighted version and four variants of the unweighted version of the biclique problem are NP-complete. For random bipartite graphs, we show that the size of the maximum balanced biclique is considerably smaller than the size of the maximum edge cardinality biclique, thus highlighting the difference between the two problems. For multipartite graphs, we consider three versions each for the edge and node weighted problems which differ in the structure of the multipartite clique (MPC) required. We show that all the edge weighted versions are NP-complete in general. We also provide a special case in which edge weighted versions are polynomially solvable.     

Some remarks on the geodetic number of a graph

A set of vertices D of a graph G is geodetic if every vertex of G lies on a shortest path between two not necessarily distinct vertices in D. The geodetic number of G is the minimum cardinality of a geodetic set of G.We prove that it is NP-complete to decide for a given chordal or chordal bipartite graph G and a given integer k whether G has a geodetic set of cardinality at most k. Furthermore, we prove an upper bound on the geodetic number of graphs without short cycles and study the geodetic number of cographs, split graphs, and unit interval graphs.     

Hamiltonian index is NP-complete

In this paper we show that the problem to decide whether the hamiltonian index of a given graph is less than or equal to a given constant is NP-complete (although this was conjectured to be polynomial). Consequently, the corresponding problem to determine the hamiltonian index of a given graph is NP-hard. Finally, we show that some known upper and lower bounds on the hamiltonian index can be computed in polynomial time.     

Computational complexity of some restricted instances of 3-SAT

Tovey [A simplified satisfiability problem, Discrete Appl. Math. 8 (1984) 85-89] showed that it is NP-hard to decide the satisfiability of 3-SAT instances in which every variable occurs four times, while every instance of 3-SAT in which each variable occurs three times is satisfiable. We explore the border between these two problems. Answering a question of Iwama and Takaki, we show that, for every fixed k?0, there is a polynomial-time algorithm to determine the satisfiability of 3-SAT instances in which k variables occur four times and the remaining variables occur three times. On the other hand, it is NP-hard to decide the satisfiability of 3-SAT instances in which all but one variable occurs three times, and the remaining variable is allowed to occur an arbitrary number of times.     

On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs

Clique-Helly and hereditary clique-Helly graphs are polynomial-time recognizable. Recently, we presented a proof that the clique graph recognition problem is NP-complete [L. Alcón, L. Faria, C.M.H. de Figueiredo, M. Gutierrez, Clique graph recognition is NP-complete, in: Proc. WG 2006, in: Lecture Notes in Comput. Sci., vol. 4271, Springer, 2006, pp. 269-277]. In this work, we consider the decision problems: given a graph G=(V,E) and an integer k≥0, we ask whether there exists a subset V^′⊆V with |V^′|≥k such that the induced subgraph G[V^′] of G is, variously, a clique, clique-Helly or hereditary clique-Helly graph. The first problem is clearly NP-complete, from the above reference; we prove that the other two decision problems mentioned are NP-complete, even for maximum degree 6 planar graphs. We consider the corresponding maximization problems of finding a maximum induced subgraph that is, respectively, clique, clique-Helly or hereditary clique-Helly. We show that these problems are Max SNP-hard, even for maximum degree 6 graphs. We show a general polynomial-time -approximation algorithm for these problems when restricted to graphs with fixed maximum degree Δ. We generalize these results to other graph classes. We exhibit a polynomial 6-approximation algorithm to minimize the number of vertices to be removed in order to obtain a hereditary clique-Helly subgraph.     

图的导出森林2-划分

对一个给定的简单图Ｇ，是否存在Ｖ（Ｇ）的一个２－划分（Ｖ１，Ｖ２）使得每个导出子图Ｇ［Ｖｉ］为森林？称该问题为导出森林２－划分问题．本文证明了对最大度为５的图该问题是ＮＰ－完全的，而对最大度≤４的图该问题多项式时间可解．     

Recognizing decomposable graphs

A graph is called decomposable if its vertices can be colored red and blue in such a way that each color appears on at least one vertex but each vertex v has at most one neighbor having a different color from v. We point out a simple and efficient algorithm for recognizing decomposable graphs with maximum degree at most 3 and prove that recognizing decomposable graphs with maximum degree 4 is an NP-complete problem.     

On the maximum cardinality search lower bound for treewidth

The Maximum Cardinality Search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS algorithm. The visited degree of a vertex v in an MCS-ordering is the number of neighbours of v that are before v in the ordering. The visited degree of an MCS-ordering ψ of G is the maximum visited degree over all vertices v in ψ. The maximum visited degree over all MCS-orderings of graph G is called its maximum visited degree. Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345-353] showed that the treewidth of a graph G is at least its maximum visited degree.We show that the maximum visited degree is of size O(logn) for planar graphs, and give examples of planar graphs G with maximum visited degree k with O(k!) vertices, for all k∈N. Given a graph G, it is NP-complete to determine if its maximum visited degree is at least k, for any fixed k?7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.