The parameterized complexity of the induced matching problem

Given a graph G and an integer k≥0, the NP-complete Induced Matching problem asks whether there exists an edge subset M of size at least k such that M is a matching and no two edges of M are joined by an edge of G. The complexity of this problem on general graphs, as well as on many restricted graph classes has been studied intensively. However, other than the fact that the problem is W[1]-hard on general graphs, little is known about the parameterized complexity of the problem in restricted graph classes. In this work, we provide first-time fixed-parameter tractability results for planar graphs, bounded-degree graphs, graphs with girth at least six, bipartite graphs, line graphs, and graphs of bounded treewidth. In particular, we give a linear-size problem kernel for planar graphs.     

On Generating Triangle-Free Graphs

We show that the problem to decide whether a graph can be made triangle-free with at most k edge deletions remains NP-complete even when restricted to planar graphs of maximum degree seven. In addition, we provide polynomial-time data reduction rules for this problem and obtain problem kernels consisting of 6k vertices for general graphs and 11k/3 vertices for planar graphs.     

The Proportional Colouring Problem: Optimizing Buffers in Wireless Mesh Networks

In this paper, we consider a new edge colouring problem motivated by wireless mesh networks optimization: the proportional edge colouring problem. Given a graph G with positive weights associated to its edges, we want to find a proper edge colouring which assigns to each edge at least a proportion (given by its weight) of all the colours. If such colouring exists, we want to find one using the minimum number of colours. We proved that deciding if a weighted graph admits a proportional edge colouring is polynomial while determining its proportional edge chromatic number is NP-hard. We also give a lower and an upper bound that can be polynomially computed. We finally characterize some graphs and weighted graphs for which we can determine the proportional edge chromatic number.     

Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree

Given an undirected graph with edge weights, we are asked to find an orientation, that is, an assignment of a direction to each edge, so as to minimize the weighted maximum outdegree in the resulted directed graph. The problem is called MMO, and is a restricted variant of the well-known minimum makespan problem. As in previous studies, it is shown that MMO is in P for trees, weak NP-hard for planar bipartite graphs, and strong NP-hard for general graphs. There are still gaps between those graph classes. The objective of this paper is to show tighter thresholds of complexity: We show that MMO is (i) in P for cactus graphs, (ii) weakly NP-hard for outerplanar graphs, and also (iii) strongly NP-hard for graphs which are both planar and bipartite. This implies the NP-hardness for P₄-bipartite, diamond-free or house-free graphs, each of which is a superclass of cactus. We also show (iv) the NP-hardness for series-parallel graphs and multi-outerplanar graphs, and (v) present a pseudo-polynomial time algorithm for graphs with bounded treewidth.     

Integer flows

A k-flow is an assignment of edge directions and integer weights in the range 1, …., k – 1 to the edges of an undirected graph so that ateach vertex the flow in is equal to the flow out. This paper gives a polynomial algorithm for finding a 6-flow that applies uniformly to each graph. The algorithm specializes to give a 5-flow for planar graphs.     

On minimum power connectivity problems

Given a (directed or undirected) graph with edge costs, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of its nodes. Motivated by applications for wireless networks, we present polynomial and improved approximation algorithms, as well as inapproximability results, for some classic network design problems under the power minimization criteria. Our main result is for the problem of finding a min-power subgraph that contains k internally-disjoint vs-paths from every node v to a given node s: we give a polynomial algorithm for directed graphs and a logarithmic approximation algorithm for undirected graphs. In contrast, we will show that the corresponding edge-connectivity problems are unlikely to admit even a polylogarithmic approximation.     

Generating unlabeled connected cubic planar graphs uniformly at random

We present an expected polynomial time algorithm to generate an unlabeled connected cubic planar graph uniformly at random. We first consider rooted connected cubic planar graphs, i.e., we count connected cubic planar graphs up to isomorphisms that fix a certain directed edge. Based on decompositions along the connectivity structure, we derive recurrence formulas for the exact number of rooted cubic planar graphs. This leads to rooted 3‐connected cubic planar graphs, which have a unique embedding on the sphere. Special care has to be taken for rooted graphs that have a sense‐reversing automorphism. Therefore we introduce the concept of colored networks, which stand in bijective correspondence to rooted 3‐connected cubic planar graphs with given symmetries. Colored networks can again be decomposed along the connectivity structure. For rooted 3‐connected cubic planar graphs embedded in the plane, we switch to the dual and count rooted triangulations. Since all these numbers can be evaluated in polynomial time using dynamic programming, rooted connected cubic planar graphs can be generated uniformly at random in polynomial time by inverting the decomposition along the connectivity structure. To generate connected cubic planar graphs without a root uniformly at random, we apply rejection sampling and obtain an expected polynomial time algorithm. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

On the complexity of packing rainbow spanning trees

One of the most important questions in matroid optimization is to find disjoint common bases of two matroids. The significance of the problem is well-illustrated by the long list of conjectures that can be formulated as special cases. Bérczi and Schwarcz showed that the problem is hard in general, therefore identifying the borderline between tractable and intractable instances is of interest.In the present paper, we study the special case when one of the matroids is a partition matroid while the other one is a graphic matroid. This setting is equivalent to the problem of packing rainbow spanning trees, an extension of the problem of packing arborescences in directed graphs which was answered by Edmonds' seminal result on disjoint arborescences. We complement his result by showing that it is NP-complete to decide whether an edge-colored graph contains two disjoint rainbow spanning trees. Our complexity result holds even for the very special case when the graph is the union of two spanning trees and each color class contains exactly two edges. As a corollary, we give a negative answer to a question on the decomposition of oriented k-partition-connected digraphs.     

Tree spanners in planar graphs

A tree t-spanner of a graph G is a spanning subtree T of G in which the distance between every pair of vertices is at most t times their distance in G. Spanner problems have received some attention, mostly in the context of communication networks. It is known that for general unweighted graphs, the problem of deciding the existence of a tree t-spanner can be solved in polynomial time for t=2, while it is NP-hard for any t⩾4; the case t=3 is open, but has been conjectured to be hard. In this paper, we consider tree spanners in planar graphs. We show that even for planar unweighted graphs, it is NP-hard to determine the minimum t for which a tree t-spanner exists. On the other hand, we give a polynomial algorithm for any fixed t that decides for planar unweighted graphs with bounded face length whether there is a tree t-spanner. Furthermore, we prove that it can be decided in polynomial time whether a planar unweighted graph has a tree t-spanner for t=3.     

Clustering and domination in perfect graphs

A k-cluster in a graph is an induced subgraph on k vertices which maximizes the number of edges. Both the k-cluster problem and the k-dominating set problem are NP-complete for graphs in general. In this paper we investigate the complexity status of these problems on various sub-classes of perfect graphs. In particular, we examine comparability graphs, chordal graphs, bipartite graphs, split graphs, cographs and κ-trees. For example, it is shown that the k-cluster problem is NP-complete for both bipartite and chordal graphs and the independent k-dominating set problem is NP-complete for bipartite graphs. Furthermore, where the k-cluster problem is polynomial we study the weighted and connected versions as well. Similarly we also look at the minimum k-dominating set problem on families which have polynomial k-dominating set algorithms.     

An approach for the Steiner problem in directed graphs

We present a scheme to solve the Steiner problem in directed graphs using a heuristic method to obtain upper bounds and thek shortest arborescences algorithm to compute lower bounds. We propose to combine these ideas in an enumerative algorithm. Computational results are presented for both thek shortest arborescences algorithm and the heuristic method, including reduction tests for the problem.This work was partially supported by CNP_q, FINEP, CAPES and IBM do Brasil.     

The most vital nodes with respect to independent set and vertex cover

Given an undirected graph with weights on its vertices, the k most vital nodes independent set (k most vital nodes vertex cover) problem consists of determining a set of k vertices whose removal results in the greatest decrease in the maximum weight of independent sets (minimum weight of vertex covers, respectively). We also consider the complementary problems, minimum node blocker independent set (minimum node blocker vertex cover) that consists of removing a subset of vertices of minimum size such that the maximum weight of independent sets (minimum weight of vertex covers, respectively) in the remaining graph is at most a specified value. We show that these problems are NP-hard on bipartite graphs but polynomial-time solvable on unweighted bipartite graphs. Furthermore, these problems are polynomial also on cographs and graphs of bounded treewidth. Results on the non-existence of ptas are presented, too.     

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

We study complexity and approximation of min weighted node coloring in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove that min weighted node coloring is NP-hard in P₈-free bipartite graphs, but polynomial for P₅-free bipartite graphs. We next focus on approximability in general bipartite graphs and improve earlier approximation results by giving approximation ratios matching inapproximability bounds. We next deal with min weighted edge coloring in bipartite graphs. We show that this problem remains strongly NP-hard, even in the case where the input graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6−ε, for any ε>0 and we give an approximation algorithm with the same ratio. Finally, we show that min weighted node coloring in split graphs can be solved by a polynomial time approximation scheme.     

Minimum edge ranking spanning trees of split graphs

Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for split graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable. We also show that the problem MERST for threshold graphs can be solved in linear time, where threshold graphs are known to be split.     

Vertex insertion approximates the crossing number of apex graphs

An apex graph is a graph G from which only one vertex v has to be removed to make it planar. We show that the crossing number of such G can be approximated up to a factor of Δ(G−v)⋅d(v)/2 by solving the vertex inserting problem, i.e. inserting a vertex plus incident edges into an optimally chosen planar embedding of a planar graph. Since the latter problem can be solved in polynomial time, this establishes the first polynomial fixed-factor approximation algorithm for the crossing number problem of apex graphs with bounded degree.Furthermore, we extend this result by showing that the optimal solution for inserting multiple edges or vertices into a planar graph also approximates the crossing number of the resulting graph.     

Feasible Graphs and Colorings

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring.     

Rooted directed path graphs are leaf powers

Leaf powers are a graph class which has been introduced to model the problem of reconstructing phylogenetic trees. A graph G=(V,E) is called k-leaf power if it admits a k-leaf root, i.e., a tree T with leaves V such that uv is an edge in G if and only if the distance between u and v in T is at most k. Moroever, a graph is simply called leaf power if it is a k-leaf power for some k∈N. This paper characterizes leaf powers in terms of their relation to several other known graph classes. It also addresses the problem of deciding whether a given graph is a k-leaf power.We show that the class of leaf powers coincides with fixed tolerance NeST graphs, a well-known graph class with absolutely different motivations. After this, we provide the largest currently known proper subclass of leaf powers, i.e, the class of rooted directed path graphs.Subsequently, we study the leaf rank problem, the algorithmic challenge of determining the minimum k for which a given graph is a k-leaf power. Firstly, we give a lower bound on the leaf rank of a graph in terms of the complexity of its separators. Secondly, we use this measure to show that the leaf rank is unbounded on both the class of ptolemaic and the class of unit interval graphs. Finally, we provide efficient algorithms to compute 2|V|-leaf roots for given ptolemaic or (unit) interval graphs G=(V,E).     

Packing and Covering Triangles in Planar Graphs

Tuza conjectured that if a simple graph G does not contain more than k pairwise edge-disjoint triangles, then there exists a set of at most 2k edges that meets all triangles in G. It has been shown that this conjecture is true for planar graphs and the bound is sharp. In this paper, we characterize the set of extremal planar graphs.     

An extremal problem in hypergraph coloring

F(n, r, k) is defined to be the minimum number of edges in an r graph on n vertices in which there exists a strongly colored edge in every equipartite k-coloring. Approximate values are given for this function in the general case, and the problem is solved in the particular case of graphs.     

On the maximum cardinality search lower bound for treewidth

The Maximum Cardinality Search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS algorithm. The visited degree of a vertex v in an MCS-ordering is the number of neighbours of v that are before v in the ordering. The visited degree of an MCS-ordering ψ of G is the maximum visited degree over all vertices v in ψ. The maximum visited degree over all MCS-orderings of graph G is called its maximum visited degree. Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345-353] showed that the treewidth of a graph G is at least its maximum visited degree.We show that the maximum visited degree is of size O(logn) for planar graphs, and give examples of planar graphs G with maximum visited degree k with O(k!) vertices, for all k∈N. Given a graph G, it is NP-complete to determine if its maximum visited degree is at least k, for any fixed k?7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.