Some results on graphs without long induced paths

Many NP-hard graph problems remain difficult on P_k-free graphs for certain values of k. Our goal is to distinguish subclasses of P_k-free graphs where several important graph problems can be solved in polynomial time. In particular, we show that the independent set problem is polynomial-time solvable in the class of (P_k,K_1,n)-free graphs for any positive integers k and n, thereby generalizing several known results.     

On the complexity of digraph packings

Let be a fixed collection of digraphs. Given a digraph H, a -packing of H is a collection of vertex disjoint subgraphs of H, each isomorphic to a member of . For undirected graphs, Loebl and Poljak have completely characterized the complexity of deciding the existence of a perfect -packing, in the case that consists of two graphs one of which is a single edge on two vertices. We characterize -packing where consists of two digraphs one of which is a single arc on two vertices.     

On maximum induced matchings in bipartite graphs

The problem of finding a maximum induced matching is known to be NP-hard in general bipartite graphs. We strengthen this result by reducing the problem to some special classes of bipartite graphs such as bipartite graphs with maximum degree 3 or C₄-free bipartite graphs. On the other hand, we describe a new polynomially solvable case for the problem in bipartite graphs which deals with a generalization of bi-complement reducible graphs.     

On finding cycle bases and fundamental cycle bases with a shortest maximal cycle

An undirected biconnected graph G with nonnegative integer lengths on the edges is given. The problem we consider is that of finding a cycle basis B of G such that the length of the longest cycle included in B is the smallest among all cycle bases of G. We first observe that Horton's algorithm [SIAM J. Comput. 16 (2) (1987) 358-366] provides a fast solution of the problem that extends the one given by Chickering et al. [Inform. Process. Lett. 54 (1995) 55-58] for uniform graphs. On the other hand we show that, if the basis is required to be fundamental, then the problem is NP-hard and cannot be approximated within 2−?, ∀?>0, even with uniform lengths, unless P=NP. This problem remains NP-hard even restricted to the class of complete graphs; in this case it cannot be approximated within 13/11−?, ∀?>0, unless P=NP; it is instead approximable within 2 in general, and within 3/2 if the triangle inequality holds.     

Chain packing in graphs

This paper discusses the complexity of packingk-chains (simple paths of lengthk) into an undirected graph; the chains packed must be either vertex-disjoint or edge-disjoint. Linear-time algorithms are given for both problems when the graph is a tree, and for the edge-disjoint packing problem when the graph is general andk = 2. The vertex-disjoint packing problem for general graphs is shown to be NP-complete even when the graph has maximum degree three andk = 2. Similarly the edge-disjoint packing problem is NP-complete even when the graph has maximum degree four andk = 3.This is a revised version of the technical report [15].     

Algorithms for transitive closure

Let σ′(n) denote the number of all strongly connected graphs on the n-element set. We prove that σ′(n)?2ⁿ²·(1−n(n−1)/2ⁿ⁻¹). Hence the algorithm computing a transitive closure by a reduction to acyclic graphs has the expected time O(n²), under the assumption of uniform distribution of input graphs. Furthermore, we present a new algorithm constructing the transitive closure of an acyclic graph.     

On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P

We show that computing the lexicographically first four-coloring for planar graphs is -hard. This result optimally improves upon a result of Khuller and Vazirani who prove this problem NP-hard, and conclude that it is not self-reducible in the sense of Schnorr, assuming P≠NP. We discuss this application to non-self-reducibility and provide a general related result. We also discuss when raising a problem's NP-hardness lower bound to -hardness can be valuable.     

Vertex rankings of chordal graphs and weighted trees

In this paper we consider the vertex ranking problem of weighted trees. We show that this problem is strongly NP-hard. We also give a polynomial-time reduction from the problem of vertex ranking of weighted trees to the vertex ranking of (simple) chordal graphs, which proves that the latter problem is NP-hard. In this way we solve an open problem of Aspvall and Heggernes. We use this reduction and the algorithm of Bodlaender et al.'s for vertex ranking of partial k-trees to give an exact polynomial-time algorithm for vertex ranking of a tree with bounded and integer valued weight functions. This algorithm serves as a procedure in designing a PTAS for weighted vertex ranking problem of trees with bounded weight functions.     

Complexity of homomorphisms to direct products of graphs

For a graph G, OALG asks whether or not an input graph H together with a partial map g:S→G, S⊆V(H), admits a homomorphism f:H→G such that f|_S=g. We show that for connected graphs G₁, G₂, OAL G₁×G₂ is in P if G₁ and G₂ are trees and NP-complete otherwise.     

On the All-Farthest-Segments problem for a planar set of points

In this note, we outline a very simple algorithm for the following problem: Given a set S of n points p₁,p₂,p₃,…,pn in the plane, we have O(n²) segments implicitly defined on pairs of these n points. For each point pi, find a segment from this set of implicitly defined segments that is farthest from pi. The time complexity of our algorithm is in O(nh+nlogn), where n is the number of input points, and h is the number of vertices on the convex hull of S.     

Parameterized power domination complexity

The optimization problem of measuring all nodes in an electrical network by placing as few measurement units (PMUs) as possible is known as Power Dominating Set. Nodes can be measured indirectly according to Kirchhoff's law. We show that this problem can be solved in linear time for graphs of bounded treewidth and establish bounds on its parameterized complexity if the number of PMUs is the parameter.     

On packing shortest cycles in graphs

We study the problems to find a maximum packing of shortest edge-disjoint cycles in a graph of given girth g (g-ESCP) and its vertex-disjoint analogue g-VSCP. In the case g=3, Caprara and Rizzi (2001) have shown that g-ESCP can be solved in polynomial time for graphs with maximum degree 4, but is APX-hard for graphs with maximum degree 5, while g-VSCP can be solved in polynomial time for graphs with maximum degree 3, but is APX-hard for graphs with maximum degree 4. For g∈{4,5}, we show that both problems allow polynomial time algorithms for instances with maximum degree 3, but are APX-hard for instances with maximum degree 4. For each g?6, both problems are APX-hard already for graphs with maximum degree 3.     

A note on compressed sensing and the complexity of matrix multiplication

We consider the conjectured O(N2+?) time complexity of multiplying any two N×N matrices A and B. Our main result is a deterministic Compressed Sensing (CS) algorithm that both rapidly and accurately computes A⋅B provided that the resulting matrix product is sparse/compressible. As a consequence of our main result we increase the class of matrices A, for any given N×N matrix B, which allows the exact computation of A⋅B to be carried out using the conjectured O(N2+?) operations. Additionally, in the process of developing our matrix multiplication procedure, we present a modified version of Indyk's recently proposed extractor-based CS algorithm [P. Indyk, Explicit constructions for compressed sensing of sparse signals, in: SODA, 2008] which is resilient to noise.     

Complexity analysis of a decentralised graph colouring algorithm

Colouring a graph with its chromatic number of colours is known to be NP-hard. Identifying an algorithm in which decisions are made locally with no information about the graph's global structure is particularly challenging. In this article we analyse the complexity of a decentralised colouring algorithm that has recently been proposed for channel selection in wireless computer networks.     

Finding a dominating set on bipartite graphs

Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O^∗(²n−z), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O^∗(²n/2). Another implication is an algorithm for general graphs whose running time is O(n^1.7088).     

Finding optimal paths in MREP routing

Maximum Residual Energy Path (MREP) routing has been shown an effective routing scheme for energy conservation in battery powered wireless networks. Past studies on MREP routing are based on the assumption that the transmitting node consumes power, but the receiving node does not. This assumption is false if acknowledgment is required as occurs, for example, in some Bluetooth applications.If the receiving node does not consume power then the MREP routing problem for a single message is easily solvable in polynomial time using a simple Dijkstra-like algorithm. We further show in that when the receiving node does consume power the problem becomes NP-complete and is even impossible to approximate with an exponential approximation factor in polynomial time unless P=NP.     

The diameter of Hanoi graphs

Many questions regarding the Tower of Hanoi problem have been posed and answered during the years. Variants of the classical puzzle, such as allowing more than 3 pegs, and imposing limitations on the possible moves among the pegs, raised the analogous questions for those variants. One such question is: given a variant, and a certain number of disks, find a pair of disk arrangements such that the minimal number of moves required for changing from the first to the second is maximal over all pairs. One of the main results of the paper is identifying these for the Cyclic_h variants—the variants with h pegs arranged along a uni-directional circle—to be the pairs of perfect configurations where the destination peg is right before the source peg.     

A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements

We introduce a simple, linear time algorithm for recognizing trivially perfect (TP) graphs. It improves upon the algorithm of Yan et al. [J.-H. Yan, J.-J. Chen, G.J. Chang, Quasi-threshold graphs, Discrete Appl. Math. 69 (3) (1996) 247–255] in that it is certifying, producing a P₄ or a C₄ when the graph is not TP. In addition, our algorithm can be easily modified to recognize the complement of TP graphs (co-TP) in linear time as well. It is based on lexicographic BFS, and in particular the technique of partition refinement, which has been used in the recognition of many other graph classes [D.G. Corneil, Lexicographic breadth first search—a survey, in: WG 2004, in: Lecture Notes in Comput. Sci., vol. 3353, Springer, 2004, pp. 1–19].     

Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs

A spanning tree T of a graph G=(V,E) is called a locally connected spanning tree if the set of all neighbors of v in T induces a connected subgraph of G for all v∈V. The problem of recognizing whether a graph admits a locally connected spanning tree is known to be NP-complete even when the input graphs are restricted to chordal graphs. In this paper, we propose linear time algorithms for finding locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs, respectively.     

A fixed-parameter tractable algorithm for matrix domination

Matrix domination is the NP-complete problem of determining whether a given {0,1} matrix contains a set of k non-zero entries that are in the same row or same column as all other non-zero entries. Using a kernelization and search tree approach, we show the problem to be fixed-parameter tractable with running time .