Search

We thoroughly study a novel but basic combinatorial matrix completion problem: Given a binary incomplete matrix, fill in the missing entries so that every pair of rows in the resulting matrix has a Hamming distance within a specified range. We obtain an almost complete picture of the complexity landscape regarding the distance constraints and the maximum number of missing entries in any row. We develop polynomial-time algorithms for maximum diameter three based on Deza's theorem (1973) [11] from extremal set theory. We also prove NP-hardness for diameter at least four. For the number of missing entries per row, we show polynomial-time solvability when there is only one and NP-hardness when there can be at least two. In many of our algorithms, we heavily rely on Deza's theorem to identify sunflower structures. This paves the way towards polynomial-time algorithms which are based on finding graph factors and solving 2-SAT instances. [ABSTRACT FROM AUTHOR]

In a graph G , the 2-neighborhood of a vertex set X consists of all vertices of G having at least 2 neighbors in X. We say that a bipartite graph G (A , B) satisfies the double Hall property if | A | ≥ 2 , and every subset X ⊆ A of size at least 2 has a 2-neighborhood of size at least | X |. Salia conjectured that any bipartite graph G (A , B) satisfying the double Hall property contains a cycle covering A. Here, we prove the existence of a 2-factor covering A in any bipartite graph G (A , B) satisfying the double Hall property. We also show Salia's conjecture for graphs with restricted degrees of vertices in B. Additionally, we prove a lower bound on the number of edges in a graph satisfying the double Hall property, and the bound is sharp up to a constant factor. [ABSTRACT FROM AUTHOR]

An (r − 1, 1)-coloring of an r-regular graph G is an edge coloring (with arbitrarily many colors) such that each vertex is incident to r − 1 edges of one color and 1 edge of a different color. In this paper, we completely characterize all 4-regular pseudographs (graphs that may contain parallel edges and loops) which do not have a (3, 1)-coloring. Also, for each r ≥ 6 we construct graphs that are not (r −1, 1)-colorable and, more generally, are not (r − t, t)-colorable for small t.

The concept of Reload cost in a graph refers to the cost that occurs while traversing a vertex via two of its incident edges. This cost is uniquely determined by the colors of the two edges. This concept has various applications in transportation networks, communication networks, and energy distribution networks. Various problems using this model are defined and studied in the literature. The problem of finding a spanning tree whose diameter with respect to the reload costs is smallest possible, the problems of finding a path, trail or walk with minimum total reload cost between two given vertices, problems about finding a proper edge coloring of a graph such that the total reload cost is minimized, the problem of finding a spanning tree such that the sum of the reload costs of all paths between all pairs of vertices is minimized, and the problem of finding a set of cycles of minimum reload cost, that cover all the vertices of a graph, are examples of such problems. In this work we focus on the last problem. Noting that a cycle cover of a graph is a 2-factor of it, we generalize the problem to the problem of finding an r-factor of minimum reload cost of an edge colored graph. We prove several NP-hardness results for special cases of the problem. Namely, bounded degree graphs, planar graphs, bounded total cost, and bounded number of distinct costs. For the special case of r = 2, our results imply an improved NP-hardness result. On the positive side, we present a polynomial-time solvable special case which provides a tight boundary between the polynomial and hard cases in terms of r and the maximum degree of the graph. We then investigate the parameterized complexity of the problem, prove W[1]-hardness results and present an FPT-algorithm. [ABSTRACT FROM AUTHOR]

Every 9-regular graph (possibly with multiple edges) with odd edge-connectivity >5 can be edge-decomposed into three 3-factors. If Tutte's 3-flow conjecture is true, it also holds for all 9-regular graphs with odd edge-connectivity 5, but not with odd edge-connectivity 3. It holds for all planar 2-edge-connected 9-regular graphs, an equivalent version of the 4-color theorem for planar graphs. We address the more general question: If G is an r -regular graph, and r = k q where k , q are natural numbers >1, can G be edge-decomposed into k q -factors? If q is even, then the decomposition exists trivially. If k , q are both odd, then we prove that the decomposition exists if G has odd edge-connectivity (size of smallest odd edge-cut) at least 3 k − 2 , which is satisfied if the odd edge-connectivity is at least r − 2. If q is odd and k is even, then we must require that G has an even number of vertices just to guarantee that G has a q -factor. If we want a decomposition into q -factors, then we also need the condition that, for any partition of the vertex set of G into two odd parts, there must be at least k edges between the parts. We prove that the edge-decomposition into q -factors is always possible if G has an even number of vertices and the edge-connectivity of G is at least 2 k 2 + k. [ABSTRACT FROM AUTHOR]

Finding low-cost spanning subgraphs with given degree and connectivity requirements is a fundamental problem in the area of network design. We consider the problem of finding d-regular spanning subgraphs (or d-factors) of minimum weight with connectivity requirements. For the case of k-edge-connectedness, we present approximation algorithms that achieve constant approximation ratios for all d≥2.⌈k/2⌉. For the case of k-vertex-connectedness, we achieve constant approximation ratios for d≥2k-1. Our algorithms also work for arbitrary degree sequences if the minimum degree is at least 2.⌈k/2⌉ (for k-edge-connectivity) or 2k-1 (for k-vertex-connectivity). To complement our approximation algorithms, we prove that the problem with simple connectivity cannot be approximated better than the traveling salesman problem. In particular, the problem is A P X-hard. [ABSTRACT FROM AUTHOR]

The partition of graphs into 'nice' subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into same-size stars, a problem known to be NP-complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial-time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP-complete cases, for example, on grid graphs and chordal graphs. [ABSTRACT FROM AUTHOR]