Source author record

Martin Vatshelle

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics Computational Complexity math.CO Artificial Intelligence

Catalog footprint

Research overview

5works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Recognition of Linear and Star Variants of Leaf Powers is in P

A $k$ -leaf power of a tree $T$ is a graph $G$ whose vertices are the leaves of $T$ and whose edges connect pairs of leaves whose distance in $T$ is at most $k$ . A graph is a leaf power if it is a $k$ -leaf power for some $k$ . Over 20 years ago, Nishimura et al. [J. Algorithms, 2002] asked if recognition of leaf powers was in P. Recently, Lafond [SODA 2022] showed an XP algorithm when parameterized by $k$ , while leaving the main question open. In this paper, we explore this question from the perspective of two alternative models of leaf powers, showing that both a linear and a star variant of leaf powers can be recognized in polynomial-time.

preprint2014arXiv

Faster Algorithms For Vertex Partitioning Problems Parameterized by Clique-width

Many NP-hard problems, such as Dominating Set, are FPT parameterized by clique-width. For graphs of clique-width $k$ given with a $k$ -expression, Dominating Set can be solved in $4^k n^{O(1)}$ time. However, no FPT algorithm is known for computing an optimal $k$ -expression. For a graph of clique-width $k$ , if we rely on known algorithms to compute a $(2^{3k}-1)$ -expression via rank-width and then solving Dominating Set using the $(2^{3k}-1)$ -expression, the above algorithm will only give a runtime of $4^{2^{3k}} n^{O(1)}$ . There have been results which overcome this exponential jump; the best known algorithm can solve Dominating Set in time $2^{O(k^2)} n^{O(1)}$ by avoiding constructing a $k$ -expression [Bui-Xuan, Telle, and Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theoret. Comput. Sci., 2013. doi:10.1016/j.tcs.2013.01.009]. We improve this to $2^{O(k\log k)}n^{O(1)}$ . Indeed, we show that for a graph of clique-width $k$ , a large class of domination and partitioning problems (LC-VSP), including Dominating Set, can be solved in $2^{O(k\log{k})} n^{O(1)}$ . Our main tool is a variant of rank-width using the rank of a $0$ - $1$ matrix over the rational field instead of the binary field.

preprint2014arXiv

Solving MaxSAT and #SAT on structured CNF formulas

In this paper we propose a structural parameter of CNF formulas and use it to identify instances of weighted MaxSAT and #SAT that can be solved in polynomial time. Given a CNF formula we say that a set of clauses is precisely satisfiable if there is some complete assignment satisfying these clauses only. Let the ps-value of the formula be the number of precisely satisfiable sets of clauses. Applying the notion of branch decompositions to CNF formulas and using ps-value as cut function, we define the ps-width of a formula. For a formula given with a decomposition of polynomial ps-width we show dynamic programming algorithms solving weighted MaxSAT and #SAT in polynomial time. Combining with results of 'Belmonte and Vatshelle, Graph classes with structured neighborhoods and algorithmic applications, Theor. Comput. Sci. 511: 54-65 (2013)' we get polynomial-time algorithms solving weighted MaxSAT and #SAT for some classes of structured CNF formulas. For example, we get $O(m^2(m + n)s)$ algorithms for formulas $F$ of $m$ clauses and $n$ variables and size $s$ , if $F$ has a linear ordering of the variables and clauses such that for any variable $x$ occurring in clause $C$ , if $x$ appears before $C$ then any variable between them also occurs in $C$ , and if $C$ appears before $x$ then $x$ occurs also in any clause between them. Note that the class of incidence graphs of such formulas do not have bounded clique-width.

preprint2011arXiv

k-Gap Interval Graphs

We initiate the study of a new parameterization of graph problems. In a multiple interval representation of a graph, each vertex is associated to at least one interval of the real line, with an edge between two vertices if and only if an interval associated to one vertex has a nonempty intersection with an interval associated to the other vertex. A graph on n vertices is a k-gap interval graph if it has a multiple interval representation with at most n+k intervals in total. In order to scale up the nice algorithmic properties of interval graphs (where k=0), we parameterize graph problems by k, and find FPT algorithms for several problems, including Feedback Vertex Set, Dominating Set, Independent Set, Clique, Clique Cover, and Multiple Interval Transversal. The Coloring problem turns out to be W[1]-hard and we design an XP algorithm for the recognition problem.

preprint2011arXiv

On graph classes with logarithmic boolean-width

Boolean-width is a recently introduced graph parameter. Many problems are fixed parameter tractable when parametrized by boolean-width, for instance "Minimum Weighted Dominating Set" (MWDS) problem can be solved in $O^*(2^{3k})$ time given a boolean-decomposition of width $k$ , hence for all graph classes where a boolean-decomposition of width $O(\log n)$ can be found in polynomial time, MWDS can be solved in polynomial time. We study graph classes having boolean-width $O(\log n)$ and problems solvable in $O^*(2^{O(k)})$ , combining these two results to design polynomial algorithms. We show that for trapezoid graphs, circular permutation graphs, convex graphs, Dilworth- $k$ graphs, circular arc graphs and complements of $k$ -degenerate graphs, boolean-decompositions of width $O(\log n)$ can be found in polynomial time. We also show that circular $k$ -trapezoid graphs have boolean-width $O(\log n)$ , and find such a decomposition if a circular $k$ -trapezoid intersection model is given. For many of the graph classes we also prove that they contain graphs of boolean-width $Θ(\log n)$ . Further we apply the results from \cite{boolw2} to give a new polynomial time algorithm solving all vertex partitioning problems introduced by Proskurowski and Telle \cite{TP97}. This extends previous results by Kratochvíl, Manuel and Miller \cite{KMM95} showing that a large subset of the vertex partitioning problems are polynomial solvable on interval graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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