Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Lexicographic Method for the Threshold Cover Problem
101
0
0.0
(
0
)
Added by
Mathew Francis
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Threshold graphs are a class of graphs that have many equivalent definitions and have applications in integer programming and set packing problems. A graph is said to have a threshold cover of size $k$ if its edges can be covered using $k$ threshold graphs. Chvatal and Hammer, in 1977, defined the threshold dimension $mathrm{th}(G)$ of a graph $G$ to be the least integer $k$ such that $G$ has a threshold cover of size $k$ and observed that $mathrm{th}(G)geqchi(G^*)$, where $G^*$ is a suitably constructed auxiliary graph. Raschle and Simon~[Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, STOC 95, pages 650--661, 1995] proved that $mathrm{th}(G)=chi(G^*)$ whenever $G^*$ is bipartite. We show how the lexicographic method of Hell and Huang can be used to obtain a completely new and, we believe, simpler proof for this result. For the case when $G$ is a split graph, our method yields a proof that is much shorter than the ones known in the literature.
rate research
Read More
In this paper, we study a primal and dual relationship about triangles: For any graph $G$, let $ u(G)$ be the maximum number of edge-disjoint triangles in $G$, and $tau(G)$ be the minimum subset $F$ of edges such that $G setminus F$ is triangle-free. It is easy to see that $ u(G) leq tau(G) leq 3 u(G)$, and in fact, this rather obvious inequality holds for a much more general primal-dual relation between $k$-hyper matching and covering in hypergraphs. Tuza conjectured in $1981$ that $tau(G) leq 2 u(G)$, and this question has received attention from various groups of researchers in discrete mathematics, settling various special cases such as planar graphs and generalized to bounded maximum average degree graphs, some cases of minor-free graphs, and very dense graphs. Despite these efforts, the conjecture in general graphs has remained wide open for almost four decades. In this paper, we provide a proof of a non-trivial consequence of the conjecture; that is, for every $k geq 2$, there exist a (multi)-set $F subseteq E(G): |F| leq 2k u(G)$ such that each triangle in $G$ overlaps at least $k$ elements in $F$. Our result can be seen as a strengthened statement of Krivelevichs result on the fractional version of Tuzas conjecture (and we give some examples illustrating this.) The main technical ingredient of our result is a charging argument, that locally identifies edges in $F$ based on a local view of the packing solution. This idea might be useful in further studying the primal-dual relations in general and the Tuzas conjecture in particular.
A tessellation of a graph is a partition of its vertices into vertex disjoint cliques. A tessellation cover of a graph is a set of tessellations that covers all of its edges. The $t$-tessellability problem aims to decide whether there is a tessellation cover of the graph with $t$ tessellations. This problem is motivated by its applications to quantum walk models, in especial, the evolution operator of the staggered model is obtained from a graph tessellation cover. We establish upper bounds on the tessellation cover number given by the minimum between the chromatic index of the graph and the chromatic number of its clique graph and we show graph classes for which these bounds are tight. We prove $mathcal{NP}$-completeness for $t$-tessellability if the instance is restricted to planar graphs, chordal (2,1)-graphs, (1,2)-graphs, diamond-free graphs with diameter five, or for any fixed $t$ at least 3. On the other hand, we improve the complexity for 2-tessellability to a linear-time algorithm.
We give an $O(n^4)$ algorithm to find a minimum clique cover of a (bull, $C_4$)-free graph, or equivalently, a minimum colouring of a (bull, $2K_2$)-free graph, where $n$ is the number of vertices of the graphs.
The input of the Test Cover problem consists of a set $V$ of vertices, and a collection ${cal E}={E_1,..., E_m}$ of distinct subsets of $V$, called tests. A test $E_q$ separates a pair $v_i,v_j$ of vertices if $|{v_i,v_j}cap E_q|=1.$ A subcollection ${cal T}subseteq {cal E}$ is a test cover if each pair $v_i,v_j$ of distinct vertices is separated by a test in ${cal T}$. The objective is to find a test cover of minimum cardinality, if one exists. This problem is NP-hard. We consider two parameterizations the Test Cover problem with parameter $k$: (a) decide whether there is a test cover with at most $k$ tests, (b) decide whether there is a test cover with at most $|V|-k$ tests. Both parameterizations are known to be fixed-parameter tractable. We prove that none have a polynomial size kernel unless $NPsubseteq coNP/poly$. Our proofs use the cross-composition method recently introduced by Bodlaender et al. (2011) and parametric duality introduced by Chen et al. (2005). The result for the parameterization (a) was an open problem (private communications with Henning Fernau and Jiong Guo, Jan.-Feb. 2012). We also show that the parameterization (a) admits a polynomial size kernel if the size of each test is upper-bounded by a constant.
Many hard algorithmic problems dealing with graphs, circuits, formulas and constraints admit polynomial-time upper bounds if the underlying graph has small treewidth. The same problems often encourage reducing the maximal degree of vertices to simplify theoretical arguments or address practical concerns. Such degree reduction can be performed through a sequence of splittings of vertices, resulting in an _expansion_ of the original graph. We observe that the treewidth of a graph may increase dramatically if the splittings are not performed carefully. In this context we address the following natural question: is it possible to reduce the maximum degree to a constant without substantially increasing the treewidth? Our work answers the above question affirmatively. We prove that any simple undirected graph G=(V, E) admits an expansion G=(V, E) with the maximum degree <= 3 and treewidth(G) <= treewidth(G)+1. Furthermore, such an expansion will have no more than 2|E|+|V| vertices and 3|E| edges; it can be computed efficiently from a tree-decomposition of G. We also construct a family of examples for which the increase by 1 in treewidth cannot be avoided.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
