Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTwin-width and generalized coloring numbers
119
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper, we prove that a graph $G$ with no $K_{s,s}$-subgraph and twin-width $d$ has $r$-admissibility and $r$-coloring numbers bounded from above by an exponential function of $r$ and that we can construct graphs achieving such a dependency in $r$.
rate research
Read More
For a given graph $G$, the least integer $kgeq 2$ such that for every Abelian group $mathcal{G}$ of order $k$ there exists a proper edge labeling $f:E(G)rightarrow mathcal{G}$ so that $sum_{xin N(u)}f(xu) eq sum_{xin N(v)}f(xv)$ for each edge $uvin E(G)$ is called the textit{group twin chromatic index} of $G$ and denoted by $chi_g(G)$. This graph invariant is related to a few well-known problems in the field of neighbor distinguishing graph colorings. We conjecture that $chi_g(G)leq Delta(G)+3$ for all graphs without isolated edges, where $Delta(G)$ is the maximum degree of $G$, and provide an infinite family of connected graph (trees) for which the equality holds. We prove that this conjecture is valid for all trees, and then apply this result as the base case for proving a general upper bound for all graphs $G$ without isolated edges: $chi_g(G)leq 2(Delta(G)+{rm col}(G))-5$, where ${rm col}(G)$ denotes the coloring number of $G$. This improves the best known upper bound known previously only for the case of cyclic groups $mathbb{Z}_k$.
We establish a list of characterizations of bounded twin-width for hereditary, totally ordered binary structures. This has several consequences. First, it allows us to show that a (hereditary) class of matrices over a finite alphabet either contains at least $n!$ matrices of size $n times n$, or at most $c^n$ for some constant $c$. This generalizes the celebrated Stanley-Wilf conjecture/Marcus-Tardos theorem from permutation classes to any matrix class over a finite alphabet, answers our small conjecture [SODA 21] in the case of ordered graphs, and with more work, settles a question first asked by Balogh, Bollobas, and Morris [Eur. J. Comb. 06] on the growth of hereditary classes of ordered graphs. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width.
We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time $f(d,k)n$ for $n$-vertex graphs given with a witness that the twin-width is at most $d$, called $d$-contraction sequence or $d$-sequence, and formulas of size $k$ [Bonnet et al., FOCS 20]. The inevitable price to pay for such a general result is that $f$ is a tower of exponentials of height roughly $k$. In this paper, we show that algorithms based on twin-width need not be impractical. We present $2^{O(k)}n$-time algorithms for $k$-Independent Set, $r$-Scattered Set, $k$-Clique, and $k$-Dominating Set when an $O(1)$-sequence is provided. We further show how to solve weighted $k$-Independent Set, Subgraph Isomorphism, and Induced Subgraph Isomorphism, in time $2^{O(k log k)}n$. These algorithms are based on a dynamic programming scheme following the sequence of contractions forward. We then show a second algorithmic use of the contraction sequence, by starting at its end and rewinding it. As an example, we establish that bounded twin-width classes are $chi$-bounded. This significantly extends the $chi$-boundedness of bounded rank-width classes, and does so with a very concise proof. The third algorithmic use of twin-width builds on the second one. Playing the contraction sequence backward, we show that bounded twin-width graphs can be edge-partitioned into a linear number of bicliques, such that both sides of the bicliques are on consecutive vertices, in a fixed vertex ordering. Given that biclique edge-partition, we show how to solve the unweighted Single-Source Shortest Paths and hence All-Pairs Shortest Paths in sublinear time $O(n log n)$ and time $O(n^2 log n)$, respectively. Finally we show that Min Dominating Set and related problems have constant integrality gaps on bounded twin-width classes, thereby getting constant approximations on these classes.
Inspired by a width invariant defined on permutations by Guillemot and Marx, the twin-width invariant has been recently introduced by Bonnet, Kim, Thomasse, and Watrigant. We prove that a class of binary relational structures (that is: edge-colored partially directed graphs) has bounded twin-width if and only if it is a first-order transduction of a~proper permutation class. As a by-product, it shows that every class with bounded twin-width contains at most $2^{O(n)}$ pairwise non-isomorphic $n$-vertex graphs.
We study the existence of polynomial kernels, for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. Our main result is that a polynomial kernel for $k$-Dominating Set on graphs of twin-width at most 4 would contradict a standard complexity-theoretic assumption. The reduction is quite involved, especially to get the twin-width upper bound down to 4, and can be tweaked to work for Connected $k$-Dominating Set and Total $k$-Dominating Set (albeit with a worse upper bound on the twin-width). The $k$-Independent Set problem admits the same lower bound by a much simpler argument, previously observed [ICALP 21], which extends to $k$-Independent Dominating Set, $k$-Path, $k$-Induced Path, $k$-Induced Matching, etc. On the positive side, we obtain a simple quadratic vertex kernel for Connected $k$-Vertex Cover and Capacitated $k$-Vertex Cover on graphs of bounded twin-width. Interestingly the kernel applies to graphs of Vapnik-Chervonenkis density 1, and does not require a witness sequence. We also present a more intricate $O(k^{1.5})$ vertex kernel for Connected $k$-Vertex Cover. Finally we show that deciding if a graph has twin-width at most 1 can be done in polynomial time, and observe that most optimization/decision graph problems can be solved in polynomial time on graphs of twin-width at most 1.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
