This paper studies generalized variants of the MAXIMUM INDEPENDENT SET problem, called the MAXIMUM DISTANCE-d INDEPENDENT SET problem (MaxDdIS for short). For an integer d≥2, a distance-d independent set of an unweighted graph G=(V, E) is a subset S⊆V of vertices such that for any pair of vertices u, v∈S, the number of edges in any path between u and v is at least d in G. Given an unweighted graph G, the goal of MaxDdIS is to find a maximum-cardinality distance-d independent set of G. In this paper, we analyze the (in)approximability of the problem on r-regular graphs (r≥3) and planar graphs, as follows: (1) For every fixed integers d≥3 and r≥3, MaxDdIS on r-regular graphs is APX-hard. (2) We design polynomial-time O(rd-1)-approximation and O(rd-2/d)-approximation algorithms for MaxDdIS on r-regular graphs. (3) We sharpen the above O(rd-2/d)-approximation algorithms when restricted to d=r=3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxDdIS admits a polynomial-time approximation scheme (PTAS) for planar graphs.

In this paper, we study a variant of the MINIMUM DOMINATING SET problem. Given an unweighted undirected graph G=(V,E) of n=|V| vertices, the goal of the MINIMUM SINGLE DOMINATING CYCLE problem (MinSDC) is to find a single shortest cycle which dominates all vertices, i.e., a cycle C such that for the set V(C) of vertices in C and the set N(V(C)) of neighbor vertices of C, V(G)=V(C)∪N(V(C)) and |V(C)| is minimum over all dominating cycles in G [6], [17], [24]. In this paper we consider the (in)approximability of MinSDC if input graphs are restricted to some special classes of graphs. We first show that MinSDC is still NP-hard to approximate even when restricted to planar, bipartite, chordal, or r-regular (r≥3). Then, we show the (lnn+1)-approximability and the (1-ε)lnn-inapproximability of MinSDC on split graphs under P≠NP. Furthermore, we explicitly design a linear-time algorithm to solve MinSDC for graphs with bounded treewidth and estimate the hidden constant factor of its running time-bound.

Suppose that each arc in a digraph D = (V,A) has two costs of non-negative integers, called a spine cost and a leaf cost. A caterpillar is a directed tree consisting of a single directed path (of spine arcs) and leaf vertices each of which is incident to the directed path by exactly one incoming arc (leaf arc). For a given terminal set K ⊆ V, we study the problem of finding a caterpillar in D such that it contains all terminals in K and its total cost is minimized, where the cost of each arc in the caterpillar depends on whether it is used as a spine arc or a leaf arc. In this paper, we first show that the problem is NP-hard for any fixed constant number of terminals with |K| ≥ 3, while it is solvable in polynomial time for at most two terminals. We also give an inapproximability result for any fixed constant number of terminals with |K| ≥ 3. Finally, we give a linear-time algorithm to solve the problem for digraphs with bounded treewidth, where the treewidth for a digraph D is defined as the one for the underlying graph of D. Our algorithm runs in linear time even if |K| = O(|V|), and the hidden constant factor of the running time is just a single exponential of the treewidth.

Given a connected graph G = (V, E) on n vertices, the MAXIMUM r-REGULAR INDUCED CONNECTED SUBGRAPH (r-MaxRICS) problem asks for a maximum sized subset of vertices S ⊆ V such that the induced subgraph G[S] on S is connected and r-regular. It is known that 2-MaxRICS and 3-MaxRICS are NP-hard. Moreover, 2-MaxRICS cannot be approximated within a factor of n1-ε in polynomial time for any ε > 0 unless P= NP. In this paper, we show that r-MaxRICS are NP-hard for any fixed integer r ≥ 4. Furthermore, we show that for any fixed integer r ≥ 3, r-MaxRICS cannot be approximated within a factor of n1/6-ε in polynomial time for any ε > 0 unless P= NP.

For a graph G, a biclique edge partition SBP(G) is a collection of bicliques (complete bipartite subgraphs) Bi such that each edge of G is contained in exactly one Bi. The Minimum Biclique Edge Partition Problem (MBEPP) asks for SBP(G) with the minimum size. In this paper, we show that for arbitrary small ε>0, (6053/6052-ε)-approximation of MBEPP is NP-hard.

For a property π on graphs, the edge-contraction problem with respect to π is defined as a problem of finding a set of edges of minimum cardinality whose contraction results in a graph satisfying the property π. This paper gives a lower bound for the approximation ratio for the problem for any property π that is hereditary on contractions and determined by biconnected components.

Semistructured data comprises irregular structure and has no a-priori database schema, therefore we encounter several problems such as inefficient data retrieval and wasteful data storage. To cope with such problems, some schema extraction algorithms over semistructured data have been proposed, in which data is modeled as an unordered tree. However, the order of elements is indispensable for document data, therefore we consider extracting an optimal database schema over an ordered tree. We consider an optimization problem to extract a smallest database schema such that the density of each class is no less than a given threshold, where the density of a class represents a similarity between the type of the class and those of the objects in the class. We first prove that the corresponding decision problem is strongly NP-complete, and show that another version of the problem is strongly NP-hard and belongs to Δ2 P. Then we show that for any r < 3/2, there is no polynomial-time r-approximation algorithm that solves the optimization problem unless P = NP. Finally, we propose a kind of class called bounded class that can be constructed efficiently, then show a polynomial-time algorithm for constructing a database schema by using bounded classes.

The Task-Coalition Assignment Problem (TCAP) is a formalization of the distributed computation problem. In TCAP, a set of agents and a set of tasks are given. A subset of the agents processes a task to produce benefit. The goal of TCAP is to find the combination of the tasks and the subsets of the agents that maximizes the sum of the benefit. In this paper, we define 1-TCAP, which is a practical subclass of TCAP. In 1-TCAP, tasks and agents are characterized by scalar values. We propose a polynomial-time approximation algorithm for 1-TCAP, and show that this algorithm achieves an approximation ratio 9/4. Here, an algorithm achieves an approximation ratio α for a maximization problem if, for every instance, it produces a solution of value at least OPT/α, where OPT is the value of the optimal solution.