Given a graph G and an odd cycle transversal T, we describe an elegant 0*(2(vertical bar T vertical bar)) algorithm for determining whether G has a smaller odd cycle transversal that is disjoint from T. We believe tha...
详细信息
Given a graph G and an odd cycle transversal T, we describe an elegant 0*(2(vertical bar T vertical bar)) algorithm for determining whether G has a smaller odd cycle transversal that is disjoint from T. We believe that our algorithm, based on a reduction to VERTEX COVER, is conceptually simpler than the known algorithms for the problem and refines the understanding of the relationship between ODD CYCLE TRANSVERSAL and VERTEX COVER. (C) 2013 Elsevier B.V. All rights reserved.
In the IMBALANCE MINIMIZATION problem we are given a graph G = (V, E) and an integer b and asked whether there is an ordering v(1) ... v(n) of V such that the sum of the imbalance of all the vertices is at most b. The...
详细信息
In the IMBALANCE MINIMIZATION problem we are given a graph G = (V, E) and an integer b and asked whether there is an ordering v(1) ... v(n) of V such that the sum of the imbalance of all the vertices is at most b. The imbalance of a vertex v(i) is the absolute value of the difference between the number of neighbors to the left and right of v(i). The problem is also known as the BALANCED VERTEX ORDERING problem and it finds many applications in graph drawing. We show that this problem is fixed parameter tractable and provide an algorithm that runs in time 2(O (b log b)) . n(O (1)). This resolves an open problem of Kara et al. [On the complexity of the balanced vertex ordering problem, in: COCOON, in: Lecture Notes in Comput. Sci., vol. 3595, 2005, pp. 849-858]. (C) 2013 Elsevier B.V. All rights reserved.
A subset F of vertices of a graph G is called a vertex cover P-t (VCPt) set if every path of order t in G contains at least one vertex from F. The vertex cover P-t (VCPt) problem is to find a minimum VCPt set in a gra...
详细信息
A subset F of vertices of a graph G is called a vertex cover P-t (VCPt) set if every path of order t in G contains at least one vertex from F. The vertex cover P-t (VCPt) problem is to find a minimum VCPt set in a graph. The VCPt problem is NP -complete for any integer t >= 2. In this paper, we restrict our attention to the VCP4 problem and present an FPT algorithm with runtime O*(3(k)) for the VCP4 problem. The algorithm constructs a VCP4 set of size at most k in a given graph G, or reports that no such VCP4 set exists in G. (C) 2015 Elsevier B:V. All rights reserved.
Covering a graph with cohesive subgraphs is a classical problem in theoretical computer science, for example when the cohesive subgraph model considered is a clique. In this paper, we consider as a model of cohesive s...
详细信息
Covering a graph with cohesive subgraphs is a classical problem in theoretical computer science, for example when the cohesive subgraph model considered is a clique. In this paper, we consider as a model of cohesive subgraph the 2-clubs, which are induced subgraphs of diameter at most 2. We prove new complexity results on the Min 2-Club Cover problem, a variant recently introduced in the literature which asks to cover the vertices of a graph with a minimum number of 2-clubs. First, we answer an open question on the decision version of Min 2-Club Cover that asks if it is possible to cover a graph with at most two 2-clubs, and we prove that it is W[1]-hard when parameterized by the distance to a 2-club. Then, we consider the complexity of Min 2-Club Cover on some graph classes. We prove that Min 2-Club Cover remains NP-hard on subcubic planar graphs, W[2]-hard on bipartite graphs when parameterized by the number of 2-clubs in a solution, and fixed-parameter tractable on graphs having hounded treewidth.
This paper revisits the classical edge-disjoint paths (EDP) problem, where one is given an undirected graphGand a set of terminal pairsPand asks whetherGcontains a set of pairwise edge-disjoint paths connecting every ...
详细信息
This paper revisits the classical edge-disjoint paths (EDP) problem, where one is given an undirected graphGand a set of terminal pairsPand asks whetherGcontains a set of pairwise edge-disjoint paths connecting every terminal pair inP. Our aim is to identify structural properties (parameters) of graphs which allow the efficient solution of EDP without restricting the placement of terminals inPin any way. In this setting, EDP is known to remain NP-hard even on extremely restricted graph classes, such as graphs with a vertex cover of size 3. We present three results which use edge-separator based parameters to chart new islands of tractability in the complexity landscape of EDP. Our first and main result utilizes the fairly recent structural parameter tree-cut width (a parameter with fundamental ties to graph immersions and graph cuts): we obtain a polynomial-time algorithm for EDP on every graph class of bounded tree-cut width. Our second result shows that EDP parameterized by tree-cut width is unlikely to be fixed-parameter tractable. Our final, third result is a polynomial kernel for EDP parameterized by the size of a minimum feedback edge set in the graph.
Given a simple polygon P on n vertices, two points x, y in P are said to be visible to each other if the line segment between x and y is contained in P. The POINT GUARD ART GALLERY problem asks for a minimum set S suc...
详细信息
Given a simple polygon P on n vertices, two points x, y in P are said to be visible to each other if the line segment between x and y is contained in P. The POINT GUARD ART GALLERY problem asks for a minimum set S such that every point in P is visible from a point in S. The VERTEX GUARD ART GALLERY problem asks for such a set S subset of the vertices of P. A point in the set S is referred to as a guard. For both variants, we rule out any f(k)n(o(k/log k)) algorithm, where k := vertical bar S vertical bar is the number of guards, for any computable function f, unless the exponential time hypothesis fails. These lower bounds almost match the n(O(k)) algorithms that exist for both problems.
In the ROOTED k-LEAF OUTBRANCHING PROBLEM, a digraph G = (V, E), a vertex r of G, and an integer k are given, and the goal is to find an r-rooted spanning outtree of G with >= k leaves (a subtree of G with vertex s...
详细信息
In the ROOTED k-LEAF OUTBRANCHING PROBLEM, a digraph G = (V, E), a vertex r of G, and an integer k are given, and the goal is to find an r-rooted spanning outtree of G with >= k leaves (a subtree of G with vertex set V, all edges directed away from r, and >= k leaves). We present a linear-time algorithm that computes a problem kernel with O(k(6)) vertices and O(k(7)) edges for the ROOTED k-LEAF OUTBRANCHING PROBLEM. By combining the new result with a result of Daligault and Thomasse (2009), a kernel with a quadratic number of vertices and edges can be found on n-vertex m-edge digraphs in time O(n + m + k(14)). (C) 2015 Elsevier B.V. All rights reserved.
The problem of finding a satisfying assignment that minimizes the number of variables that are set to 1 is NP-complete even for a satisfiable 2-SAT formula. We call this problem MIN ONES 2-SAT. It generalizes the well...
详细信息
The problem of finding a satisfying assignment that minimizes the number of variables that are set to 1 is NP-complete even for a satisfiable 2-SAT formula. We call this problem MIN ONES 2-SAT. It generalizes the well-studied problem of finding the smallest vertex cover of a graph, which can be modeled using a 2-SAT formula with no negative literals. The natural parameterized version of the problem asks for a satisfying assignment of weight at most k. In this paper, we present a polynomial-time reduction from MIN ONES 2-SAT to VERTEX COVER without increasing the parameter and ensuring that the number of vertices in the reduced instance is equal to the number of variables of the input formula. Consequently, we conclude that this problem also has a simple 2-approximation algorithm and a 2k - c logk-variable kernel subsuming (or, in the case of kernels, improving) the results known earlier. Further, the problem admits algorithms for the parameterized and optimization versions whose runtimes will always match the runtimes of the best-known algorithms for the corresponding versions of vertex cover. Finally we show that the optimum value of the LP relaxation of the MIN ONES 2-SAT and that of the corresponding VERTEX COVER are the same. This implies that the (recent) results of VERTEX COVER version parameterized above the optimum value of the LP relaxation of VERTEX COVER carry over to the MIN ONES 2-SAT version parameterized above the optimum of the LP relaxation of MIN ONES 2-SAT. (C) 2013 Elsevier B.V. All rights reserved.
The main topic of this article is to study a class of graph modification problems. A typical graph modification problem takes as input a graph G, a positive integer k and the objective is to add/delete k vertices (edg...
详细信息
The main topic of this article is to study a class of graph modification problems. A typical graph modification problem takes as input a graph G, a positive integer k and the objective is to add/delete k vertices (edges) so that the resulting graph belongs to a particular family, F, of graphs. In general the family F is defined by forbidden subgraph/minor characterization. In this paper rather than taking a structural route to define F, we take algebraic route. More formally, given a fixed positive integer r, we define F-r, as the family of graphs where for each G is an element of (F)r, the rank of the adjacency matrix of G is at most r. Using the family Fr we initiate algorithmic study, both in classical and parameterized complexity, of following graph modification problems: r-RANK VERTEX DELETION, r-RANK EDGE DELETION and r-RANK EDITING. These problems generalize the classical VERTEX COVER problem and a variant of the d-CLUSTER EDITING problem. We first show that all the three problems are NP-Complete. Then we show that these problems are fixed parameter tractable (FPT) by designing an algorithm with running time 2(O(k log r))n(O(1)) for r-RANK VERTEX DELETION, and an algorithm for r-RANK EDGE DELETION and r-RANK EDITING running in time 2(O(f(r)root k log k))n(O(1)). We complement our FPT result by designing polynomial kernels for these problems. (C) 2016 Elsevier B.V. All rights reserved.
In this paper, we study the SHORTEST COLOR SPANNING t- INTERVALS problem, and related generalizations, namely SMALLEST COLOR SPANNING t- SQUARES and SMALLEST COLOR SPANNING t- CIRCLES. The generic setting is the follo...
详细信息
In this paper, we study the SHORTEST COLOR SPANNING t- INTERVALS problem, and related generalizations, namely SMALLEST COLOR SPANNING t- SQUARES and SMALLEST COLOR SPANNING t- CIRCLES. The generic setting is the following: we are given n points in the plane (or on a line), each colored with one of k colors. For each color i we also have a demand s(i). Given a budget t, we are required to find at most t objects (for example, intervals, squares, circles, etc.) that cover at least si points of color i. Typically, the goal is to minimize the maximum perimeter or area. We provide exact algorithms for these problems for the cases of intervals, circles and squares, generalizing several known results. In the case of intervals, we provide a comprehensive understanding of the complexity landscape of the problem after taking several natural parameters into account. Given that the problem turns out to be W[1]-hard parameterized by the standard parameters, we introduce a new parameter, namely sparsity, and prove new hardness and tractability results in this context. For squares and circles, we use existing algorithms of one smallest color spanning object in order to design algorithms for getting t identical objects of minimum size whose union spans all the colors. (C) 2018 Elsevier B.V. All rights reserved.
暂无评论