Search

Abstract Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis and Yannakakis gives a complete dichotomy of their complexity. It however has nothing to say about the case when the input graph is also special. This paper initiates a systematic study of vertex deletion problems from one subclass of chordal graphs to another. We give polynomial-time algorithms or proofs of NP-completeness for most of the problems. In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete. [ABSTRACT FROM AUTHOR]

In the field of parameterized counting complexity, the problems that are #W[1]-hard and admit fixed-parameter tractable randomized approximation scheme (FPTRAS) have attracted much attention in recent years. In this paper, we focus on the problems on parameterized counting matching and packing. These problems include counting set packing , counting matching , and counting subgraph packing (including both vertex-disjoint and edge-disjoint versions). We study the parameterized complexity on these problems. On the basis of some results for counting graph matchings, we show that a series of problems are #W[1]-hard. Furthermore, by extending the previous algorithm for counting 3- d matching , we obtain FPTRAS for each considered problem, respectively. Our results indicate that the problems on parameterized counting matching and packing form a large family of problems that are #W[1]-hard and admit FPTRAS. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study the geodetic convexity of graphs, focusing on the problem of the complexity of computing a minimum hull set of a graph in several graph classes. For any two vertices of a connected graph , the closed interval of and is the set of vertices that belong to some shortest -path. For any , let . A subset is geodesically convex or convex if . In other words, a subset is convex if, for any and for any shortest -path , . Given a subset , the convex hull of is the smallest convex set that contains . We say that is a hull set of if . The size of a minimum hull set of is the hull number of , denoted by . The Hull Number problem is to decide whether , for a given graph and an integer . Dourado et al. showed that this problem is NP-complete in general graphs. In this paper, we answer an open question of Dourado et al. (2009) [1] by showing that the Hull Number problem is NP-hard even when restricted to the class of bipartite graphs. Then, we design polynomial-time algorithms to solve the Hull Number problem in several graph classes. First, we deal with the class of complements of bipartite graphs. Then, we generalize some results in Araujo et al. (2011) [2] to the class of -graphs and to cacti. Finally, we prove tight upper bounds on the hull numbers. In particular, we show that the hull number of an -node graph without simplicial vertices is at most in general, at most if is regular or has no triangle, and at most if has girth at least . [Copyright &y& Elsevier]

Graph editing problems offer an interesting perspective on sub- and supergraph identification problems for a large variety of target properties. They have also attracted significant attention in recent years, particularly in the area of parameterized complexity as the problems have rich parameter ecologies. In this paper we examine generalisations of the notion of editing a graph to obtain a regular subgraph. In particular we extend the notion of regularity to include two variants of edge-regularity along with the unifying constraint of strong regularity. We present a number of results, with the central observation that these problems retain the general complexity profile of their regularity-based inspiration: when the number of edits k and the maximum degree r are taken together as a combined parameter, the problems are tractable (i.e. in FPT ), but are otherwise intractable. We also examine variants of the basic editing to obtain a regular subgraph problem from the perspective of parameterizing by the treewidth of the input graph. In this case the treewidth of the input graph essentially becomes a limiting parameter on the natural k + r parameterization. [ABSTRACT FROM AUTHOR]

Abstract: Recently, there has been significant theoretical progress towards fixed-parameter algorithms for the DOMINATING SET problem of planar graphs. It is known that the problem on a planar graph with vertices and dominating number can be solved in time using tree/branch-decomposition based algorithms. In this paper, we report computational results of Fomin and Thilikos algorithm which uses the branch-decomposition based approach. The computational results show that the algorithm can solve the DOMINATING SET problem of large planar graphs in a practical time and memory space for the class of graphs with small branchwidth. For the class of graphs with large branchwidth, the size of instances that can be solved by the algorithm in practice is limited to about one thousand edges due to a memory space bottleneck. The practical performances of the algorithm coincide with the theoretical analysis of the algorithm. The results of this paper suggest that the branch-decomposition based algorithms can be practical for some applications on planar graphs. [Copyright &y& Elsevier]

Abstract: One of the most relevant topics in the analysis of biological networks is the identification of functional motifs inside a network. A recent approach introduced in literature, called Graph Motif, represents the network as a vertex-colored graph, and the motif as a multiset of colors. An occurrence of a motif in a vertex-colored graph is a connected induced subgraph of whose vertex set is colored exactly as . In this paper we investigate three different variants of the Graph Motif problem. The first two variants, Minimum Adding Motif (Min-Add Graph Motif) and Minimum Substitution Motif (Min-Sub Graph Motif), deal with approximate occurrences of a motif in the graph, while the third variant, Constrained Graph Motif (CGM), constrains the motif to contain a given set of vertices. We investigate the computational and parameterized complexity of the three problems. We show that Min-Add Graph Motifand Min-Sub Graph Motifare both NP-hard, even when is a set, and the graph is a tree with maximum degree in which each color appears at most twice. Then, we show that Min-Sub Graph Motifis fixed-parameter tractable when parameterized by the size of . Finally, we consider the parameterized complexity of the CGMproblem; we give a fixed-parameter algorithm for graphs of bounded treewidth, and show that the problem is W[2]-hard when parameterized by , even if the input graph has diameter . [Copyright &y& Elsevier]

Abstract: Let be an undirected graph with maximum degree at most 3 such that does not contain any of the three graphs given in the paper as a subgraph. We prove that the independence number of is at least , where is the number of vertices in and is the number of nontriangle vertices in . This bound is tight as implied by the well-known tight lower bound of on the independence number of triangle-free graphs of maximum degree at most 3. We show some algorithmic applications of the aforementioned combinatorial result to the area of parameterized complexity. We present a linear-time kernelization algorithm for the independent set problem on graphs with maximum degree at most 3 that computes a kernel of size at most , where is the given parameter. This improves the known upper bound on the kernel size for the problem, and implies a lower bound on the kernel size for the vertex cover problem on graphs with maximum degree at most 3. [Copyright &y& Elsevier]

Abstract: The maximum induced matching problem is known to be APX-hard in the class of bipartite graphs. Moreover, the problem is also intractable in this class from a parameterized point of view, i.e. it is W[1]-hard. In this paper, we reveal several classes of bipartite (and more general) graphs for which the problem admits fixed-parameter tractable algorithms. We also study the computational complexity of the problem for regular bipartite graphs and prove that the problem remains APX-hard even under this restriction. On the other hand, we show that for hypercubes (a proper subclass of regular bipartite graphs) the problem admits a simple solution. [Copyright &y& Elsevier]

Abstract: The notion of a boundary graph property was recently introduced as a relaxation of that of a minimal property and was applied to several problems of both algorithmic and combinatorial nature. In the present paper, we first survey recent results related to this notion and then apply it to two algorithmic graph problems: Hamiltonian cycle and vertex -colorability. In particular, we discover the first two boundary classes for the Hamiltonian cycle problem and prove that for any there is a continuum of boundary classes for vertex -colorability. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the problem of reconstructing a hidden weighted graph using additive queries. We prove the following. Let be a weighted hidden graph with  vertices and edges such that the weights on the edges are bounded between  and  for any positive constants  and . For any , there exists a non-adaptive algorithm that finds the edges of the graph using additive queries. This solves the open problem in [S. Choi, J.H. Kim, Optimal query complexity bounds for finding graphs, in: STOC, 2008, pp. 749–758]. Choi and Kim’s proof holds for for a sufficiently large constant  and uses the graph theory. We use the algebraic approach for the problem. Our proof is simple and holds for any . [Copyright &y& Elsevier]

Abstract: We consider the problem of matching people to items, where each person ranks a subset of items in an order of preference, possibly involving ties. There are several notions of optimality about how to best match a person to an item; in particular, popularity is a natural and appealing notion of optimality. A matching is popular if there is no matching such that the number of people who prefer to exceeds the number who prefer to . However, popular matchings do not always provide an answer to the problem of determining an optimal matching since there are simple instances that do not admit popular matchings. This motivates the following extension of the popular matchings problem: [•] Given a graph where is the set of people and is the set of items, and a list denoting upper bounds on the number of copies of each item, does there exist such that for each , having copies of the -th item, where , enables the resulting graph to admit a popular matching? In this paper we show that the above problem is NP-hard. We show that the problem is NP-hard even when each is 1 or 2. We show a polynomial time algorithm for a variant of the above problem where the total increase in copies is bounded by an integer . [Copyright &y& Elsevier]

Abstract: The Cops and Robbers game as originally defined independently by Quilliot and by Nowakowski and Winkler in the 1980s has been much studied, but very few results pertain to the algorithmic and complexity aspects of it. In this paper we prove that computing the minimum number of cops that are guaranteed to catch a robber on a given graph is NP-hard and that the parameterized version of the problem is W[2]-hard; the proof extends to the case where the robber moves time faster than the cops. We show that on split graphs, the problem is polynomially solvable if but is NP-hard if . We further prove that on graphs of bounded cliquewidth the problem is polynomially solvable for . Finally, we show that for planar graphs the minimum number of cops is unbounded if the robber is faster than the cops. [Copyright &y& Elsevier]

Abstract: In this paper we propose a simple algorithm called CliqueMinTriang for computing a minimal triangulation of a graph. If is the set of edges that is added to to make it a complete graph then the asymptotic complexity of CliqueMinTriang is where is the degree of the subgraph of induced by . Therefore our algorithm performs well when is a dense graph. We also show how to exploit the existing minimal triangulation techniques in conjunction with CliqueMinTriang to efficiently find a minimal triangulation of nondense graphs. Finally we show how the algorithm can be adapted to perform a backward stepwise selection of decomposable Markov networks; the resulting procedure has the same time complexity as that of existing similar algorithms. [Copyright &y& Elsevier]

Abstract: The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. Given two functions, and , with domain sizes and , respectively, and the same range, the goal of the problem is to find and such that . This problem has been considered in both quantum and classical settings in terms of query complexity. This paper describes an optimal algorithm that uses quantum walk to solve this problem. Our algorithm can be slightly modified to solve the more general problem of finding a tuple consisting of elements in the two function domains that has a prespecified property. It can also be generalized to find a claw of functions for any constant integer , where the domain sizes of the functions may be different. [Copyright &y& Elsevier]