
Records 
Links 

Author 
Gaspers, S.; Liedloff, M.; Stein, M.; Suchan, K. 


Title 
Complexity of splits reconstruction for lowdegree trees 
Type 


Year 
2015 
Publication 
Discrete Applied Mathematics 
Abbreviated Journal 
Discret Appl. Math. 


Volume 
180 
Issue 

Pages 
89100 


Keywords 
Reconstruction of trees; Computational complexity; Computational chemistry 


Abstract 
Given a vertexweighted tree T, the split of an edge em T is the minimum over the weights of the two trees obtained by removing e from T, where the weight of a tree is the sum of weights of its vertices. Given a set of weighted vertices V and a multiset of integers s, we consider the problem of constructing a tree on V whose splits correspond to s. The problem is known to be NPcomplete, even when all vertices have unit weight and the maximum vertex degree of T is required to be at most 4. We show that the problem is strongly NPcomplete when T is required to be a path, the problem is NPcomplete when all vertices have unit weight and the maximum degree of T is required to be at most 3, and it remains NPcomplete when all vertices have unit weight and T is required to be a caterpillar with unbounded hair length and maximum degree at most 3. We also design polynomial time algorithms for the variant where T is required to be a path and the number of distinct vertex weights is constant, and the variant where all vertices have unit weight and T has a constant number of leaves. The latter algorithm is not only polynomial when the number of leaves, k, is a constant, but also is a fixedparameter algorithm for parameter k. Finally, we shortly discuss the problem when the vertex weights are not given but can be freely chosen by an algorithm. The considered problem is related to building libraries of chemical compounds used for drug design and discovery. In these inverse problems, the goal is to generate chemical compounds having desired structural properties, as there is a strong relation between structural invariants of the particles, such as the Wiener index and, less directly, the problem under consideration here, and physicochemical properties of the substance. (C) 2014 Elsevier B.V. All rights reserved. 


Address 
[Gaspers, Serge] Univ New S Wales, Sch Comp Sci & Engn, Sydney, NSW 2052, Australia, Email: sergeg@cse.unsw.edu.au; 


Corporate Author 

Thesis 



Publisher 
Elsevier Science Bv 
Place of Publication 

Editor 



Language 
English 
Summary Language 

Original Title 



Series Editor 

Series Title 

Abbreviated Series Title 



Series Volume 

Series Issue 

Edition 



ISSN 
0166218x 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000346545500009 
Approved 



Call Number 
UAI @ eduardo.moreno @ 
Serial 
433 

Permanent link to this record 




Author 
Liedloff, M.; Montealegre, P.; Todinca, I. 


Title 
Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques 
Type 


Year 
2019 
Publication 
Algorithmica 
Abbreviated Journal 
Algorithmica 


Volume 
81 
Issue 
3 
Pages 
9861005 


Keywords 
FPT algorithms; Treewidth; Potential maximal cliques 


Abstract 
Let P(G,X) be a property associating a boolean value to each pair (G,X) where G is a graph and X is a vertex subset. Assume that P is expressible in counting monadic second order logic (CMSO) and let t be an integer constant. We consider the following optimization problem: given an input graph G=(V,E), find subsets XFV such that the treewidth of G[F] is at most t, property P(G[F],X) is true and X is of maximum size under these conditions. The problem generalizes many classical algorithmic questions, e.g., Longest Induced Path, Maximum Induced Forest, IndependentHPacking, etc. Fomin et al. (SIAM J Comput 44(1):5487, 2015) proved that the problem is polynomial on the class of graph Gpoly, i.e. the graphs having at most poly(n) minimal separators for some polynomial poly. Here we consider the class Gpoly+kv, formed by graphs of Gpoly to which we add a set of at most k vertices with arbitrary adjacencies, called modulator. We prove that the generic optimization problem is fixed parameter tractable on Gpoly+kv, with parameter k, if the modulator is also part of the input. 


Address 
[Liedloff, Mathieu; Todinca, Ioan] Univ Orleans, INSA Ctr Val Loire, LIFO, EA 4022, Orleans, France, Email: mathieu.liedloff@univorleans.fr; 


Corporate Author 

Thesis 



Publisher 
Springer 
Place of Publication 

Editor 



Language 
English 
Summary Language 

Original Title 



Series Editor 

Series Title 

Abbreviated Series Title 



Series Volume 

Series Issue 

Edition 



ISSN 
01784617 
ISBN 

Medium 



Area 

Expedition 

Conference 



Notes 
WOS:000460105700003 
Approved 



Call Number 
UAI @ eduardo.moreno @ 
Serial 
989 

Permanent link to this record 