Search

For two integers r, ℓ ≥ 0, a graph G = ( V, E) is an ( r, ℓ)-graph if V can be partitioned into r independent sets and ℓ cliques. In the parameterized ( r, ℓ)- Vertex Deletion problem, given a graph G and an integer k, one has to decide whether at most k vertices can be removed from G to obtain an ( r, ℓ)-graph. This problem is NP-hard if r + ℓ ≥ 1 and encompasses several relevant problems such as Vertex Cover and Odd Cycle Transversal. The parameterized complexity of ( r, ℓ)- Vertex Deletion was known for all values of ( r, ℓ) except for (2,1), (1,2), and (2,2). We prove that each of these three cases is FPT and, furthermore, solvable in single-exponential time, which is asymptotically optimal in terms of k. We consider as well the version of ( r, ℓ)- Vertex Deletion where the set of vertices to be removed has to induce an independent set, and provide also a parameterized complexity dichotomy for this problem. [ABSTRACT FROM AUTHOR]

In an edge-colored graph, the cost incurred at a vertex on a path when two incident edges with different colors are traversed is called reload or changeover cost. The Minimum Changeover Cost Arborescence ( MinCCA ) problem consists in finding an arborescence with a given root vertex such that the total changeover cost of the internal vertices is minimized. It has been recently proved by Gözüpek et al. (2016) that the MinCCA problem when parameterized by the treewidth and the maximum degree of the input graph is in FPT . In this article we present the following hardness results for MinCCA : • the problem is W [1]-hard when parameterized by the vertex cover number of the input graph, even on graphs of degeneracy at most 3. In particular, it is W [1]-hard parameterized by the treewidth of the input graph, which answers the main open problem in the work of Gözüpek et al. (2016); • it is W [1]-hard on multigraphs parameterized by the tree-cutwidth of the input multigraph; and • it remains NP -hard on planar graphs even when restricted to instances with at most 6 colors and 0/1 symmetric costs, or when restricted to instances with at most 8 colors, maximum degree bounded by 4, and 0/1 symmetric costs. [ABSTRACT FROM AUTHOR]

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51-63, ] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction: [ABSTRACT FROM AUTHOR]

Minor Containment is a fundamental problem in Algorithmic Graph Theory used as a subroutine in numerous graph algorithms. A model of a graph H in a graph G is a set of disjoint connected subgraphs of G indexed by the vertices of H, such that if { u, v} is an edge of H, then there is an edge of G between components C and C. A graph H is a minor of G if G contains a model of H as a subgraph. We give an algorithm that, given a planar n-vertex graph G and an h-vertex graph H, either finds in time $\mathcal{O}(2^{\mathcal{O}(h)} \cdot n +n^{2}\cdot\log n)$ a model of H in G, or correctly concludes that G does not contain H as a minor. Our algorithm is the first single-exponential algorithm for this problem and improves all previous minor testing algorithms in planar graphs. Our technique is based on a novel approach called partially embedded dynamic programming. [ABSTRACT FROM AUTHOR]

Abstract: In this article we provide hardness results and approximation algorithms for the following three natural degree-constrained subgraph problems, which take as input an undirected graph . Let be a fixed integer. The () problem takes as additional input a weight function , and asks for a subset such that the subgraph induced by is connected, has maximum degree at most , and is maximized. The Minimum Subgraph of Minimum Degree () problem involves finding a smallest subgraph of with minimum degree at least . Finally, the Dual Degree-dense -Subgraph () problem consists in finding a subgraph of such that and the minimum degree in is maximized. [Copyright &y& Elsevier]

Abstract: All-Optical Label Switching (AOLS) is a new technology that performs packet forwarding without any optical–electrical–optical conversions. In this paper, we study the problem of routing a set of requests in AOLS networks using GMPLS technology, with the aim of minimizing the number of labels required to ensure the forwarding. We first formalize the problem by associating to each routing strategy a logical hypergraph, called a hypergraph layout, whose hyperarcs are dipaths of the physical graph, called tunnels in GMPLS terminology. We define a cost function for the hypergraph layout, depending on its total length plus its total hop count. Minimizing the cost of the design of an AOLS network can then be expressed as finding a minimum cost hypergraph layout. We prove hardness results for the problem, namely for general directed networks we prove that it is NP-hard to find a -approximation, where is a positive constant and is the number of nodes of the network. For symmetric directed networks, we prove that the problem is APX-hard. These hardness results hold even if the traffic instance is a partial broadcast. On the other hand, we provide approximation algorithms, in particular an -approximation for symmetric directed networks. Finally, we focus on the case where the physical network is a directed path, providing a polynomial-time dynamic programming algorithm for a fixed number of sources running in time. [Copyright &y& Elsevier]

Abstract: The -Minor containment problem asks whether a graph contains some fixed graph as a minor, that is, whether can be obtained by some subgraph of after contracting edges. The derivation of a polynomial-time algorithm for -Minor containment is one of the most important and technical parts of the Graph Minor Theory of Robertson and Seymour and it is a cornerstone for most of the algorithmic applications of this theory. -Minor containment for graphs of bounded branchwidth is a basic ingredient of this algorithm. The currently fastest solution to this problem, based on the ideas introduced by Robertson and Seymour, was given by Hicks in [I.V. Hicks, Branch decompositions and minor containment, Networks 43 (1) (2004) 1–9], providing an algorithm that in time decides if a graph with edges and branchwidth , contains a fixed graph on vertices as a minor. In this work we improve the dependence on of Hicks’ result by showing that checking if is a minor of can be done in time . We set up an approach based on a combinatorial object called rooted packing, which captures the properties of the subgraphs of that we seek in our dynamic programming algorithm. This formulation with rooted packings allows us to speed up the algorithm when is embedded in a fixed surface, obtaining the first algorithm for minor containment testing with single-exponential dependence on branchwidth. Namely, it runs in time , with . Finally, we show that slight modifications of our algorithm permit to solve some related problems within the same time bounds, like induced minor or contraction containment. [Copyright &y& Elsevier]

We study grooming for two-period optical networks, a variation of the traffic grooming problem for wavelength division multiplexed (WDM) ring networks introduced by Colbourn, Quattrocchi, and Syrotiuk. In the two-period grooming problem, during the first period of time there is all-to-all uniform traffic among n nodes, each request using 1/C of the bandwidth; and during the second period there is all-to-all uniform traffic only among a subset V of v nodes, each request now being allowed to use 1/C' of the bandwidth, where C' < C. We determine the minimum drop cost (minimum number of add-drop multiplexers (ADMs)) for any n, v and C = 4 and C' ϵ (1, 2, 3). To do this, we use tools of graph decompositions. Indeed the two-period grooming problem corresponds to minimizing the total number of vertices in a partition of the edges of the complete graph Kn into subgraphs, where each subgraph has at most C edges and where furthermore it contains at most C' edges of the complete graph on v specified vertices. Subject to the condition that the two-period grooming has the least drop cost, the minimum number of wavelengths required is also determined in each case. [ABSTRACT FROM AUTHOR]