检索结果-内蒙古大学图书馆

parameterized complexity of connected even/odd subgraph problems

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2014年第1期80卷 157-179页

作者： Fomin, Fedor V. Golovach, Petr A. Univ Bergen Dept Informat N-5020 Bergen Norway

In 2011, Cai an Yang initiated the systematic parameterized complexity study of the following set of problems around Eulerian graphs: for a given graph G and integer k, the task is to decide if G contains a (connected) subgraph with k vertices (edges) with all vertices of even (odd) degrees. They succeed to establish the parameterized complexity of all cases except two, when we ask about: a connected k-edge subgraph with all vertices of odd degrees, the problem known as k-EDGE CONNECTED ODD SUBGRAPH;and a connected k-vertex induced subgraph with all vertices of even degrees, the problem known as k-VERTEX EULERIAN SUBGRAPH. We show that k-EDGE CONNECTED ODD SUBGRAPH is FPT and k-VERTEX EULERIAN SUBGRAPH is W[1]-hard. Our EFT algorithm is based on a novel combinatorial result on the treewidth of minimal connected odd graphs with even amount of edges. (C) 2013 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Euler graph Even graph Odd graph Treewidth

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity of the Shared Center Problem

引用

ALGORITHMICA 2014年第2期69卷 269-293页

作者： Chen, Zhi-Zhong Ma, Wenji Wang, Lusheng Tokyo Denki Univ Div Informat Syst Design Hiki Saitama 3590394 Japan City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China

Recently, the shared center (SC) problem has been proposed as a mathematical model for inferring the allele-sharing status of a given set of individuals using a database of confirmed haplotypes as reference. The problem was proved to be NP-complete and a ratio-2 polynomial-time approximation algorithm was designed for its minimization version (called the closest shared center (CSC) problem). In this paper, we consider the parameterized complexity of the SC problem. First, we show that the SC problem is W[1]-hard with parameters d and n, where d and n are the radius and the number of (diseased or normal) individuals in the input, respectively. Then, we present two asymptotically optimal parameterized algorithms for the problem and apply them to linkage analysis.

关键词： Haplotype inference Linkage analysis Pedigree Allele-sharing status parameterized complexity parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2014年第7期80卷 1430-1447页

作者： Fomin, Fedor V. Kratsch, Stefan Pilipczuk, Marcin Pilipczuk, Michal Villanger, Yngve Univ Bergen Dept Informat N-5020 Bergen Norway Tech Univ Berlin Berlin Germany Univ Warsaw Inst Informat PL-00325 Warsaw Poland

In the CLUSTER EDITING problem, also known as CORRELATION CLUSTERING, we are given an undirected n-vertex graph G and a positive integer k. The task is to decide if G can be transformed into a cluster graph, i.e., a disjoint union of cliques, by changing at most k adjacencies, i.e. by adding/deleting at most k edges. We give a subexponential-time parameterized algorithm that in time 2(O(root pk)) + n(O(1)) decides whether G can be transformed into a cluster graph with exactly p cliques by changing at most k adjacencies. Our algorithmic findings are complemented by the following tight lower bound on the asymptotic behavior of our algorithm. We show that unless ETH fails, for any constant 0 < sigma <= 1, there is p = Theta(k(sigma)) such that there is no algorithm deciding in time 2(o(root pk)) . n(O)(1) whether G can be transformed into a cluster graph with at most p cliques by changing at most k adjacencies. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Cluster editing Correlation clustering parameterized complexity Subexponential-time algorithms Exponential-time hypothesis

来源：评论

学校读者我要写书评

暂无评论

Gerrymandering on Graphs: Computational complexity and parameterized Algorithms 14th

Gerrymandering on Graphs: Computational Complexity and Param...

引用

14th International Symposium on Algorithmic Game Theory (SAGT)

作者： Gupta, Sushmita Jain, Pallavi Panolan, Fahad Roy, Sanjukta Saurabh, Saket HBNI Inst Math Sci Chennai Tamil Nadu India Indian Inst Technol Jodhpur Jodhpur Rajasthan India Indian Inst Technol Hyderabad Hyderabad India TU Wien Vienna Austria

ISBN: (纸本)9783030859466;9783030859473

This paper studies gerrymandering on graphs from a computational viewpoint (introduced by Cohen-Zemach et al. [AAMAS 2018] and continued by Ito et al. [AAMAS 2019]). Our contributions are twofold: conceptual and computational. We propose a generalization of the model studied by Ito et al., where the input consists of a graph on n vertices representing the set of voters, a set of m candidates C, a weight function w(v) : C -> Z(+) for each voter v is an element of V (G) representing the preference of the voter over the candidates, a distinguished candidate p is an element of C, and a positive integer k. The objective is to decide if it is possible to partition the vertex set into k districts (i.e., pairwise disjoint connected sets) such that the candidate p wins more districts than any other candidate. There are several natural parameters associated with the problem: the number of districts (k), the number of voters (n), and the number of candidates (m). The problem is known to be NP-complete even if k = 2, m = 2, and G is either a complete bipartite graph (in fact K-2,K-n, i.e., partitions of size 2 and n) or a complete graph. Moreover, recently we and Bentert et al. [WG 2021], independently, showed that the problem is NP-hard for paths. This means that the search for FPT algorithms needs to focus either on the parameter n, or subclasses of forest (as the problem is NP-complete on K-2,K-n, a family of graphs that can be transformed into a forest by deleting one vertex). Circumventing these intractability results we successfully obtain the following algorithmic results. - A 2(n) (n + m)(O(1)) time algorithm on general graphs. - FPT algorithm with respect to k (an algorithm with running time 2(O(k)) n(O(1))) on paths in both deterministic and randomized settings, even for arbitrary weight functions. Whether the problem is FPT parameterized by k on trees remains an interesting open problem. Our algorithmic results use sophisticated technical tools such as representative

关键词： Gerrymandering parameterized complexity Representative set

来源：评论

学校读者我要写书评

暂无评论

Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask) 31

Everything you always wanted to know about the parameterized...

引用

31st International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Marx, Daniel Pilipczuk, Michal Hungarian Acad Sci MTA SZTAKI Comp & Automat Res Inst Budapest Hungary Univ Bergen Dept Informat Bergen Norway

ISBN: (纸本)9783939897651

Given two graphs H and G, the SUBGRAPH ISOMORPHISM problem asks if H is isomorphic to a subgraph of G. While NP-hard in general, algorithms exist for various parameterized versions of the problem. However, the literature contains very little guidance on which combinations of parameters can or cannot be exploited algorithmically. Our goal is to systematically investigate the possible parameterized algorithms that can exist for SUBGRAPH ISOMORPHISM. We develop a framework involving 10 relevant parameters for each of H and G (such as treewidth, pathwidth, genus, maximum degree, number of vertices, number of components, etc.), and ask if an algorithm with running time ft (p(1),p(2), ..., p(l)) . n(f2(pl+1, ..., pk)) exists, where each of p(1), ..., p(k) is one of the 10 parameters depending only on H or G. We show that all the questions arising in this framework are answered by a set of 11 maximal positive results (algorithms) and a set of 17 maximal negative results (hardness proofs);some of these results already appear in the literature, while others are new in this paper. On the algorithmic side, our study reveals for example that an unexpected combination of bounded degree, genus, and feedback vertex set number of G gives rise to a highly nontrivial algorithm for SUBGRAPH ISOMORPHISM. On the hardness side, we present W[1]-hardness proofs under extremely restricted conditions, such as when H is a bounded-degree tree of constant pathwidth and G is a planar graph of bounded pathwidth.

关键词： parameterized complexity subgraph isomorphism

来源：评论

学校读者我要写书评

暂无评论

Algorithms and Turing kernels for detecting and counting small patterns in unit disk graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2025年 148卷

作者： Nederlof, Jesper Szilagyi, Krisztina Univ Utrecht Utrecht Netherlands

In this paper we investigate the parameterized complexity of counting and detecting small patterns in unit disk graphs: Given an n-vertex unit disk graph G with an embedding of ply p (i.e. G is an intersection graph of closed unit disks, and each point is contained in at most p disks) and a k-vertex unit disk graph P, count the number of (induced) copies of Pin G. For general patterns P, we give an 2O(pk/ log k)nO (1) time algorithm for counting pattern occurrences. We show this is tight, even for ply p = 2: any 2o(n/ log n)nO (1) time algorithm violates the Exponential Time Hypothesis (ETH). Our approach combines tools developed for planar subgraph isomorphism such as 'efficient inclusion-exclusion' from Nederlof (2020) [15], and 'isomorphisms checks' from Bodlaender et al. (2016) [5] with a different separator hierarchy and a new bound on the number of non-isomorphic separations tailored for unit disk graphs. (c) 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： Unit disk graphs Subgraph isomorphism parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

The influence of dimensions on the complexity of computing decision trees

引用

ARTIFICIAL INTELLIGENCE 2025年 343卷

作者： Kobourov, Stephen Loffler, Maarten Montecchiani, Fabrizio Pilipczuk, Marcin Rutter, Ignaz Seidel, Raimund Sorge, Manuel Wulms, Jules Tech Univ Munich Dept Comp Sci Munich Germany Univ Utrecht Dept Informat & Comp Sci Utrecht Netherlands Univ Perugia Dept Engn Perugia Italy Univ Warsaw Fac Math Informat & Mech Warsaw Poland Univ Passau Fac Comp Sci & Math Passau Germany Saarland Univ Dept Comp Sci Saarbrucken Germany TU Wien Inst Logic & Computat Vienna Austria

A decision tree recursively splits a feature space & Ropf;(d) and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work considers heuristic algorithms that compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum- size tree for the given training data. We study this problem with respect to the number d of dimensions of the feature space & Ropf;(d), which contains n training examples. We show that it can be solved in O(n(2d+1)) time, but under reasonable complexity-theoretic assumptions it is not possible to achieve f(d) & sdot;n(O(d / log d)) running time. The problem is solvable in (dR)(O(dR))& sdot;n(1+o(1) )time if there are exactly two classes and R is an upper bound on the number of tree leaves labeled with the first class.

关键词： Decision trees parameterized complexity Machine learning

来源：评论

学校读者我要写书评

暂无评论

parameterized inapproximability of Morse matching

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2025年 126卷

作者： Bauer, Ulrich Rathod, Abhishek Tech Univ Munich Munich Germany Ben Gurion Univ Negev Beer Sheva Israel

We study the problem of minimizing the number of critical simplices from the point of view of inapproximability and parameterized complexity. We first show inapproximability of MIN-MORSE MATCHING within a factor of 2 log ( 1-r) n . Our second result shows that MIN- MORSE MATCHING is W [ P ]-hard with respect to the standard parameter. Next, we show that MIN-MORSE MATCHING with standard parameterization has no FPT approximation algorithm for any approximation factor rho . The above hardness results are applicable to complexes of dimension >= 2. On the positive side, we provide a factor O( n log n ) approximation algorithm for MIN-MORSE MATCHING on 2-complexes, noting that no such algorithm is known for higher dimensional complexes. Finally, we devise discrete gradients with very few critical simplices for typical instances drawn from a fairly wide range of parameter values of the Costa-Farber model of random complexes. (c) 2024 Published by Elsevier B.V.

关键词： Discrete Morse theory Approximation algorithms parameterized complexity Stochastic topology

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Satisfying Almost All Linear Equations over F₂

引用

THEORY OF COMPUTING SYSTEMS 2013年第4期52卷 719-728页

作者： Crowston, R. Gutin, G. Jones, M. Yeo, A. Univ London Egham TW20 0EX Surrey England Univ Johannesburg ZA-2006 Auckland Pk South Africa

The problem MaxLin2 can be stated as follows. We are given a system S of m equations in variables x (1),aEuro broken vertical bar,x (n) , where each equation is assigned a positive integral weight w (j) and , I (j) aS dagger{1,2,aEuro broken vertical bar,n} for j=1,aEuro broken vertical bar,m. We are required to find an assignment of values in to the variables in order to maximize the total weight of the satisfied equations. Let W be the total weight of all equations in S. We consider the following parameterized version of MaxLin2: decide whether there is an assignment satisfying equations of total weight at least W-k, where k is a nonnegative parameter. We prove that this parameterized problem is W[1]-hard even if each equation of S has exactly three variables and every variable appears in exactly three equations and, moreover, each weight w (j) equals 1 and no two equations have the same left-hand side. We show the tightness of this result by proving that if each equation has at most two variables then the parameterized problem is fixed-parameter tractable. We also prove that if no variable appears in more than two equations then we can maximize the total weight of satisfied equations in polynomial time.

关键词： parameterized complexity Linear equations Finite field

来源：评论

学校读者我要写书评

暂无评论

complexity of scheduling few types of jobs on related and unrelated machines

引用

JOURNAL OF SCHEDULING 2025年第1期28卷 139-156页

作者： Koutecky, Martin Zink, Johannes Charles Univ Prague Prague Czech Republic Univ Wurzburg Wurzburg Germany

The task of scheduling jobs to machines while minimizing the total makespan, the sum of weighted completion times, or a norm of the load vector are among the oldest and most fundamental tasks in combinatorial optimization. Since all of these problems are in general NP-hard, much attention has been given to the regime where there is only a small number k of job types, but possibly the number of jobs n is large;this is the few job types, high-multiplicity regime. Despite many positive results, the hardness boundary of this regime was not understood until now. We show that makespan minimization on uniformly related machines (Q|HM|Cmax\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Q|HM|C_{\max }$$\end{document}) is NP-hard already with 6 job types, and that the related Cutting Stock problem is NP-hard already with 8 item types. For the more general unrelated machines model (R|HM|Cmax\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R|HM|C_{\max }$$\end{document}), we show that if the largest job size pmax\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p_{\max }$$\end{document} or the number of jobs n is polynomially bounded in the instance size |I|, there are algorithms with complexity |I|poly(k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|I|<^>{{{\,\ma

关键词： High-multiplicity jobs Cutting stock Hardness parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：