Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLinear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs
179
0
0.0
(
0
)
Added by
Nathan Lindzey
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Lekkerkerker and Boland characterized the minimal forbidden induced subgraphs for the class of interval graphs. We give a linear-time algorithm to find one in any graph that is not an interval graph. Tucker characterized the minimal forbidden submatrices of binary matrices that do not have the consecutive-ones property. We give a linear-time algorithm to find one in any binary matrix that does not have the consecutive-ones property.
rate research
Read More
Let $mathcal{C}$ and $mathcal{D}$ be hereditary graph classes. Consider the following problem: given a graph $Ginmathcal{D}$, find a largest, in terms of the number of vertices, induced subgraph of $G$ that belongs to $mathcal{C}$. We prove that it can be solved in $2^{o(n)}$ time, where $n$ is the number of vertices of $G$, if the following conditions are satisfied: * the graphs in $mathcal{C}$ are sparse, i.e., they have linearly many edges in terms of the number of vertices; * the graphs in $mathcal{D}$ admit balanced separators of size governed by their density, e.g., $mathcal{O}(Delta)$ or $mathcal{O}(sqrt{m})$, where $Delta$ and $m$ denote the maximum degree and the number of edges, respectively; and * the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph. This leads, for example, to the following corollaries for specific classes $mathcal{C}$ and $mathcal{D}$: * a largest induced forest in a $P_t$-free graph can be found in $2^{tilde{mathcal{O}}(n^{2/3})}$ time, for every fixed $t$; and * a largest induced planar graph in a string graph can be found in $2^{tilde{mathcal{O}}(n^{3/4})}$ time.
Suppose that we are given two independent sets $I_b$ and $I_r$ of a graph such that $|I_b|=|I_r|$, and imagine that a token is placed on each vertex in $I_b$. Then, the sliding token problem is to determine whether there exists a sequence of independent sets which transforms $I_b$ into $I_r$ so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we thus study the problem restricted to trees, and give the following three results: (1) the decision problem is solvable in linear time; (2) for a yes-instance, we can find in quadratic time an actual sequence of independent sets between $I_b$ and $I_r$ whose length (i.e., the number of token-slides) is quadratic; and (3) there exists an infinite family of instances on paths for which any sequence requires quadratic length.
Inductive $k$-independent graphs generalize chordal graphs and have recently been advocated in the context of interference-avoiding wireless communication scheduling. The NP-hard problem of finding maximum-weight induced $c$-colorable subgraphs, which is a generalization of finding maximum independent sets, naturally occurs when selecting $c$ sets of pairwise non-conflicting jobs (modeled as graph vertices). We investigate the parameterized complexity of this problem on inductive $k$-independent graphs. We show that the Independent Set problem is W[1]-hard even on 2-simplicial 3-minoes---a subclass of inductive 2-independent graphs. In contrast, we prove that the more general Maximum $c$-Colorable Subgraph problem is fixed-parameter tractable on edge-wise unions of cluster and chordal graphs, which are 2-simplicial. In both cases, the parameter is the solution size. Aside from this, we survey other graph classes between inductive 1-inductive and inductive 2-inductive graphs with applications in scheduling.
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.
Let $H$ be a fixed $k$-vertex graph with $m$ edges and minimum degree $d >0$. We use the learning graph framework of Belovs to show that the bounded-error quantum query complexity of determining if an $n$-vertex graph contains $H$ as a subgraph is $O(n^{2-2/k-t})$, where $ t = max{frac{k^2- 2(m+1)}{k(k+1)(m+1)}, frac{2k - d - 3}{k(d+1)(m-d+2)}}$. The previous best algorithm of Magniez et al. had complexity $widetilde O(n^{2-2/k})$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
