 |
Discrete Mathematics & Theoretical Computer Science |
Vol. 16 no. 2
1. Diversities and the Geometry of Hypergraphs
The embedding of finite metrics in 1 has become a fundamental tool for both combinatorial optimization and large-scale data analysis. One important application is to network flow problems as there is close relation between max-flow min-cut theorems and the minimal distortion embeddings of metrics into 1. Here we show that this theory can be generalized to a larger set of combinatorial optimization problems on both graphs and hypergraphs. This theory is not built on metrics and metric embeddings, but on diversities, a type of multi-way metric introduced recently by the authors. We explore diversity embeddings, 1 diversities, and their application to Steiner Tree Packing and Hypergraph Cut problems.
Section:
PRIMA 2013
2. Uniquely monopolar-partitionable block graphs
As a common generalization of bipartite and split graphs, monopolar graphs are defined in terms of the existence of certain vertex partitions. It has been shown that to determine whether a graph has such a partition is NP-complete for general graphs and polynomial for several classes of graphs. In this paper, we investigate graphs that admit a unique such partition and call them uniquely monopolar-partitionable graphs. By employing a tree trimming technique, we obtain a characterization of uniquely monopolar-partitionable block graphs. Our characterization implies a polynomial time algorithm for recognizing them.
Section:
PRIMA 2013
3. On additive combinatorics of permutations of ℤ<sub>n</sub>
Let ℤ<sub>n</sub> denote the ring of integers modulo n. A permutation of ℤ<sub>n</sub> is a sequence of n distinct elements of ℤ<sub>n</sub>. Addition and subtraction of two permutations is defined element-wise. In this paper we consider two extremal problems on permutations of ℤ<sub>n</sub>, namely, the maximum size of a collection of permutations such that the sum of any two distinct permutations in the collection is again a permutation, and the maximum size of a collection of permutations such that no sum of two distinct permutations in the collection is a permutation. Let the sizes be denoted by s(n) and t(n) respectively. The case when n is even is trivial in both the cases, with s(n)=1 and t(n)=n!. For n odd, we prove (nφ(n))/2<sup>k</sup>≤s(n)≤n!· 2<sup>-(n-1)/2</sup>((n-1)/2)! and 2<sup>(n-1)/2</sup>·(n-1 / 2)!≤t(n)≤ 2<sup>k</sup>·(n-1)!/φ(n), where k is the number of distinct prime divisors of n and φ is the Euler's totient function.
Section:
PRIMA 2013
4. A matroid associated with a phylogenetic tree
A (pseudo-)metric D on a finite set X is said to be a \textquotelefttree metric\textquoteright if there is a finite tree with leaf set X and non-negative edge weights so that, for all x,y ∈X, D(x,y) is the path distance in the tree between x and y. It is well known that not every metric is a tree metric. However, when some such tree exists, one can always find one whose interior edges have strictly positive edge weights and that has no vertices of degree 2, any such tree is – up to canonical isomorphism – uniquely determined by D, and one does not even need all of the distances in order to fully (re-)construct the tree\textquoterights edge weights in this case. Thus, it seems of some interest to investigate which subsets of X, 2 suffice to determine (\textquoteleftlasso\textquoteright) these edge weights. In this paper, we use the results of a previous paper to discuss the structure of a matroid that can be associated with an (unweighted) X-tree T defined by the requirement that its bases are exactly the \textquotelefttight edge-weight lassos\textquoteright for T, i.e, the minimal subsets of X, 2 that lasso the edge weights of T.
Section:
PRIMA 2013
5. Influence of the tie-break rule on the end-vertex problem
End-vertices of a given graph search may have some nice properties, as for example it is well known that the last vertex of Lexicographic Breadth First Search (LBFS) in a chordal graph is simplicial, see Rose, Tarjan and Lueker 1976. Therefore it is interesting to consider if these vertices can be recognized in polynomial time or not, as first studied in Corneil, Köhler and Lanlignel 2010. A graph search is a mechanism for systematically visiting the vertices of a graph. At each step of a graph search, the key point is the choice of the next vertex to be explored. Graph searches only differ by this selection mechanism during which a tie-break rule is used. In this paper we study how the choice of the tie-break in case of equality during the search, for a given graph search including the classic ones such as BFS and DFS, can determine the complexity of the end-vertex problem. In particular we prove a counterintuitive NP-completeness result for Breadth First Search solving a problem raised in Corneil, Köhler and Lanlignel 2010.
Section:
PRIMA 2013
6. Complexity aspects of the computation of the rank of a graph
We consider the P₃-convexity on simple undirected graphs, in which a set of vertices S is convex if no vertex outside S has two or more neighbors in S. The convex hull H(S) of a set S is the smallest convex set containing S as a subset. A set S is a convexly independent set if v \not ∈ H(S\setminus \v\) for all v in S. The rank \rk(G) of a graph is the size of the largest convexly independent set. In this paper we consider the complexity of determining \rk(G). We show that the problem is NP-complete even for split or bipartite graphs with small diameter. We also show how to determine \rk(G) in polynomial time for the well structured classes of graphs of trees and threshold graphs. Finally, we give a tight upper bound for \rk(G), which in turn gives a tight upper bound for the Radon number as byproduct, which is the same obtained before by Henning, Rautenbach and Schäfer. Additionally, we briefly show that the problem is NP-complete also in the monophonic convexity.
Section:
PRIMA 2013
7. The graph isomorphism problem on geometric graphs
The graph isomorphism (GI) problem asks whether two given graphs are isomorphic or not. The GI problem is quite basic and simple, however, it\textquoterights time complexity is a long standing open problem. The GI problem is clearly in NP, no polynomial time algorithm is known, and the GI problem is not NP-complete unless the polynomial hierarchy collapses. In this paper, we survey the computational complexity of the problem on some graph classes that have geometric characterizations. Sometimes the GI problem becomes polynomial time solvable when we add some restrictions on some graph classes. The properties of these graph classes on the boundary indicate us the essence of difficulty of the GI problem. We also show that the GI problem is as hard as the problem on general graphs even for grid unit intersection graphs on a torus, that partially solves an open problem.
Section:
PRIMA 2013
8. Nonrepetitive colorings of lexicographic product of graphs
A coloring c of the vertices of a graph G is nonrepetitive if there exists no path v1v2\textellipsisv2l for which c(vi)=c(vl+i) for all 1<=i<=l. Given graphs G and H with |V(H)|=k, the lexicographic product G[H] is the graph obtained by substituting every vertex of G by a copy of H, and every edge of G by a copy of Kk,k. We prove that for a sufficiently long path P, a nonrepetitive coloring of P[Kk] needs at least 3k+⌊k/2⌋ colors. If k>2 then we need exactly 2k+1 colors to nonrepetitively color P[Ek], where Ek is the empty graph on k vertices. If we further require that every copy of Ek be rainbow-colored and the path P is sufficiently long, then the smallest number of colors needed for P[Ek] is at least 3k+1 and at most 3k+⌈k/2⌉. Finally, we define fractional nonrepetitive colorings of graphs and consider the connections between this notion and the above results.
Section:
PRIMA 2013
9. Hamiltonian decomposition of prisms over cubic graphs
The prisms over cubic graphs are 4-regular graphs. The prisms over 3-connected cubic graphs are Hamiltonian. In 1986 Brian Alspach and Moshe Rosenfeld conjectured that these prisms are Hamiltonian decomposable. In this paper we present a short survey of the status of this conjecture, various constructions proving that certain families of prisms over 3-connected cubic graphs are Hamiltonian decomposable. Among others, we prove that the prisms over cubic Halin graphs, cubic generalized Halin graphs of order 4k + 2 and other infinite sequences of cubic graphs are Hamiltonian decomposable.
Section:
PRIMA 2013
10. Spanning connectedness and Hamiltonian thickness of graphs and interval graphs
A spanning connectedness property is one which involves the robust existence of a spanning subgraph which is of some special form, say a Hamiltonian cycle in which a sequence of vertices appear in an arbitrarily given ordering, or a Hamiltonian path in the subgraph obtained by deleting any three vertices, or three internally-vertex-disjoint paths with any given endpoints such that the three paths meet every vertex of the graph and cover the edges of an almost arbitrarily given linear forest of a certain fixed size. Let π = π1 · · · πn be an ordering of the vertices of an n-vertex graph G. For any positive integer k ≤ n − 1, we call π a k-thick Hamiltonian vertex ordering of G provided it holds for all i ∈ {1,. .. , n − 1} that πiπi+1 ∈ E(G) and the number of neighbors of πi among {πi+1,. .. , πn} is at least min{n − i, k}; For any nonnegative integer k, we say that π is a −k-thick Hamiltonian vertex ordering of G provided |{i : πiπi+1 / ∈ E(G), 1 ≤ i ≤ n − 1}| ≤ k + 1. Our main discovery is that the existence of a thick Hamiltonian vertex ordering will guarantee that the graph has various kinds of spanning connectedness properties and that for interval graphs, quite a few seemingly unrelated spanning connectedness properties are equivalent to the existence of a thick Hamiltonian vertex ordering. Due to the connection between Hamiltonian thickness and spanning connectedness properties, we can present several linear time algorithms for […]
Section:
PRIMA 2013