BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Dimitrios M. Thilikos

Dimitrios M. Thilikos contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.COData Structures and AlgorithmsDiscrete MathematicsComputational ComplexityMachine Learning

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
11works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2022arXiv

A linear fixed parameter tractable algorithm for connected pathwidth

The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search where we are given a system of tunnels that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher on a vertex or removes a searcher from a vertex and where an edge is cleaned when both endpoints are simultaneously occupied by searchers. It was proved that the minimum number of searchers required for a successful cleaning strategy is equal to the pathwidth of the graph plus one. Two desired characteristics for a cleaning strategy is to be monotone (no recontamination occurs) and connected (clean territories always remain connected). Under these two demands, the number of searchers is equivalent to a variant of pathwidth called {\em connected pathwidth}. We prove that connected pathwidth is fixed parameter tractable, in particular we design a $2^{O(k^2)}\cdot n$ time algorithm that checks whether the connected pathwidth of $G$ is at most $k.$ This resolves an open question by [Dereniowski, Osula, and Rz{ą}{ż}ewski, Finding small-width connected path-decompositions in polynomial time. Theor. Comput. Sci., 794:85-100, 2019]. For our algorithm, we enrich the typical sequence technique that is able to deal with the connectivity demand. Typical sequences have been introduced in [Bodlaender and Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358-402, 1996] for the design of linear parameterized algorithms for treewidth and pathwidth. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted so to deliver linear parameterized algorithms for the connected variants of other width parameters as well.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Combing a Linkage in an Annulus

A linkage in a graph $G$ of size $k$ is a subgraph $L$ of $G$ whose connected components are $k$ paths. The pattern of a linkage of size $k$ is the set of $k$ pairs formed by the endpoints of these paths. A consequence of the Unique Linkage Theorem is the following: there exists a function $f:\mathbb{N}\to\mathbb{N}$ such that if a plane graph $G$ contains a sequence $\mathcal{C}$ of at least $f(k)$ nested cycles and a linkage of size at most $k$ whose pattern vertices lay outside the outer cycle of $\mathcal{C},$ then $G$ contains a linkage with the same pattern avoiding the inner cycle of $\mathcal{C}$. In this paper we prove the following variant of this result: Assume that all the cycles in $\mathcal{C}$ are "orthogonally" traversed by a linkage $P$ and $L$ is a linkage whose pattern vertices may lay either outside the outer cycle or inside the inner cycle of $\mathcal{C}:=[C_{1},\ldots,C_{p},\ldots,C_{2p-1}]$. We prove that there are two functions $g,f:\mathbb{N}\to\mathbb{N}$, such that if $L$ has size at most $k$, $P$ has size at least $f(k),$ and $|\mathcal{C}|\geq g(k)$, then there is a linkage with the same pattern as $L$ that is "internally combed" by $P$, in the sense that $L\cap C_{p}\subseteq P\cap C_{p}$. In fact, we prove this result in the most general version where the linkage $L$ is $s$-scattered: no two vertices of distinct paths of $L$ are within distance at most $s$. We deduce several variants of this result in the cases where $s=0$ and $s>0$. These variants permit the application of the unique linkage theorem on several path routing problems on embedded graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Contraction Bidimensionality of Geometric Intersection Graphs

Given a graph $G$, we define ${\bf bcg}(G)$ as the minimum $k$ for which $G$ can be contracted to the uniformly triangulated grid $Γ_{k}$. A graph class ${\cal G}$ has the SQG${\bf C}$ property if every graph $G\in{\cal G}$ has treewidth $\mathcal{O}({\bf bcg}(G)^{c})$ for some $1\leq c<2$. The SQG${\bf C}$ property is important for algorithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a wide family of graph classes that satisfy the SQG${\bf C}$ property. This family includes, in particular, bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for contraction bidimensional problems.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Hcore-Init: Neural Network Initialization based on Graph Degeneracy

Neural networks are the pinnacle of Artificial Intelligence, as in recent years we witnessed many novel architectures, learning and optimization techniques for deep learning. Capitalizing on the fact that neural networks inherently constitute multipartite graphs among neuron layers, we aim to analyze directly their structure to extract meaningful information that can improve the learning process. To our knowledge graph mining techniques for enhancing learning in neural networks have not been thoroughly investigated. In this paper we propose an adapted version of the k-core structure for the complete weighted multipartite graph extracted from a deep learning architecture. As a multipartite graph is a combination of bipartite graphs, that are in turn the incidence graphs of hypergraphs, we design k-hypercore decomposition, the hypergraph analogue of k-core degeneracy. We applied k-hypercore to several neural network architectures, more specifically to convolutional neural networks and multilayer perceptrons for image recognition tasks after a very short pretraining. Then we used the information provided by the hypercore numbers of the neurons to re-initialize the weights of the neural network, thus biasing the gradient optimization scheme. Extensive experiments proved that k-hypercore outperforms the state-of-the-art initialization methods.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Block Elimination Distance

We introduce the block elimination distance as a measure of how close a graph is to some particular graph class. Formally, given a graph class ${\cal G}$, the class ${\cal B}({\cal G})$ contains all graphs whose blocks belong to ${\cal G}$ and the class ${\cal A}({\cal G})$ contains all graphs where the removal of a vertex creates a graph in ${\cal G}$. Given a hereditary graph class ${\cal G}$, we recursively define ${\cal G}^{(k)}$ so that ${\cal G}^{(0)}={\cal B}({\cal G})$ and, if $k\geq 1$, ${\cal G}^{(k)}={\cal B}({\cal A}({\cal G}^{(k-1)}))$. The block elimination distance of a graph $G$ to a graph class ${\cal G}$ is the minimum $k$ such that $G\in{\cal G}^{(k)}$ and can be seen as an analog of the elimination distance parameter, with the difference that connectivity is now replaced by biconnectivity. We show that, for every non-trivial hereditary class ${\cal G}$, the problem of deciding whether $G\in{\cal G}^{(k)}$ is NP-complete. We focus on the case where ${\cal G}$ is minor-closed and we study the minor obstruction set of ${\cal G}^{(k)}$. We prove that the size of the obstructions of ${\cal G}^{(k)}$ is upper bounded by some explicit function of $k$ and the maximum size of a minor obstruction of ${\cal G}$. This implies that the problem of deciding whether $G\in{\cal G}^{(k)}$ is constructively fixed parameter tractable, when parameterized by $k$. Our results are based on a structural characterization of the obstructions of ${\cal B}({\cal G})$, relatively to the obstructions of ${\cal G}$. We give two graph operations that generate members of ${\cal G}^{(k)}$ from members of ${\cal G}^{(k-1)}$ and we prove that this set of operations is complete for the class ${\cal O}$ of outerplanar graphs. This yields the identification of all members ${\cal O}\cap{\cal G}^{(k)}$, for every $k\in\mathbb{N}$ and every non-trivial minor-closed graph class ${\cal G}$.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

k-apices of minor-closed graph classes. II. Parameterized algorithms

Let ${\cal G}$ be a minor-closed graph class. We say that a graph $G$ is a $k$-apex of ${\cal G}$ if $G$ contains a set $S$ of at most $k$ vertices such that $G\setminus S$ belongs to ${\cal G}$. We denote by ${\cal A}_k ({\cal G})$ the set of all graphs that are $k$-apices of ${\cal G}.$ In the first paper of this series we obtained upper bounds on the size of the graphs in the minor-obstruction set of ${\cal A}_k ({\cal G})$, i.e., the minor-minimal set of graphs not belonging to ${\cal A}_k ({\cal G}).$ In this article we provide an algorithm that, given a graph $G$ on $n$ vertices, runs in $2^{{\sf poly}(k)}\cdot n^3$-time and either returns a set $S$ certifying that $G \in {\cal A}_k ({\cal G})$, or reports that $G \notin {\cal A}_k ({\cal G})$. Here ${\sf poly}$ is a polynomial function whose degree depends on the maximum size of a minor-obstruction of ${\cal G}.$ In the special case where ${\cal G}$ excludes some apex graph as a minor, we give an alternative algorithm running in $2^{{\sf poly}(k)}\cdot n^2$-time.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Bidimensionality and Kernels

Bidimensionality Theory was introduced by [E.D. Demaine, F.V. Fomin, M.Hajiaghayi, and D.M. Thilikos. Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs, J. ACM, 52 (2005), pp.866--893] as a tool to obtain sub-exponential time parameterized algorithms on H-minor-free graphs. In [E.D. Demaine and M.Hajiaghayi, Bidimensionality: new connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2005, pp.590--601] this theory was extended in order to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this work, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In particular, we prove that every minor (respectively contraction) bidimensional problem that satisfies a separation property and is expressible in Countable Monadic Second Order Logic (CMSO), admits a linear kernel for classes of graphs that exclude a fixed graph (respectively an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems g graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Edge Degeneracy: Algorithmic and Structural Results

We consider a cops and robber game where the cops are blocking edges of a graph, while the robber occupies its vertices. At each round of the game, the cops choose some set of edges to block and right after the robber is obliged to move to another vertex traversing at most $s$ unblocked edges ($s$ can be seen as the speed of the robber). Both parts have complete knowledge of the opponent&#39;s moves and the cops win when they occupy all edges incident to the robbers position. We introduce the capture cost on $G$ against a robber of speed $s$. This defines a hierarchy of invariants, namely $δ^{1}_{\rm e},δ^{2}_{\rm e},\ldots,δ^{\infty}_{\rm e}$, where $δ^{\infty}_{\rm e}$ is an edge-analogue of the admissibility graph invariant, namely the {\em edge-admissibility} of a graph. We prove that the problem asking wether $δ^{s}_{\rm e}(G)\leq k$, is polynomially solvable when $s\in \{1,2,\infty\}$ while, otherwise, it is NP-complete. Our main result is a structural theorem for graphs of bounded edge-admissibility. We prove that every graph of edge-admissibility at most $k$ can be constructed using $(\leq k)$-edge-sums, starting from graphs whose all vertices, except possibly from one, have degree at most $k$. Our structural result is approximately tight in the sense that graphs generated by this construction always have edge-admissibility at most $2k-1$. Our proofs are based on a precise structural characterization of the graphs that do not contain $θ_{r}$ as an immersion, where $θ_{r}$ is the graph on two vertices and $r$ parallel edges.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Structure and enumeration of K4-minor-free links and link-diagrams

We study the class L of link-types that admit a K4-minor-free diagram, i.e., they can be projected on the plane so that the resulting graph does not contain any subdivision of K4. We prove that L is the closure of a subclass of torus links under the operation of connected sum. Using this structural result, we enumerate L and subclasses of it, with respect to the minimum number of crossings or edges in a projection of L&#39; in L. Further, we obtain counting formulas and asymptotic estimates for the connected K4-minor-free link-diagrams, minimal K4-minor-free link-diagrams, and K4-minor-free diagrams of the unknot.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Partial complementation of graphs

A partial complement of the graph $G$ is a graph obtained from $G$ by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph $G$ and graph class $\mathcal{G}$, is there a partial complement of $G$ which is in $\mathcal{G}$? We show that this problem can be solved in polynomial time for various choices of the graphs class $\mathcal{G}$, such as bipartite, degenerate, or cographs. We complement these results by proving that the problem is NP-complete when $\mathcal{G}$ is the class of $r$-regular graphs.

0 citations0 reviewsNo code linkedOpen access