Colorability of mixed hypergraphs and their chromatic inversions

We solve a long-standing open problem concerning a discrete mathematical model, which has various applications in computer science and several other fields, including frequency assignment and many other problems on resource allocation. A mixed hypergraph $\mathcal H $ is a triple $(X,\mathcal C ,\mathcal D )$ , where $X$ is the set of vertices, and $\mathcal C $ and $\mathcal D $ are two set systems over $X$ , the families of so-called C-edges and D-edges, respectively. A vertex coloring of a mixed hypergraph $\mathcal H $ is proper if every C-edge has two vertices with a common color and every D-edge has two vertices with different colors. A mixed hypergraph is colorable if it has at least one proper coloring; otherwise it is uncolorable. The chromatic inversion of a mixed hypergraph $\mathcal H =(X,\mathcal C ,\mathcal D )$ is defined as $\mathcal H ^c=(X,\mathcal D ,\mathcal C )$ . Since 1995, it was an open problem wether there is a correlation between the colorability properties of a hypergraph and its chromatic inversion. In this paper we answer this question in the negative, proving that there exists no polynomial-time algorithm (provided that $P \ne NP$ ) to decide whether both $\mathcal H $ and $\mathcal H ^c$ are colorable, or both are uncolorable. This theorem holds already for the restricted class of 3-uniform mixed hypergraphs (i.e., where every edge has exactly three vertices). The proof is based on a new polynomial-time algorithm for coloring a special subclass of 3-uniform mixed hypergraphs. Implementation in C++ programming language has been tested. Further related decision problems are investigated, too.     

Objective functions with redundant domains

Let $(E,{ \mathcal{A}})$ be a set system consisting of a finite collection ${ \mathcal{A}}$ of subsets of a ground set E, and suppose that we have a function ? which maps ${ \mathcal{A}}$ into some set S. Now removing a subset K from E gives a restriction ${ \mathcal{A}}(\bar{K})$ to those sets of ${ \mathcal{A}}$ disjoint from K, and we have a corresponding restriction $\phi|_{\hspace {.02in}{ \mathcal{A}}(\bar{K})}$ of our function ?. If the removal of K does not affect the image set of ?, that is $\mbox {Im}(\phi|_{\hspace {.02in}{ \mathcal{A}}(\bar{X})})=\mbox {Im}(\phi)$ , then we will say that K is a kernel set of ${ \mathcal{A}}$ with respect to ?. Such sets are potentially useful in optimisation problems defined in terms of ?. We will call the set of all subsets of E that are kernel sets with respect to ? a kernel system and denote it by $\mathrm {Ker}_{\phi}({ \mathcal{A}})$ . Motivated by the optimisation theme, we ask which kernel systems are matroids. For instance, if ${ \mathcal{A}}$ is the collection of forests in a graph G with coloured edges and ? counts how many edges of each colour occurs in a forest then $\mathrm {Ker}_{\phi}({ \mathcal{A}})$ is isomorphic to the disjoint sum of the cocycle matroids of the differently coloured subgraphs; on the other hand, if ${ \mathcal{A}}$ is the power set of a set of positive integers, and ? is the function which takes the values 1 and 0 on subsets according to whether they are sum-free or not, then we show that $\mathrm {Ker}_{\phi}({ \mathcal{A}})$ is essentially never a matroid.     

Optimal strategies for the one-round discrete Voronoi game on a line

The one-round discrete Voronoi game, with respect to a n-point user set  $\mathcal {U}$ , consists of two players Player 1 (P1) and Player 2 (P2). At first, P1 chooses a set $\mathcal{F}_{1}$ of m facilities following which P2 chooses another set $\mathcal{F}_{2}$ of m facilities, disjoint from  $\mathcal{F}_{1}$ , where m(=O(1)) is a positive constant. The payoff of P2 is defined as the cardinality of the set of points in $\mathcal{U}$ which are closer to a facility in $\mathcal{F}_{2}$ than to every facility in $\mathcal{F}_{1}$ , and the payoff of P1 is the difference between the number of users in $\mathcal{U}$ and the payoff of P2. The objective of both the players in the game is to maximize their respective payoffs. In this paper, we address the case where the points in $\mathcal{U}$ are located along a line. We show that if the sorted order of the points in $\mathcal{U}$ along the line is known, then the optimal strategy of P2, given any placement of facilities by P1, can be computed in O(n) time. We then prove that for m≥2 the optimal strategy of P1 in the one-round discrete Voronoi game, with the users on a line, can be computed in $O(n^{m-\lambda_{m}})$ time, where 0<λ _m <1, is a constant depending only on m.     

The partition method for poset-free families

Given a finite poset P, let ${\rm La}(n,P)$ denote the largest size of a family of subsets of an n-set that does not contain P as a (weak) subposet. We employ a combinatorial method, using partitions of the collection of all full chains of subsets of the n-set, to give simpler new proofs of the known asymptotic behavior of ${\rm La}(n,P)$ , as n→∞, when P is the r-fork $\mathcal {V}_{r}$ , the four-element N poset $\mathcal {N}$ , and the four-element butterfly-poset $\mathcal {B}$ .     

Minimum diameter cost-constrained Steiner trees

Given an edge-weighted undirected graph $G=(V,E,c,w)$ where each edge $e\in E$ has a cost $c(e)\ge 0$ and another weight $w(e)\ge 0$ , a set $S\subseteq V$ of terminals and a given constant $\mathrm{C}_0\ge 0$ , the aim is to find a minimum diameter Steiner tree whose all terminals appear as leaves and the cost of tree is bounded by $\mathrm{C}_0$ . The diameter of a tree refers to the maximum weight of the path connecting two different leaves in the tree. This problem is called the minimum diameter cost-constrained Steiner tree problem, which is NP-hard even when the topology of the Steiner tree is fixed. In this paper, we deal with the fixed-topology restricted version. We prove the restricted version to be polynomially solvable when the topology is not part of the input and propose a weakly fully polynomial time approximation scheme (weakly FPTAS) when the topology is part of the input, which can find a $(1+\epsilon )$ –approximation of the restricted version problem for any $\epsilon >0$ with a specific characteristic.     

Radiation hybrid map construction problem parameterized

In this paper, we study the Radiation hybrid map construction ( $\mathsf{{RHMC} }$ ) problem which is about reconstructing a genome from a set of gene clusters. The problem is known to be $\mathsf{{NP} }$ -complete even when all gene clusters are of size two and the corresponding problem ( $\mathsf{{RHMC}_2 }$ ) admits efficient constant-factor approximation algorithms. In this paper, for the first time, we consider the more general case when the gene clusters can have size either two or three ( $\mathsf{{RHMC}_3 }$ ). Let ${p\text{- }\mathsf {RHMC} }$ be a parameterized version of $\mathsf{{RHMC} }$ where the parameter is the size of solution. We present a linear kernel for ${p\text{- }\mathsf {RHMC}_3 }$ of size $22k$ that when combined with a bounded search-tree algorithm, gives an FPT algorithm running in $O(6^kk+n)$ time. For ${p\text{- }\mathsf {RHMC}_3 }$ we present a bounded search tree algorithm which runs in $O^*(2.45^k)$ time, greatly improving the previous bound using weak kernels.     

Popularity at minimum cost

We consider an extension of the popular matching problem in this paper. The input to the popular matching problem is a bipartite graph $G = (\mathcal{A}\cup\mathcal{B},E)$ , where $\mathcal{A}$ is a set of people, $\mathcal{B}$ is a set of items, and each person $a \in\mathcal{A}$ ranks a subset of items in order of preference, with ties allowed. The popular matching problem seeks to compute a matching M ^? between people and items such that there is no matching M where more people are happier with M than with M ^?. Such a matching M ^? is called a popular matching. However, there are simple instances where no popular matching exists. Here we consider the following natural extension to the above problem: associated with each item $b \in\mathcal{B}$ is a non-negative price cost(b), that is, for any item b, new copies of b can be added to the input graph by paying an amount of cost(b) per copy. When G does not admit a popular matching, the problem is to “augment” G at minimum cost such that the new graph admits a popular matching. We show that this problem is NP-hard; in fact, it is NP-hard to approximate it within a factor of $\sqrt{n_{1}}/2$ , where n ₁ is the number of people. This problem has a simple polynomial time algorithm when each person has a preference list of length at most 2. However, if we consider the problem of constructing a graph at minimum cost that admits a popular matching that matches all people, then even with preference lists of length 2, the problem becomes NP-hard. On the other hand, when the number of copies of each item is fixed, we show that the problem of computing a minimum cost popular matching or deciding that no popular matching exists can be solved in O(mn ₁) time, where m is the number of edges.     

On certain geometric properties of the Yao–Yao graphs

We show that, for any constant $\rho > 1$ , there exists an integer constant $k$ such that the Yao–Yao graph with parameter $k$ defined on a civilized unit disk graph is a geometric spanner of stretch factor $\rho $ . This improves the results of Wang and Li in several aspects, as described in the paper. This partially answers an open problem posed by Demaine, Mitchell and O’Rourke about the spanner properties of Yao–Yao graphs. We also show that the Yao–Yao graph with parameter $k=4$ defined on the complete Euclidean graph is not plane.     

Parity and strong parity edge-colorings of graphs

A parity walk in an edge-coloring of a graph is a walk along which each color is used an even number of times. A parity edge-coloring (respectively, strong parity edge-coloring) is an edge-coloring in which there is no nontrivial parity path (respectively, open parity walk). The parity edge-chromatic number p(G) (respectively, strong parity edge-chromatic number $\widehat{p}(G)$ ) is the least number of colors in a parity edge-coloring (respectively, strong parity edge-coloring) of G. Notice that $\widehat{p}(G) \ge p(G) \ge \chi'(G) \ge \Delta(G)$ for any graph G. In this paper, we determine $\widehat{p}(G)$ and p(G) for some complete bipartite graphs and some products of graphs. For instance, we determine $\widehat{p}(K_{m,n})$ and p(K _m,n ) for m≤n with n≡0,?1,?2 (mod 2^?lg?m?).     

Spanning 3-connected index of graphs

For an integer $s>0$ and for $u,v\in V(G)$ with $u\ne v$ , an $(s;u,v)$ -path-system of G is a subgraph H of G consisting of s internally disjoint (u, v)-paths, and such an H is called a spanning $(s;u,v)$ -path system if $V(H)=V(G)$ . The spanning connectivity $\kappa ^{*}(G)$ of graph G is the largest integer s such that for any integer k with $1\le k \le s$ and for any $u,v\in V(G)$ with $u\ne v$ , G has a spanning ( $k;u,v$ )-path-system. Let G be a simple connected graph that is not a path, a cycle or a $K_{1,3}$ . The spanning k-connected index of G, written $s_{k}(G)$ , is the smallest nonnegative integer m such that $L^m(G)$ is spanning k-connected. Let $l(G)=\max \{m:\,G$ has a divalent path of length m that is not both of length 2 and in a $K_{3}$ }, where a divalent path in G is a path whose interval vertices have degree two in G. In this paper, we prove that $s_{3}(G)\le l(G)+6$ . The key proof to this result is that every connected 3-triangular graph is 2-collapsible.     

On the complexity of path problems in properly colored directed graphs

We address the complexity class of several problems related to finding a path in a properly colored directed graph. A properly colored graph is defined as a graph G whose vertex set is partitioned into $\mathcal{X}(G)$ stable subsets, where $\mathcal{X}(G)$ denotes the chromatic number of G. We show that to find a simple path that meets all the colors in a properly colored directed graph is NP-complete, and so are the problems of finding a shortest and longest of such paths between two specific nodes.     

On the approximability of positive influence dominating set in social networks

In social networks, there is a tendency for connected users to match each other’s behaviors. Moreover, a user likely adopts a behavior, if a certain fraction of his family and friends follows that behavior. Identifying people who have the most influential effect to the others is of great advantages, especially in politics, marketing, behavior correction, and so on. Under a graph-theoretical framework, we study the positive influence dominating set (PIDS) problem that seeks for a minimal set of nodes $\mathcal{P}$ such that all other nodes in the network have at least a fraction ρ>0 of their neighbors in $\mathcal{P}$ . We also study a different formulation, called total positive influence dominating set (TPIDS), in which even nodes in $\mathcal{P}$ are required to have a fraction ρ of neighbors inside $\mathcal{P}$ . We show that neither of these problems can be approximated within a factor of (1??)lnmax{Δ,|V|^1/2}, where Δ is the maximum degree. Moreover, we provide a simple proof that both problems can be approximated within a factor lnΔ+O(1). In power-law networks, where the degree sequence follows a power-law distribution, both problems admit constant factor approximation algorithms. Finally, we present a linear-time exact algorithms for trees.     

The adjacent vertex distinguishing total coloring of planar graphs

An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of adjacent vertices have distinct sets of colors. The minimum number of colors needed for an adjacent vertex distinguishing total coloring of G is denoted by $\chi''_{a}(G)$ . In this paper, we characterize completely the adjacent vertex distinguishing total chromatic number of planar graphs G with large maximum degree Δ by showing that if Δ≥14, then $\varDelta+1\leq \chi''_{a}(G)\leq \varDelta+2$ , and $\chi''_{a}(G)=\varDelta+2$ if and only if G contains two adjacent vertices of maximum degree.     

Online maximum directed cut

We investigate a natural online version of the well-known Maximum Directed Cut problem on DAGs. We propose a deterministic algorithm and show that it achieves a competitive ratio of $\frac{3\sqrt{3}}{2}\approx 2.5981$ . We then give a lower bound argument to show that no deterministic algorithm can achieve a ratio of $\frac{3\sqrt{3}}{2}-\epsilon$ for any ??>0 thus showing that our algorithm is essentially optimal. Then, we extend our technique to improve upon the analysis of an old result: we show that greedily derandomizing the trivial randomized algorithm for MaxDiCut in general graphs improves the competitive ratio from 4 to 3, and also provide a tight example.     

Improved upper bound for acyclic chromatic index of planar graphs without 4-cycles

Let $\chi'_{a}(G)$ and Δ(G) denote the acyclic chromatic index and the maximum degree of a graph G, respectively. Fiam?ík conjectured that $\chi'_{a}(G)\leq \varDelta (G)+2$ . Even for planar graphs, this conjecture remains open with large gap. Let G be a planar graph without 4-cycles. Fiedorowicz et al. showed that $\chi'_{a}(G)\leq \varDelta (G)+15$ . Recently Hou et al. improved the upper bound to Δ(G)+4. In this paper, we further improve the upper bound to Δ(G)+3.     

Graphs with small balanced decomposition numbers

A balanced coloring of a graph \(G\) is an ordered pair \((R,B)\) of disjoint subsets \(R,B \subseteq V(G)\) with \(|R|=|B|\) . The balanced decomposition number  \(f(G)\) of a connected graph \(G\) is the minimum integer \(f\) such that for any balanced coloring \((R,B)\) of \(G\) there is a partition \(\mathcal{P}\) of \(V(G)\) such that \(S\) induces a connected subgraph with \(|S| \le f\) and \(|S \cap R| = |S \cap B|\) for \(S \in \mathcal{P}\) . This paper gives a short proof for the result by Fujita and Liu (2010) that a graph \(G\) of \(n\) vertices has \(f(G)=3\) if and only if \(G\) is \(\lfloor \frac{n}{2} \rfloor \) -connected but is not a complete graph.     

\lambda -numbers of several classes of snarks

In the paper we study \(\lambda \) -numbers of several classes of snarks. We show that the \(\lambda \) -number of each Blanu \(\breve{s}\) a snark, Flower snark and Goldberg snark is \(6\) . For \(n\ge 2\) , we show that there is a dot product of \(n\) Petersen graphs such that its \(\lambda \) -number is 6.     

Minimum number of disjoint linear forests covering a planar graph

Graph coloring has interesting real-life applications in optimization, computer science and network design, such as file transferring in a computer network, computation of Hessians matrix and so on. In this paper, we consider one important coloring, linear arboricity, which is an improper edge coloring. Moreover, we study linear arboricity on planar graphs with maximum degree \(\varDelta \ge 7\) . We have proved that the linear arboricity of \(G\) is \(\lceil \frac{\varDelta }{2}\rceil \) , if for each vertex \(v\in V(G)\) , there are two integers \(i_v,j_v\in \{3,4,5,6,7,8\}\) such that any two cycles of length \(i_v\) and \(j_v\) , which contain \(v\) , are not adjacent. Clearly, if \(i_v=i, j_v=j\) for each vertex \(v\in V(G)\) , then we can easily get one corollary: for two fixed integers \(i,j\in \{3,4,5,6,7,8\}\) , if there is no adjacent cycles with length \(i\) and \(j\) in \(G\) , then the linear arboricity of \(G\) is \(\lceil \frac{\varDelta }{2}\rceil \) .     

Mobile facility location: combinatorial filtering via weighted occupancy

An instance of the mobile facility location problem consists of a complete directed graph \(G = (V, E)\) , in which each arc \((u, v) \in E\) is associated with a numerical attribute \(\mathcal M (u,v)\) , representing the cost of moving any object from \(u\) to \(v\) . An additional ingredient of the input is a collection of servers \(S = \{ s_1, \ldots , s_k \}\) and a set of clients \(C = \{ c_1, \ldots , c_\ell \}\) , which are located at nodes of the underlying graph. With this setting in mind, a movement scheme is a function \(\psi : S \rightarrow V\) that relocates each server \(s_i\) to a new position, \(\psi ( s_i )\) . We refer to \(\mathcal M ( s_i, \psi ( s_i ) )\) as the relocation cost of \(s_i\) , and to \(\min _{i \in [k]} \mathcal M (c_j, \psi ( s_i ) )\) , the cost of assigning client \(c_j\) to the nearest final server location, as the service cost of \(c_j\) . The objective is to compute a movement scheme that minimizes the sum of relocation and service costs. In this paper, we resolve an open question posed by Demaine et al. (SODA ’07) by characterizing the approximability of mobile facility location through LP-based methods. We also develop a more efficient algorithm, which is based on a combinatorial filtering approach. The latter technique is of independent interest, as it may be applicable in other settings as well. In this context, we introduce a weighted version of the occupancy problem, for which we establish interesting tail bounds, not before demonstrating that existing bounds cannot be extended.     

Notes on L(1,1) and L(2,1) labelings for n-cube

Suppose \(d\) is a positive integer. An \(L(d,1)\) -labeling of a simple graph \(G=(V,E)\) is a function \(f:V\rightarrow \mathbb{N }=\{0,1,2,{\ldots }\}\) such that \(|f(u)-f(v)|\ge d\) if \(d_G(u,v)=1\) ; and \(|f(u)-f(v)|\ge 1\) if \(d_G(u,v)=2\) . The span of an \(L(d,1)\) -labeling \(f\) is the absolute difference between the maximum and minimum labels. The \(L(d,1)\) -labeling number, \(\lambda _d(G)\) , is the minimum of span over all \(L(d,1)\) -labelings of \(G\) . Whittlesey et al. proved that \(\lambda _2(Q_n)\le 2^k+2^{k-q+1}-2,\) where \(n\le 2^k-q\) and \(1\le q\le k+1\) . As a consequence, \(\lambda _2(Q_n)\le 2n\) for \(n\ge 3\) . In particular, \(\lambda _2(Q_{2^k-k-1})\le 2^k-1\) . In this paper, we provide an elementary proof of this bound. Also, we study the \(L(1,1)\) -labeling number of \(Q_n\) . A lower bound on \(\lambda _1(Q_n)\) are provided and \(\lambda _1(Q_{2^k-1})\) are determined.