Narrow Results

We present a modification of Bodlaender's linear time algorithm that, for constant k, determine whether an input graph G has treewidth k and, if so, constructs a tree decomposition of G of width at most k. Our algorithm has the following additional feature: if G has treewidth greater than k then a subgraph G′ of G of treewidth greater than k is returned along with a tree decomposition of G′ of width at most 2k. A consequence is that the fundamental disjoint rooted paths problem can now be solved in O(n²) time. This is the primary motivation of this paper.

Let G be a k-tree such that |{v ∈ V(G): deg_G(v) = k}| = 2, n = |V(G)| ≥ 2k + 2, and the maximum degree of G is at most 2k. In this paper, we will show that such a k-tree G is isomorphic to P_n,k. In this way, we give a new characterization of k-th power (i.e. P_n,k) of paths with n vertices in terms of k-trees.

We consider the maximum common connected edge subgraph problem and the maximum common connected induced subgraph problem for simple graphs with labeled vertices (or labeled edges). The former is to find a connected graph with the maximum number of edges that is isomorphic to a subgraph of each of the two input graphs. The latter is to find a common connected induced subgraph with the maximum number of vertices. We prove that both problems are NP-hard for 3-outerplanar labeled graphs even if the maximum vertex degree is bounded by 4. Since the reductions used in the proofs construct graphs with treewidth at most 4, both problems are NP-hard also for such graphs, which significantly improves the previous hardness results for graphs with treewidth 11. We also present improved exponential-time algorithms for both problems on labeled graphs of bounded treewidth and bounded vertex degree.

In this paper we show that the treewidth of a circle graph can be computed in polynomial time. A circle graph is a graph that is isomorphic to the intersection graph of a finite collection of chords of a circle. The TREEWIDTH problem can be viewed upon as the problem of finding a chordal embedding of the graph that minimizes the clique number. Our algorithm to determine the treewidth of a circle graph can be implemented to run in O(n³) time, where n is the number of vertices of the graph.

A graph $G$ is a 3-degree 4-chordal graph if every cycle of length at least five has a chord and the degree of each vertex is at most three. In this paper, we investigate the structure of 3-degree 4-chordal graphs, which is a subclass of 3-degree graphs. We present a structural characterization based on minimal vertex separators and bi-connected components. Many classical problems are known to be NP-complete for 3-degree graphs, and 3-degree 4-chordal graphs are a nontrivial subclass of 3-degree graphs. Using our structural results, we present polynomial-time algorithms for many classical problems which are grouped into (i) subset problems (vertex cover and its variants, feedback vertex set, Steiner tree), (ii) Hamiltonicity and its variants, (iii) graph embedding problems (treewidth, minimum fill-in), and (iv) Coloring problems(rainbow coloring).