On maximum induced matchings in bipartite graphs

The problem of finding a maximum induced matching is known to be NP-hard in general bipartite graphs. We strengthen this result by reducing the problem to some special classes of bipartite graphs such as bipartite graphs with maximum degree 3 or C₄-free bipartite graphs. On the other hand, we describe a new polynomially solvable case for the problem in bipartite graphs which deals with a generalization of bi-complement reducible graphs.     

Locating a tree in a phylogenetic network

Phylogenetic trees and networks are leaf-labelled graphs that are used to describe evolutionary histories of species. The Tree Containment problem asks whether a given phylogenetic tree is embedded in a given phylogenetic network. Given a phylogenetic network and a cluster of species, the Cluster Containment problem asks whether the given cluster is a cluster of some phylogenetic tree embedded in the network. Both problems are known to be NP-complete in general. In this article, we consider the restriction of these problems to several well-studied classes of phylogenetic networks. We show that Tree Containment is polynomial-time solvable for normal networks, for binary tree-child networks, and for level-k networks. On the other hand, we show that, even for tree-sibling, time-consistent, regular networks, both Tree Containment and Cluster Containment remain NP-complete.     

Parameterized Complexity of the Spanning Tree Congestion Problem

We study the problem of determining the spanning tree congestion of a?graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for every fixed k. We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k??8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for k??3 the problem becomes polynomially time solvable.     

Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs

A spanning tree T of a graph G=(V,E) is called a locally connected spanning tree if the set of all neighbors of v in T induces a connected subgraph of G for all v∈V. The problem of recognizing whether a graph admits a locally connected spanning tree is known to be NP-complete even when the input graphs are restricted to chordal graphs. In this paper, we propose linear time algorithms for finding locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs, respectively.     

Rainbow graph splitting

Given an integer c, an edge colored graph G is said to be rainbow c-splittable if it can be decomposed into at most c vertex-disjoint monochromatic induced subgraphs of distinct colors. We provide a polynomial-time algorithm for deciding whether an edge-colored complete graph is rainbow c-splittable. For not necessarily complete graphs, we show that the problem is polynomial if c=2, whereas for c≥3 it is NP-complete even if the graph has maximum degree 2c−1. Finally, it remains NP-complete even for 2-edge colored graphs of maximum degree 7c−14.     

On the complexity of signed and minus total domination in graphs

In this paper we present unified methods to solve the minus and signed total domination problems for chordal bipartite graphs and trees in O(n²) and O(n+m) time, respectively. We also prove that the decision problem for the signed total domination problem on doubly chordal graphs is NP-complete. Note that bipartite permutation graphs, biconvex bipartite graphs, and convex bipartite graphs are subclasses of chordal bipartite graphs.     

On the k-path partition of graphs

The k-path partition problem is to partition a graph into the minimum number of paths, so that none of them has length more than k, for a given positive integer k. The problem is a generalization of the Hamiltonian path problem and the problem of partitioning a graph into the minimum number of paths. The k-path partition problem remains NP-complete on the class of chordal bipartite graphs if k is part of the input, and we show that it is NP-complete on the class of comparability graphs even for k=3. On the positive side, we present a polynomial-time solution for the problem, with any k, on bipartite permutation graphs, which form a subclass of chordal bipartite graphs.     

Editing to Eulerian graphs

The Eulerian Editing problem asks, given a graph G and an integer k, whether G can be modified into an Eulerian graph using at most k edge additions and edge deletions. We show that this problem is polynomial-time solvable for both undirected and directed graphs. We generalize these results for problems with degree parity constraints and degree balance constraints, respectively. We also consider the variants where vertex deletions are permitted. Combined with known results, this leads to full complexity classifications for both undirected and directed graphs and for every subset of the three graph operations.     

Tree Spanners for Bipartite Graphs and Probe Interval Graphs

A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of vertices in T is at most t times their distance in G. The tree t-spanner problem asks whether a graph admits a tree t-spanner, given t. We first substantially strengthen the known results for bipartite graphs. We prove that the tree t-spanner problem is NP-complete even for chordal bipartite graphs for t ≥ 5, and every bipartite ATE-free graph has a tree 3-spanner, which can be found in linear time. The previous best known results were NP-completeness for general bipartite graphs, and that every convex graph has a tree 3-spanner. We next focus on the tree t-spanner problem for probe interval graphs and related graph classes. The graph classes were introduced to deal with the physical mapping of DNA. From a graph theoretical point of view, the classes are natural generalizations of interval graphs. We show that these classes are tree 7-spanner admissible, and a tree 7-spanner can be constructed in (m log n) time.     

Some results on graphs without long induced paths

Many NP-hard graph problems remain difficult on P_k-free graphs for certain values of k. Our goal is to distinguish subclasses of P_k-free graphs where several important graph problems can be solved in polynomial time. In particular, we show that the independent set problem is polynomial-time solvable in the class of (P_k,K_1,n)-free graphs for any positive integers k and n, thereby generalizing several known results.     

Partition Into Triangles on Bounded Degree Graphs

We consider the Partition Into Triangles problem on bounded degree graphs. We show that this problem is polynomial-time solvable on graphs of maximum degree three by giving a linear-time algorithm. We also show that this problem becomes $\mathcal{NP}$ -complete on graphs of maximum degree four. Moreover, we show that there is no subexponential-time algorithm for this problem on graphs of maximum degree four unless the Exponential-Time Hypothesis fails. However, the Partition Into Triangles problem on graphs of maximum degree at most four is in many cases practically solvable as we give an algorithm for this problem that runs in $\mathcal{O}(1.02220^{n})$ time and linear space.     

Letter to the editor

The maximal-cut problem for directed graphs can be defined analogously to that for the undirected case. The undirected problem is known to be NP-complete. We consider two directed variants of the problem. Depending on the definition of the value of a cut, the resulting problem for general directed graphs is either efficiently solvable or NP-complete. We show that the latter version of the problem remains NP-complete when restricted to acyclic directed graphs. Further restriction to directed trees yields an efficiently solvable problem. We present an algorithm solving the problem in time proportional to the size of the input.     

Complexity of a proposed database storage structure

An alternate method for storing M to N relationships is presented. Implementing this method involves a minimization procedure which is shown to be equivalent to finding the minimal number of bipartite cliques which cover all of the edges of a related bipartite graph. This bipartite edge clique cover problem is known to be NP-complete, suggesting that attention should be focused on finding heuristic, not necessarily optimal, algorithms which produce solutions in polynomial-time. One such heuristic is presented which seems to work well on a variety of bipartite graphs. However, there are bipartite graphs for which its performance is poor, i.e. the heuristic produces solutions significantly worse than optimum. A family of bipartite graphs is presented for which the performance factor is unbounded.     

Updating the complexity status of coloring graphs without a fixed induced linear forest

A graph is H-free if it does not contain an induced subgraph isomorphic to the graph H. The graph P_k denotes a path on k vertices. The ?-Coloring problem is the problem to decide whether a graph can be colored with at most ? colors such that adjacent vertices receive different colors. We show that 4-Coloring is NP-complete for P₈-free graphs. This improves a result of Le, Randerath, and Schiermeyer, who showed that 4-Coloring is NP-complete for P₉-free graphs, and a result of Woeginger and Sgall, who showed that 5-Coloring is NP-complete for P₈-free graphs. Additionally, we prove that the precoloring extension version of 4-Coloring is NP-complete for P₇-free graphs, but that the precoloring extension version of 3-Coloring can be solved in polynomial time for (P₂+P₄)-free graphs, a subclass of P₇-free graphs. Here P₂+P₄ denotes the disjoint union of a P₂ and a P₄. We denote the disjoint union of s copies of a P₃ by sP₃ and involve Ramsey numbers to prove that the precoloring extension version of 3-Coloring can be solved in polynomial time for sP₃-free graphs for any fixed s. Combining our last two results with known results yields a complete complexity classification of (precoloring extension of) 3-Coloring for H-free graphs when H is a fixed graph on at most 6 vertices: the problem is polynomial-time solvable if H is a linear forest; otherwise it is NP-complete.     

Finding vertex-surjective graph homomorphisms

The Surjective Homomorphism problem is to test whether a given graph G called the guest graph allows a vertex-surjective homomorphism to some other given graph H called the host graph. The bijective and injective homomorphism problems can be formulated in terms of spanning subgraphs and subgraphs, and as such their computational complexity has been extensively studied. What about the surjective variant? Because this problem is NP-complete in general, we restrict the guest and the host graph to belong to graph classes \({{\mathcal G}}\) and \({{\mathcal H}}\), respectively. We determine to what extent a certain choice of \({{\mathcal G}}\) and \({{\mathcal H}}\) influences its computational complexity. We observe that the problem is polynomial-time solvable if \({{\mathcal H}}\) is the class of paths, whereas it is NP-complete if \({{\mathcal G}}\) is the class of paths. Moreover, we show that the problem is even NP-complete on many other elementary graph classes, namely linear forests, unions of complete graphs, cographs, proper interval graphs, split graphs and trees of pathwidth at most 2. In contrast, we prove that the problem is fixed-parameter tractable in k if \({{\mathcal G}}\) is the class of trees and \({{\mathcal H}}\) is the class of trees with at most k leaves, or if \({{\mathcal G}}\) and \({{\mathcal H}}\) are equal to the class of graphs with vertex cover number at most k.     

The Longest Path Problem Is Polynomial on Cocomparability Graphs

The longest path problem is the problem of finding a path of maximum length in a graph. As a generalization of the Hamiltonian path problem, it is NP-complete on general graphs and, in fact, on every class of graphs that the Hamiltonian path problem is NP-complete. Polynomial solutions for the longest path problem have recently been proposed for weighted trees, Ptolemaic graphs, bipartite permutation graphs, interval graphs, and some small classes of graphs. Although the Hamiltonian path problem on cocomparability graphs was proved to be polynomial almost two decades ago, the complexity status of the longest path problem on cocomparability graphs has remained open; actually, the complexity status of the problem has remained open even on the smaller class of permutation graphs. In this paper, we present a polynomial-time algorithm for solving the longest path problem on the class of cocomparability graphs. Our result resolves the open question for the complexity of the problem on such graphs, and since cocomparability graphs form a superclass of both interval and permutation graphs, extends the polynomial solution of the longest path problem on interval graphs and provides polynomial solution to the class of permutation graphs.     

Isomorphic tree spanner problems

A treet-spanner, wheret is a positive integer, of a graph G is a spanning tree in which the distance between the two ends of every edge ofG is at mostt. This notion is motivated by applications in distributed systems and communication networks. This paper is concerned with the problem of determining whether a graph contains a tree t-spanner isomorphic to a given tree. It is shown that the problem fort=2 is solvable in O(n^3.5) time for 2-connected graphs, whereas the problem for any fixed integert 3 is NP-complete, even for 2-connected bipartite graphs.Financial support for this research was received from the Natural Sciences and Engineering Research Council of Canada.     

On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs

In this paper we show that the problem of finding a chordless path between a vertex $s$ and a vertex $t$ containing a vertex $v$ remains NP-complete in bipartite graphs, thereby strengthening the previous results on the same problem. We show a relation between this problem and two interval operators: the simple path interval operator in hypergraphs and the even-chorded path interval operator in graphs. We show that the problem of computing the two mentioned intervals is NP-complete.     

Tractable cases of the extended global cardinality constraint

We study the consistency and domain consistency problem for extended global cardinality (EGC) constraints. An EGC constraint consists of a set X of variables, a set D of values, a domain D(x) í DD(x) \subseteq D for each variable x, and a “cardinality set” K(d) of non-negative integers for each value d. The problem is to instantiate each variable x with a value in D(x) such that for each value d, the number of variables instantiated with d belongs to the cardinality set K(d). It is known that this problem is NP-complete in general, but solvable in polynomial time if all cardinality sets are intervals. First we pinpoint connections between EGC constraints and general factors in graphs. This allows us to extend the known polynomial-time case to certain non-interval cardinality sets. Second we consider EGC constraints under restrictions in terms of the treewidth of the value graph (the bipartite graph representing variable-value pairs) and the cardinality-width (the largest integer occurring in the cardinality sets). We show that EGC constraints can be solved in polynomial time for instances of bounded treewidth, where the order of the polynomial depends on the treewidth. We show that (subject to the complexity theoretic assumption  FPT ≠ W[1]) this dependency cannot be avoided without imposing additional restrictions. If, however, also the cardinality-width is bounded, this dependency gets removed and EGC constraints can be solved in linear time.