FPT-algorithms for some problems related to integer programming

This paper studies a new version of the location problem called the mixed center location problem. Let P be a set of n points in the plane. We first consider the mixed 2-center problem, where one of the centers must be in P, and we solve it in \(O(n^2\log n)\) time. Second, we consider the mixed k-center problem, where m of the centers are in P, and we solve it in \(O(n^{m+O(\sqrt{k-m})})\) time. Motivated by two practical constraints, we propose two variations of the problem. Third, we present a 2-approximation algorithm and three heuristics solving the mixed k-center problem (\(k>2\)).     

The <Emphasis Type="Italic">k</Emphasis>-metric dimension

The anti-Ramsey number AR(G, H) is defined to be the maximum number of colors in an edge coloring of G which doesn’t contain any rainbow subgraphs isomorphic to H. It is clear that there is an \(AR(K_{m,n},kK_2)\)-edge-coloring of \(K_{m,n}\) that doesn’t contain any rainbow \(kK_2\). In this paper, we show the uniqueness of this kind of \(AR(K_{m,n},kK_2)\)-edge-coloring of \(K_{m,n}\).     

A compact representation for minimizers of <Emphasis Type="Italic">k</Emphasis>-submodular functions

A k-submodular function is a generalization of submodular and bisubmodular functions. This paper establishes a compact representation for minimizers of a k-submodular function by a poset with inconsistent pairs (PIP). This is a generalization of Ando–Fujishige’s signed poset representation for minimizers of a bisubmodular function. We completely characterize the class of PIPs (elementary PIPs) arising from k-submodular functions. We give algorithms to construct the elementary PIP of minimizers of a k-submodular function f for three cases: (i) a minimizing oracle of f is available, (ii) f is network-representable, and (iii) f arises from a Potts energy function. Furthermore, we provide an efficient enumeration algorithm for all maximal minimizers of a Potts k-submodular function. Our results are applicable to obtain all maximal persistent labelings in actual computer vision problems. We present experimental results for real vision instances.     

Two extremal problems related to orders

We consider two extremal problems related to total orders on all subsets of \({\mathbb N}\). The first one is to maximize the Lagrangian of hypergraphs among all hypergraphs with m edges for a given positive integer m. In 1980’s, Frankl and Füredi conjectured that for a given positive integer m, the r-uniform hypergraph with m edges formed by taking the first m r-subsets of \({\mathbb N}\) in the colex order has the largest Lagrangian among all r-uniform hypergraphs with m edges. We provide some partial results for 4-uniform hypergraphs to this conjecture. The second one is for a given positive integer m, how to minimize the cardinality of the union closure families generated by edge sets of the r-uniform hypergraphs with m edges. Leck, Roberts and Simpson conjectured that the union closure family generated by the first m r-subsets of \({\mathbb N}\) in order U has the minimum cardinality among all the union closure families generated by edge sets of the r-uniform hypergraphs with m edges. They showed that the conjecture is true for graphs. We show that a similar result holds for non-uniform hypergraphs whose edges contain 1 or 2 vertices.     

The <Emphasis Type="Italic">w</Emphasis>-centroids and least <Emphasis Type="Italic">w</Emphasis>-central subtrees in weighted trees

Let T be a weighted tree with a positive number w(v) associated with each vertex v. A subtree S is a w-central subtree of the weighted tree T if it has the minimum eccentricity \(e_L(S)\) in median graph \(G_{LW}\). A w-central subtree with the minimum vertex weight is called a least w-central subtree of the weighted tree T. In this paper we show that each least w-central subtree of a weighted tree either contains a vertex of the w-centroid or is adjacent to a vertex of the w-centroid. Also, we show that any two least w-central subtrees of a weighted tree either have a nonempty intersection or are adjacent.     

Pac king spanning trees and spanning 2-connected k-edge-connected essentially $$(2 k-1)$$(2 k-1)-edge-connected subgraphs

Let \(k\ge 2, p\ge 1, q\ge 0\) be integers. We prove that every \((4kp-2p+2q)\)-connected graph contains p spanning subgraphs \(G_i\) for \(1\le i\le p\) and q spanning trees such that all \(p+q\) subgraphs are pairwise edge-disjoint and such that each \(G_i\) is k-edge-connected, essentially \((2k-1)\)-edge-connected, and \(G_i -v\) is \((k-1)\)-edge-connected for all \(v\in V(G)\). This extends the well-known result of Nash-Williams and Tutte on packing spanning trees, a theorem that every 6p-connected graph contains p pairwise edge-disjoint spanning 2-connected subgraphs, and a theorem that every \((6p+2q)\)-connected graph contains p spanning 2-connected subgraphs and q spanning trees, which are all pairwise edge-disjoint. As an application, we improve a result on k-arc-connected orientations.     

Safe sets in graphs: Graph classes and structural parameters

A safe set of a graph \(G=(V,E)\) is a non-empty subset S of V such that for every component A of G[S] and every component B of \(G[V {\setminus } S]\), we have \(|A| \ge |B|\) whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between the tree-depth and the vertex cover number. We then conclude the paper by showing hardness for split graphs and planar graphs.     

Modified linear programming and class 0 bounds for graph pebbling

Given a configuration of pebbles on the vertices of a connected graph G, a pebbling move removes two pebbles from some vertex and places one pebble on an adjacent vertex. The pebbling number of a graph G is the smallest integer k such that for each vertex v and each configuration of k pebbles on G there is a sequence of pebbling moves that places at least one pebble on v. First, we improve on results of Hurlbert, who introduced a linear optimization technique for graph pebbling. In particular, we use a different set of weight functions, based on graphs more general than trees. We apply this new idea to some graphs from Hurlbert’s paper to give improved bounds on their pebbling numbers. Second, we investigate the structure of Class 0 graphs with few edges. We show that every n-vertex Class 0 graph has at least \(\frac{5}{3}n - \frac{11}{3}\) edges. This disproves a conjecture of Blasiak et al. For diameter 2 graphs, we strengthen this lower bound to \(2n - 5\), which is best possible. Further, we characterize the graphs where the bound holds with equality and extend the argument to obtain an identical bound for diameter 2 graphs with no cut-vertex.     

On (<Emphasis Type="Italic">s</Emphasis>, <Emphasis Type="Italic">t</Emphasis>)-relaxed strong edge-coloring of graphs

In this paper, we introduce a new relaxation of strong edge-coloring. Let G be a graph. For two nonnegative integers s and t, an (s, t)-relaxed strong k-edge-coloring is an assignment of k colors to the edges of G, such that for any edge e, there are at most s edges adjacent to e and t edges which are distance two apart from e assigned the same color as e. The (s, t)-relaxed strong chromatic index, denoted by \({\chi '}_{(s,t)}(G)\), is the minimum number k of an (s, t)-relaxed strong k-edge-coloring admitted by G. This paper studies the (s, t)-relaxed strong edge-coloring of graphs, especially trees. For a tree T, the tight upper bounds for \({\chi '}_{(s,0)}(T)\) and \({\chi '}_{(0,t)}(T)\) are given. And the (1, 1)-relaxed strong chromatic index of an infinite regular tree is determined. Further results on \({\chi '}_{(1,0)}(T)\) are also presented.     

A new graph parameter and a construction of larger graph without increasing radio <Emphasis Type="Italic">k</Emphasis>-chromatic number

For a positive integer \(k\ge 2\), the radio k-coloring problem is an assignment L of non-negative integers (colors) to the vertices of a finite simple graph G satisfying the condition \(|L(u)-L(v)| \ge k+1-d(u,v)\), for any two distinct vertices u, v of G and d(u, v) being distance between u, v. The span of L is the largest integer assigned by L, while 0 is taken as the smallest color. An \(rc_k\)-coloring on G is a radio k-coloring on G of minimum span which is referred as the radio k-chromatic number of G and denoted by \(rc_k(G)\). An integer h, \(0<h<rc_k(G)\), is a hole in a \(rc_k\)-coloring on G if h is not assigned by it. In this paper, we construct a larger graph from a graph of a certain class by using a combinatorial property associated with \((k-1)\) consecutive holes in any \(rc_k\)-coloring of a graph. Exploiting the same property, we introduce a new graph parameter, referred as \((k-1)\)-hole index of G and denoted by \(\rho _k(G)\). We also explore several properties of \(\rho _k(G)\) including its upper bound and relation with the path covering number of the complement \(G^c\).     

The <Emphasis Type="Italic">k</Emphasis>-hop connected dominating set problem: approximation and hardness

Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G there is a vertex u in D such that the distance between v and u in G is at most k. We study the problem of finding a minimum k-hop connected dominating set of a graph (\({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\)). We prove that \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) is \(\mathscr {NP}\)-hard on planar bipartite graphs of maximum degree 4. We also prove that \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) is \(\mathscr {APX}\)-complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) on bipartite and on (1, 2)-split graphs. Interestingly, one of these thresholds is a parameter of the input graph which is not a function of its number of vertices. We also discuss the complexity of computing this graph parameter. On the positive side, we show an approximation algorithm for \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\). Finally, when \(k=1\), we present two new approximation algorithms for the weighted version of the problem restricted to graphs with a polynomially bounded number of minimal separators.     

On the b-coloring of tight graphs

A coloring c of a graph \(G=(V,E)\) is a b -coloring if for every color i there is a vertex, say w(i), of color i whose neighborhood intersects every other color class. The vertex w(i) is called a b-dominating vertex of color i. The b -chromatic number of a graph G, denoted by b(G), is the largest integer k such that G admits a b-coloring with k colors. Let m(G) be the largest integer m such that G has at least m vertices of degree at least \(m-1\). A graph G is tight if it has exactly m(G) vertices of degree \(m(G)-1\), and any other vertex has degree at most \(m(G)-2\). In this paper, we show that the b-chromatic number of tight graphs with girth at least 8 is at least \(m(G)-1\) and characterize the graphs G such that \(b(G)=m(G)\). Lin and Chang (2013) conjectured that the b-chromatic number of any graph in \(\mathcal {B}_{m}\) is m or \(m-1\) where \(\mathcal {B}_{m}\) is the class of tight bipartite graphs \((D,D{^\prime })\) of girth 6 such that D is the set of vertices of degree \(m-1\). We verify the conjecture of Lin and Chang for some subclass of \(\mathcal {B}_{m}\), and we give a lower bound for any graph in \(\mathcal {B}_{m}\).     

Algorithmic aspects of <Emphasis Type="Italic">b</Emphasis>-disjunctive domination in graphs

For a fixed integer \(b>1\), a set \(D\subseteq V\) is called a b-disjunctive dominating set of the graph \(G=(V,E)\) if for every vertex \(v\in V{\setminus }D\), v is either adjacent to a vertex of D or has at least b vertices in D at distance 2 from it. The Minimum b-Disjunctive Domination Problem (MbDDP) is to find a b-disjunctive dominating set of minimum cardinality. The cardinality of a minimum b-disjunctive dominating set of G is called the b-disjunctive domination number of G, and is denoted by \(\gamma _{b}^{d}(G)\). Given a positive integer k and a graph G, the b-Disjunctive Domination Decision Problem (bDDDP) is to decide whether G has a b-disjunctive dominating set of cardinality at most k. In this paper, we first show that for a proper interval graph G, \(\gamma _{b}^{d}(G)\) is equal to \(\gamma (G)\), the domination number of G for \(b \ge 3\) and observe that \(\gamma _{b}^{d}(G)\) need not be equal to \(\gamma (G)\) for \(b=2\). We then propose a polynomial time algorithm to compute a minimum cardinality b-disjunctive dominating set of a proper interval graph for \(b=2\). Next we tighten the NP-completeness of bDDDP by showing that it remains NP-complete even in chordal graphs. We also propose a \((\ln ({\varDelta }^{2}+(b-1){\varDelta }+b)+1)\)-approximation algorithm for MbDDP, where \({\varDelta }\) is the maximum degree of input graph \(G=(V,E)\) and prove that MbDDP cannot be approximated within \((1-\epsilon ) \ln (|V|)\) for any \(\epsilon >0\) unless NP \(\subseteq \) DTIME\((|V|^{O(\log \log |V|)})\). Finally, we show that MbDDP is APX-complete for bipartite graphs with maximum degree \(\max \{b,4\}\).     

On irreducible no-hole <Emphasis Type="Italic">L</Emphasis>(2, 1)-coloring of subdivision of graphs

An L(2, 1)-coloring (or labeling) of a graph G is a mapping \(f:V(G) \rightarrow \mathbb {Z}^{+}\bigcup \{0\}\) such that \(|f(u)-f(v)|\ge 2\) for all edges uv of G, and \(|f(u)-f(v)|\ge 1\) if u and v are at distance two in G. The span of an L(2, 1)-coloring f, denoted by span f, is the largest integer assigned by f to some vertex of the graph. The span of a graph G, denoted by \(\lambda (G)\), is min {span \(f: f\text {is an }L(2,1)\text {-coloring of } G\}\). If f is an L(2, 1)-coloring of a graph G with span k then an integer l is a hole in f, if \(l\in (0,k)\) and there is no vertex v in G such that \(f(v)=l\). A no-hole coloring is defined to be an L(2, 1)-coloring with span k which uses all the colors from \(\{0,1,\ldots ,k\}\), for some integer k not necessarily the span of the graph. An L(2, 1)-coloring is said to be irreducible if colors of no vertices in the graph can be decreased and yield another L(2, 1)-coloring of the same graph. An irreducible no-hole coloring of a graph G, also called inh-coloring of G, is an L(2, 1)-coloring of G which is both irreducible and no-hole. The lower inh-span or simply inh-span of a graph G, denoted by \(\lambda _{inh}(G)\), is defined as \(\lambda _{inh}(G)=\min ~\{\)span f : f is an inh-coloring of G}. Given a graph G and a function h from E(G) to \(\mathbb {N}\), the h-subdivision of G, denoted by \(G_{(h)}\), is the graph obtained from G by replacing each edge uv in G with a path of length h(uv). In this paper we show that \(G_{(h)}\) is inh-colorable for \(h(e)\ge 2\), \(e\in E(G)\), except the case \(\Delta =3\) and \(h(e)=2\) for at least one edge but not for all. Moreover we find the exact value of \(\lambda _{inh}(G_{(h)})\) in several cases and give upper bounds of the same in the remaining.     

Cha n nel assig nme n t problem a nd n-fold t-separa ted $$L(j_1,j_2,\ldo ts,j_m)$$-labeli ng of graphs

This paper considers the channel assignment problem in mobile communications systems. Suppose there are many base stations in an area, each of which demands a number of channels to transmit signals. The channels assigned to the same base station must be separated in some extension, and two channels assigned to two different stations that are within a distance must be separated in some other extension according to the distance between the two stations. The aim is to assign channels to stations so that the interference is controlled within an acceptable level and the spectrum of channels used is minimized. This channel assignment problem can be modeled as the multiple t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labeling of the interference graph. In this paper, we consider the case when all base stations demand the same number of channels. This case is referred as n-fold t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labeling of a graph. This paper first investigates the basic properties of n-fold t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labelings of graphs. And then it focuses on the special case when \(m=1\). The optimal n-fold t-separated L(j)-labelings of all complete graphs and almost all cycles are constructed. As a consequence, the optimal n-fold t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labelings of the triangular lattice and the square lattice are obtained for the case \(j_1=j_2=\cdots =j_m\). This provides an optimal solution to the corresponding channel assignment problems with interference graphs being the triangular lattice and the square lattice, in which each base station demands a set of n channels that are t-separated and channels from two different stations at distance at most m must be \(j_1\)-separated. We also study a variation of n-fold t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labeling, namely, n-fold t-separated consecutive \(L(j_1,j_2,\ldots ,j_m)\)-labeling. And present the optimal n-fold t-separated consecutive L(j)-labelings of all complete graphs and cycles.     

Possible winner problems on partial tournaments: a parameterized study

We study possible winner problems related to the uncovered set and the Banks set on partial tournaments from the viewpoint of parameterized complexity. We first study a problem where given a partial tournament D and a subset X of vertices, we are asked to add some arcs to D such that all vertices in X are included in the uncovered set. We focus on two parameterizations: parameterized by |X| and parameterized by the number of arcs to be added. In addition, we study a parameterized variant of the problem which is to determine whether all vertices of X can be included in the uncovered set by reversing at most k arcs. Finally, we study some parameterizations of a possible winner problem on partial tournaments, where we are given a partial tournament D and a distinguished vertex p, and asked whether D has a maximal transitive subtournament with p being the 0-indegree vertex. These parameterized problems are related to the Banks set. We achieve \(\mathcal {XP}\) results, \(\mathcal {W}\)-hardness results as well as \(\mathcal {FPT}\) results along with a kernelization lower bound for the problems studied in this paper.     

A note on (<Emphasis Type="Italic">s</Emphasis>, <Emphasis Type="Italic">t</Emphasis>)-relaxed <Emphasis Type="Italic">L</Emphasis>(2, 1)-labeling of graphs

Let \(G=(V, E)\) be a graph. For two vertices u and v in G, we denote \(d_G(u, v)\) the distance between u and v. A vertex v is called an i-neighbor of u if \(d_G(u,v)=i\). Let s, t and k be nonnegative integers. An (s, t)-relaxed k-L(2, 1)-labeling of a graph G is an assignment of labels from \(\{0, 1, \ldots , k\}\) to the vertices of G if the following three conditions are met: (1) adjacent vertices get different labels; (2) for any vertex u of G, there are at most s 1-neighbors of u receiving labels from \(\{f(u)-1,f(u)+1\}\); (3) for any vertex u of G, the number of 2-neighbors of u assigned the label f(u) is at most t. The (s, t)-relaxed L(2, 1)-labeling number \(\lambda _{2,1}^{s,t}(G)\) of G is the minimum k such that G admits an (s, t)-relaxed k-L(2, 1)-labeling. In this article, we refute Conjecture 4 and Conjecture 5 stated in (Lin in J Comb Optim. doi: 10.1007/s10878-014-9746-9, 2013).     

Computing the <Emphasis Type="Italic">k</Emphasis>-resilience of a synchronized multi-robot system

The vertex arboricity va(G) of a graph G is the minimum number of colors the vertices can be colored so that each color class induces a forest. It was known that \(va(G)\le 3\) for every planar graph G. In this paper, we prove that \(va(G)\le 2\) if G is a planar graph without intersecting 5-cycles.     

On nonlinear multi-covering problems

In this paper we define the exact k-coverage problem, and study it for the special cases of intervals and circular-arcs. Given a set system consisting of a ground set of n points with integer demands \(\{d_0,\dots ,d_{n-1}\}\) and integer rewards, subsets of points, and an integer k, select up to k subsets such that the sum of rewards of the covered points is maximized, where point i is covered if exactly \(d_i\) subsets containing it are selected. Here we study this problem and some related optimization problems. We prove that the exact k-coverage problem with unbounded demands is NP-hard even for intervals on the real line and unit rewards. Our NP-hardness proof uses instances where some of the natural parameters of the problem are unbounded (each of these parameters is linear in the number of points). We show that this property is essential, as if we restrict (at least) one of these parameters to be a constant, then the problem is polynomial time solvable. Our polynomial time algorithms are given for various generalizations of the problem (in the setting where one of the parameters is a constant).     

Anti-forcing spectra of perfect matchings of graphs

Let M be a perfect matching of a graph G. The smallest number of edges whose removal to make M as the unique perfect matching in the resulting subgraph is called the anti-forcing number of M. The anti-forcing spectrum of G is the set of anti-forcing numbers of all perfect matchings in G, denoted by \(\hbox {Spec}_{af}(G)\). In this paper, we show that any finite set of positive integers can be the anti-forcing spectrum of a graph. We present two classes of hexagonal systems whose anti-forcing spectra are integer intervals. Finally, we show that determining the anti-forcing number of a perfect matching of a bipartite graph with maximum degree four is a NP-complete problem.